1 /*
   2  * Copyright (c) 1996, 2017, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package sun.security.pkcs;
  27 
  28 import java.io.OutputStream;
  29 import java.io.IOException;
  30 import java.math.BigInteger;
  31 import java.security.CryptoPrimitive;
  32 import java.security.InvalidKeyException;
  33 import java.security.MessageDigest;
  34 import java.security.NoSuchAlgorithmException;
  35 import java.security.Principal;
  36 import java.security.PublicKey;
  37 import java.security.Signature;
  38 import java.security.SignatureException;
  39 import java.security.Timestamp;
  40 import java.security.cert.CertPathValidatorException;
  41 import java.security.cert.CertificateException;
  42 import java.security.cert.CertificateFactory;
  43 import java.security.cert.CertPath;
  44 import java.security.cert.X509Certificate;
  45 import java.util.ArrayList;
  46 import java.util.Arrays;
  47 import java.util.Collections;
  48 import java.util.EnumSet;
  49 import java.util.Set;
  50 
  51 import sun.security.timestamp.TimestampToken;
  52 import sun.security.util.ConstraintsParameters;
  53 import sun.security.util.Debug;
  54 import sun.security.util.DerEncoder;
  55 import sun.security.util.DerInputStream;
  56 import sun.security.util.DerOutputStream;
  57 import sun.security.util.DerValue;
  58 import sun.security.util.DisabledAlgorithmConstraints;
  59 import sun.security.util.HexDumpEncoder;
  60 import sun.security.util.KeyUtil;
  61 import sun.security.util.ObjectIdentifier;
  62 import sun.security.x509.AlgorithmId;
  63 import sun.security.x509.X500Name;
  64 import sun.security.x509.KeyUsageExtension;
  65 
  66 /**
  67  * A SignerInfo, as defined in PKCS#7's signedData type.
  68  *
  69  * @author Benjamin Renaud
  70  */
  71 public class SignerInfo implements DerEncoder {
  72 
  73     // Digest and Signature restrictions
  74     private static final Set<CryptoPrimitive> DIGEST_PRIMITIVE_SET =
  75             Collections.unmodifiableSet(EnumSet.of(CryptoPrimitive.MESSAGE_DIGEST));
  76 
  77     private static final Set<CryptoPrimitive> SIG_PRIMITIVE_SET =
  78             Collections.unmodifiableSet(EnumSet.of(CryptoPrimitive.SIGNATURE));
  79 
  80     private static final DisabledAlgorithmConstraints JAR_DISABLED_CHECK =
  81             new DisabledAlgorithmConstraints(
  82                     DisabledAlgorithmConstraints.PROPERTY_JAR_DISABLED_ALGS);
  83 
  84     BigInteger version;
  85     X500Name issuerName;
  86     BigInteger certificateSerialNumber;
  87     AlgorithmId digestAlgorithmId;
  88     AlgorithmId digestEncryptionAlgorithmId;
  89     byte[] encryptedDigest;
  90     Timestamp timestamp;
  91     private boolean hasTimestamp = true;
  92     private static final Debug debug = Debug.getInstance("jar");
  93 
  94     PKCS9Attributes authenticatedAttributes;
  95     PKCS9Attributes unauthenticatedAttributes;
  96 
  97     public SignerInfo(X500Name  issuerName,
  98                       BigInteger serial,
  99                       AlgorithmId digestAlgorithmId,
 100                       AlgorithmId digestEncryptionAlgorithmId,
 101                       byte[] encryptedDigest) {
 102         this.version = BigInteger.ONE;
 103         this.issuerName = issuerName;
 104         this.certificateSerialNumber = serial;
 105         this.digestAlgorithmId = digestAlgorithmId;
 106         this.digestEncryptionAlgorithmId = digestEncryptionAlgorithmId;
 107         this.encryptedDigest = encryptedDigest;
 108     }
 109 
 110     public SignerInfo(X500Name  issuerName,
 111                       BigInteger serial,
 112                       AlgorithmId digestAlgorithmId,
 113                       PKCS9Attributes authenticatedAttributes,
 114                       AlgorithmId digestEncryptionAlgorithmId,
 115                       byte[] encryptedDigest,
 116                       PKCS9Attributes unauthenticatedAttributes) {
 117         this.version = BigInteger.ONE;
 118         this.issuerName = issuerName;
 119         this.certificateSerialNumber = serial;
 120         this.digestAlgorithmId = digestAlgorithmId;
 121         this.authenticatedAttributes = authenticatedAttributes;
 122         this.digestEncryptionAlgorithmId = digestEncryptionAlgorithmId;
 123         this.encryptedDigest = encryptedDigest;
 124         this.unauthenticatedAttributes = unauthenticatedAttributes;
 125     }
 126 
 127     /**
 128      * Parses a PKCS#7 signer info.
 129      */
 130     public SignerInfo(DerInputStream derin)
 131         throws IOException, ParsingException
 132     {
 133         this(derin, false);
 134     }
 135 
 136     /**
 137      * Parses a PKCS#7 signer info.
 138      *
 139      * <p>This constructor is used only for backwards compatibility with
 140      * PKCS#7 blocks that were generated using JDK1.1.x.
 141      *
 142      * @param derin the ASN.1 encoding of the signer info.
 143      * @param oldStyle flag indicating whether or not the given signer info
 144      * is encoded according to JDK1.1.x.
 145      */
 146     public SignerInfo(DerInputStream derin, boolean oldStyle)
 147         throws IOException, ParsingException
 148     {
 149         // version
 150         version = derin.getBigInteger();
 151 
 152         // issuerAndSerialNumber
 153         DerValue[] issuerAndSerialNumber = derin.getSequence(2);
 154         byte[] issuerBytes = issuerAndSerialNumber[0].toByteArray();
 155         issuerName = new X500Name(new DerValue(DerValue.tag_Sequence,
 156                                                issuerBytes));
 157         certificateSerialNumber = issuerAndSerialNumber[1].getBigInteger();
 158 
 159         // digestAlgorithmId
 160         DerValue tmp = derin.getDerValue();
 161 
 162         digestAlgorithmId = AlgorithmId.parse(tmp);
 163 
 164         // authenticatedAttributes
 165         if (oldStyle) {
 166             // In JDK1.1.x, the authenticatedAttributes are always present,
 167             // encoded as an empty Set (Set of length zero)
 168             derin.getSet(0);
 169         } else {
 170             // check if set of auth attributes (implicit tag) is provided
 171             // (auth attributes are OPTIONAL)
 172             if ((byte)(derin.peekByte()) == (byte)0xA0) {
 173                 authenticatedAttributes = new PKCS9Attributes(derin);
 174             }
 175         }
 176 
 177         // digestEncryptionAlgorithmId - little RSA naming scheme -
 178         // signature == encryption...
 179         tmp = derin.getDerValue();
 180 
 181         digestEncryptionAlgorithmId = AlgorithmId.parse(tmp);
 182 
 183         // encryptedDigest
 184         encryptedDigest = derin.getOctetString();
 185 
 186         // unauthenticatedAttributes
 187         if (oldStyle) {
 188             // In JDK1.1.x, the unauthenticatedAttributes are always present,
 189             // encoded as an empty Set (Set of length zero)
 190             derin.getSet(0);
 191         } else {
 192             // check if set of unauth attributes (implicit tag) is provided
 193             // (unauth attributes are OPTIONAL)
 194             if (derin.available() != 0
 195                 && (byte)(derin.peekByte()) == (byte)0xA1) {
 196                 unauthenticatedAttributes =
 197                     new PKCS9Attributes(derin, true);// ignore unsupported attrs
 198             }
 199         }
 200 
 201         // all done
 202         if (derin.available() != 0) {
 203             throw new ParsingException("extra data at the end");
 204         }
 205     }
 206 
 207     public void encode(DerOutputStream out) throws IOException {
 208 
 209         derEncode(out);
 210     }
 211 
 212     /**
 213      * DER encode this object onto an output stream.
 214      * Implements the {@code DerEncoder} interface.
 215      *
 216      * @param out
 217      * the output stream on which to write the DER encoding.
 218      *
 219      * @exception IOException on encoding error.
 220      */
 221     public void derEncode(OutputStream out) throws IOException {
 222         DerOutputStream seq = new DerOutputStream();
 223         seq.putInteger(version);
 224         DerOutputStream issuerAndSerialNumber = new DerOutputStream();
 225         issuerName.encode(issuerAndSerialNumber);
 226         issuerAndSerialNumber.putInteger(certificateSerialNumber);
 227         seq.write(DerValue.tag_Sequence, issuerAndSerialNumber);
 228 
 229         digestAlgorithmId.encode(seq);
 230 
 231         // encode authenticated attributes if there are any
 232         if (authenticatedAttributes != null)
 233             authenticatedAttributes.encode((byte)0xA0, seq);
 234 
 235         digestEncryptionAlgorithmId.encode(seq);
 236 
 237         seq.putOctetString(encryptedDigest);
 238 
 239         // encode unauthenticated attributes if there are any
 240         if (unauthenticatedAttributes != null)
 241             unauthenticatedAttributes.encode((byte)0xA1, seq);
 242 
 243         DerOutputStream tmp = new DerOutputStream();
 244         tmp.write(DerValue.tag_Sequence, seq);
 245 
 246         out.write(tmp.toByteArray());
 247     }
 248 
 249 
 250 
 251     /*
 252      * Returns the (user) certificate pertaining to this SignerInfo.
 253      */
 254     public X509Certificate getCertificate(PKCS7 block)
 255         throws IOException
 256     {
 257         return block.getCertificate(certificateSerialNumber, issuerName);
 258     }
 259 
 260     /*
 261      * Returns the certificate chain pertaining to this SignerInfo.
 262      */
 263     public ArrayList<X509Certificate> getCertificateChain(PKCS7 block)
 264         throws IOException
 265     {
 266         X509Certificate userCert;
 267         userCert = block.getCertificate(certificateSerialNumber, issuerName);
 268         if (userCert == null)
 269             return null;
 270 
 271         ArrayList<X509Certificate> certList = new ArrayList<>();
 272         certList.add(userCert);
 273 
 274         X509Certificate[] pkcsCerts = block.getCertificates();
 275         if (pkcsCerts == null
 276             || userCert.getSubjectDN().equals(userCert.getIssuerDN())) {
 277             return certList;
 278         }
 279 
 280         Principal issuer = userCert.getIssuerDN();
 281         int start = 0;
 282         while (true) {
 283             boolean match = false;
 284             int i = start;
 285             while (i < pkcsCerts.length) {
 286                 if (issuer.equals(pkcsCerts[i].getSubjectDN())) {
 287                     // next cert in chain found
 288                     certList.add(pkcsCerts[i]);
 289                     // if selected cert is self-signed, we're done
 290                     // constructing the chain
 291                     if (pkcsCerts[i].getSubjectDN().equals(
 292                                             pkcsCerts[i].getIssuerDN())) {
 293                         start = pkcsCerts.length;
 294                     } else {
 295                         issuer = pkcsCerts[i].getIssuerDN();
 296                         X509Certificate tmpCert = pkcsCerts[start];
 297                         pkcsCerts[start] = pkcsCerts[i];
 298                         pkcsCerts[i] = tmpCert;
 299                         start++;
 300                     }
 301                     match = true;
 302                     break;
 303                 } else {
 304                     i++;
 305                 }
 306             }
 307             if (!match)
 308                 break;
 309         }
 310 
 311         return certList;
 312     }
 313 
 314     /* Returns null if verify fails, this signerInfo if
 315        verify succeeds. */
 316     SignerInfo verify(PKCS7 block, byte[] data)
 317     throws NoSuchAlgorithmException, SignatureException {
 318 
 319         try {
 320 
 321             ContentInfo content = block.getContentInfo();
 322             if (data == null) {
 323                 data = content.getContentBytes();
 324             }
 325 
 326             Timestamp timestamp = null;
 327             try {
 328                 timestamp = getTimestamp();
 329             } catch (Exception ignore) {
 330             }
 331 
 332             ConstraintsParameters cparams =
 333                     new ConstraintsParameters(timestamp);
 334             String digestAlgname = getDigestAlgorithmId().getName();
 335 
 336             byte[] dataSigned;
 337 
 338             // if there are authenticate attributes, get the message
 339             // digest and compare it with the digest of data
 340             if (authenticatedAttributes == null) {
 341                 dataSigned = data;
 342             } else {
 343 
 344                 // first, check content type
 345                 ObjectIdentifier contentType = (ObjectIdentifier)
 346                        authenticatedAttributes.getAttributeValue(
 347                          PKCS9Attribute.CONTENT_TYPE_OID);
 348                 if (contentType == null ||
 349                     !contentType.equals(content.contentType))
 350                     return null;  // contentType does not match, bad SignerInfo
 351 
 352                 // now, check message digest
 353                 byte[] messageDigest = (byte[])
 354                     authenticatedAttributes.getAttributeValue(
 355                          PKCS9Attribute.MESSAGE_DIGEST_OID);
 356 
 357                 if (messageDigest == null) // fail if there is no message digest
 358                     return null;
 359 
 360                 // check that digest algorithm is not restricted
 361                 try {
 362                     JAR_DISABLED_CHECK.permits(digestAlgname, cparams);
 363                 } catch (CertPathValidatorException e) {
 364                     throw new SignatureException(e.getMessage(), e);
 365                 }
 366 
 367                 MessageDigest md = MessageDigest.getInstance(digestAlgname);
 368                 byte[] computedMessageDigest = md.digest(data);
 369 
 370                 if (messageDigest.length != computedMessageDigest.length)
 371                     return null;
 372                 for (int i = 0; i < messageDigest.length; i++) {
 373                     if (messageDigest[i] != computedMessageDigest[i])
 374                         return null;
 375                 }
 376 
 377                 // message digest attribute matched
 378                 // digest of original data
 379 
 380                 // the data actually signed is the DER encoding of
 381                 // the authenticated attributes (tagged with
 382                 // the "SET OF" tag, not 0xA0).
 383                 dataSigned = authenticatedAttributes.getDerEncoding();
 384             }
 385 
 386             // put together digest algorithm and encryption algorithm
 387             // to form signing algorithm
 388             String encryptionAlgname =
 389                 getDigestEncryptionAlgorithmId().getName();
 390 
 391             // Workaround: sometimes the encryptionAlgname is actually
 392             // a signature name
 393             String tmp = AlgorithmId.getEncAlgFromSigAlg(encryptionAlgname);
 394             if (tmp != null) encryptionAlgname = tmp;
 395             String algname = AlgorithmId.makeSigAlg(
 396                     digestAlgname, encryptionAlgname);
 397 
 398             // check that jar signature algorithm is not restricted
 399             try {
 400                 JAR_DISABLED_CHECK.permits(algname, cparams);
 401             } catch (CertPathValidatorException e) {
 402                 throw new SignatureException(e.getMessage(), e);
 403             }
 404 
 405             X509Certificate cert = getCertificate(block);
 406             if (cert == null) {
 407                 return null;
 408             }
 409             PublicKey key = cert.getPublicKey();
 410 
 411             // check if the public key is restricted
 412             if (!JAR_DISABLED_CHECK.permits(SIG_PRIMITIVE_SET, key)) {
 413                 throw new SignatureException("Public key check failed. " +
 414                         "Disabled key used: " +
 415                         KeyUtil.getKeySize(key) + " bit " +
 416                         key.getAlgorithm());
 417             }
 418 
 419             if (cert.hasUnsupportedCriticalExtension()) {
 420                 throw new SignatureException("Certificate has unsupported "
 421                                              + "critical extension(s)");
 422             }
 423 
 424             // Make sure that if the usage of the key in the certificate is
 425             // restricted, it can be used for digital signatures.
 426             // XXX We may want to check for additional extensions in the
 427             // future.
 428             boolean[] keyUsageBits = cert.getKeyUsage();
 429             if (keyUsageBits != null) {
 430                 KeyUsageExtension keyUsage;
 431                 try {
 432                     // We don't care whether or not this extension was marked
 433                     // critical in the certificate.
 434                     // We're interested only in its value (i.e., the bits set)
 435                     // and treat the extension as critical.
 436                     keyUsage = new KeyUsageExtension(keyUsageBits);
 437                 } catch (IOException ioe) {
 438                     throw new SignatureException("Failed to parse keyUsage "
 439                                                  + "extension");
 440                 }
 441 
 442                 boolean digSigAllowed = keyUsage.get(
 443                         KeyUsageExtension.DIGITAL_SIGNATURE).booleanValue();
 444 
 445                 boolean nonRepuAllowed = keyUsage.get(
 446                         KeyUsageExtension.NON_REPUDIATION).booleanValue();
 447 
 448                 if (!digSigAllowed && !nonRepuAllowed) {
 449                     throw new SignatureException("Key usage restricted: "
 450                                                  + "cannot be used for "
 451                                                  + "digital signatures");
 452                 }
 453             }
 454 
 455             Signature sig = Signature.getInstance(algname);
 456             sig.initVerify(key);
 457             sig.update(dataSigned);
 458             if (sig.verify(encryptedDigest)) {
 459                 return this;
 460             }
 461 
 462         } catch (IOException e) {
 463             throw new SignatureException("IO error verifying signature:\n" +
 464                                          e.getMessage());
 465 
 466         } catch (InvalidKeyException e) {
 467             throw new SignatureException("InvalidKey: " + e.getMessage());
 468 
 469         }
 470         return null;
 471     }
 472 
 473     /* Verify the content of the pkcs7 block. */
 474     SignerInfo verify(PKCS7 block)
 475     throws NoSuchAlgorithmException, SignatureException {
 476         return verify(block, null);
 477     }
 478 
 479 
 480     public BigInteger getVersion() {
 481             return version;
 482     }
 483 
 484     public X500Name getIssuerName() {
 485         return issuerName;
 486     }
 487 
 488     public BigInteger getCertificateSerialNumber() {
 489         return certificateSerialNumber;
 490     }
 491 
 492     public AlgorithmId getDigestAlgorithmId() {
 493         return digestAlgorithmId;
 494     }
 495 
 496     public PKCS9Attributes getAuthenticatedAttributes() {
 497         return authenticatedAttributes;
 498     }
 499 
 500     public AlgorithmId getDigestEncryptionAlgorithmId() {
 501         return digestEncryptionAlgorithmId;
 502     }
 503 
 504     public byte[] getEncryptedDigest() {
 505         return encryptedDigest;
 506     }
 507 
 508     public PKCS9Attributes getUnauthenticatedAttributes() {
 509         return unauthenticatedAttributes;
 510     }
 511 
 512     /**
 513      * Returns the timestamp PKCS7 data unverified.
 514      * @return a PKCS7 object
 515      */
 516     public PKCS7 getTsToken() throws IOException {
 517         if (unauthenticatedAttributes == null) {
 518             return null;
 519         }
 520         PKCS9Attribute tsTokenAttr =
 521                 unauthenticatedAttributes.getAttribute(
 522                         PKCS9Attribute.SIGNATURE_TIMESTAMP_TOKEN_OID);
 523         if (tsTokenAttr == null) {
 524             return null;
 525         }
 526         return new PKCS7((byte[])tsTokenAttr.getValue());
 527     }
 528 
 529     /*
 530      * Extracts a timestamp from a PKCS7 SignerInfo.
 531      *
 532      * Examines the signer's unsigned attributes for a
 533      * {@code signatureTimestampToken} attribute. If present,
 534      * then it is parsed to extract the date and time at which the
 535      * timestamp was generated.
 536      *
 537      * @param info A signer information element of a PKCS 7 block.
 538      *
 539      * @return A timestamp token or null if none is present.
 540      * @throws IOException if an error is encountered while parsing the
 541      *         PKCS7 data.
 542      * @throws NoSuchAlgorithmException if an error is encountered while
 543      *         verifying the PKCS7 object.
 544      * @throws SignatureException if an error is encountered while
 545      *         verifying the PKCS7 object.
 546      * @throws CertificateException if an error is encountered while generating
 547      *         the TSA's certpath.
 548      */
 549     public Timestamp getTimestamp()
 550         throws IOException, NoSuchAlgorithmException, SignatureException,
 551                CertificateException
 552     {
 553         if (timestamp != null || !hasTimestamp)
 554             return timestamp;
 555 
 556         PKCS7 tsToken = getTsToken();
 557         if (tsToken == null) {
 558             hasTimestamp = false;
 559             return null;
 560         }
 561 
 562         // Extract the content (an encoded timestamp token info)
 563         byte[] encTsTokenInfo = tsToken.getContentInfo().getData();
 564         // Extract the signer (the Timestamping Authority)
 565         // while verifying the content
 566         SignerInfo[] tsa = tsToken.verify(encTsTokenInfo);
 567         // Expect only one signer
 568         ArrayList<X509Certificate> chain = tsa[0].getCertificateChain(tsToken);
 569         CertificateFactory cf = CertificateFactory.getInstance("X.509");
 570         CertPath tsaChain = cf.generateCertPath(chain);
 571         // Create a timestamp token info object
 572         TimestampToken tsTokenInfo = new TimestampToken(encTsTokenInfo);
 573         // Check that the signature timestamp applies to this signature
 574         verifyTimestamp(tsTokenInfo);
 575         // Create a timestamp object
 576         timestamp = new Timestamp(tsTokenInfo.getDate(), tsaChain);
 577         return timestamp;
 578     }
 579 
 580     /*
 581      * Check that the signature timestamp applies to this signature.
 582      * Match the hash present in the signature timestamp token against the hash
 583      * of this signature.
 584      */
 585     private void verifyTimestamp(TimestampToken token)
 586         throws NoSuchAlgorithmException, SignatureException {
 587         String digestAlgname = token.getHashAlgorithm().getName();
 588         // check that algorithm is not restricted
 589         if (!JAR_DISABLED_CHECK.permits(DIGEST_PRIMITIVE_SET, digestAlgname,
 590                 null)) {
 591             throw new SignatureException("Timestamp token digest check failed. " +
 592                     "Disabled algorithm used: " + digestAlgname);
 593         }
 594 
 595         MessageDigest md =
 596             MessageDigest.getInstance(digestAlgname);
 597 
 598         if (!Arrays.equals(token.getHashedMessage(),
 599             md.digest(encryptedDigest))) {
 600 
 601             throw new SignatureException("Signature timestamp (#" +
 602                 token.getSerialNumber() + ") generated on " + token.getDate() +
 603                 " is inapplicable");
 604         }
 605 
 606         if (debug != null) {
 607             debug.println();
 608             debug.println("Detected signature timestamp (#" +
 609                 token.getSerialNumber() + ") generated on " + token.getDate());
 610             debug.println();
 611         }
 612     }
 613 
 614     public String toString() {
 615         HexDumpEncoder hexDump = new HexDumpEncoder();
 616 
 617         String out = "";
 618 
 619         out += "Signer Info for (issuer): " + issuerName + "\n";
 620         out += "\tversion: " + Debug.toHexString(version) + "\n";
 621         out += "\tcertificateSerialNumber: " +
 622                Debug.toHexString(certificateSerialNumber) + "\n";
 623         out += "\tdigestAlgorithmId: " + digestAlgorithmId + "\n";
 624         if (authenticatedAttributes != null) {
 625             out += "\tauthenticatedAttributes: " + authenticatedAttributes +
 626                    "\n";
 627         }
 628         out += "\tdigestEncryptionAlgorithmId: " + digestEncryptionAlgorithmId +
 629             "\n";
 630 
 631         out += "\tencryptedDigest: " + "\n" +
 632             hexDump.encodeBuffer(encryptedDigest) + "\n";
 633         if (unauthenticatedAttributes != null) {
 634             out += "\tunauthenticatedAttributes: " +
 635                    unauthenticatedAttributes + "\n";
 636         }
 637         return out;
 638     }
 639 }