1 /*

     2  * Copyright (c) 2003, 2013, 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.rsa;

    27 

    28 import java.util.*;

    29 

    30 import java.security.*;

    31 import java.security.spec.*;

    32 

    33 import javax.crypto.BadPaddingException;

    34 import javax.crypto.spec.PSource;

    35 import javax.crypto.spec.OAEPParameterSpec;

    36 

    37 import sun.security.jca.JCAUtil;

    38 

    39 /**

    40  * RSA padding and unpadding.

    41  *

    42  * The various PKCS#1 versions can be found in the EMC/RSA Labs

    43  * web site, which is currently:

    44  *

    45  *     http://www.emc.com/emc-plus/rsa-labs/index.htm

    46  *

    47  * or in the IETF RFCs derived from the above PKCS#1 standards.

    48  *

    49  *     RFC 2313: v1.5

    50  *     RFC 2437: v2.0

    51  *     RFC 3447: v2.1

    52  *

    53  * The format of PKCS#1 v1.5 padding is:

    54  *

    55  *   0x00 | BT | PS...PS | 0x00 | data...data

    56  *

    57  * where BT is the blocktype (1 or 2). The length of the entire string

    58  * must be the same as the size of the modulus (i.e. 128 byte for a 1024 bit

    59  * key). Per spec, the padding string must be at least 8 bytes long. That

    60  * leaves up to (length of key in bytes) - 11 bytes for the data.

    61  *

    62  * OAEP padding was introduced in PKCS#1 v2.0 and is a bit more complicated

    63  * and has a number of options. We support:

    64  *

    65  *   . arbitrary hash functions ('Hash' in the specification), MessageDigest

    66  *     implementation must be available

    67  *   . MGF1 as the mask generation function

    68  *   . the empty string as the default value for label L and whatever

    69  *     specified in javax.crypto.spec.OAEPParameterSpec

    70  *

    71  * The algorithms (representations) are forwards-compatible: that is,

    72  * the algorithm described in previous releases are in later releases.

    73  * However, additional comments/checks/clarifications were added to the

    74  * later versions based on real-world experience (e.g. stricter v1.5

    75  * format checking.)

    76  *

    77  * Note: RSA keys should be at least 512 bits long

    78  *

    79  * @since   1.5

    80  * @author  Andreas Sterbenz

    81  */

    82 public final class RSAPadding {

    83 

    84     // NOTE: the constants below are embedded in the JCE RSACipher class

    85     // file. Do not change without coordinating the update

    86 

    87     // PKCS#1 v1.5 padding, blocktype 1 (signing)

    88     public final static int PAD_BLOCKTYPE_1    = 1;

    89     // PKCS#1 v1.5 padding, blocktype 2 (encryption)

    90     public final static int PAD_BLOCKTYPE_2    = 2;

    91     // nopadding. Does not do anything, but allows simpler RSACipher code

    92     public final static int PAD_NONE           = 3;

    93     // PKCS#1 v2.1 OAEP padding

    94     public final static int PAD_OAEP_MGF1 = 4;

    95 

    96     // type, one of PAD_*

    97     private final int type;

    98 

    99     // size of the padded block (i.e. size of the modulus)

   100     private final int paddedSize;

   101 

   102     // PRNG used to generate padding bytes (PAD_BLOCKTYPE_2, PAD_OAEP_MGF1)

   103     private SecureRandom random;

   104 

   105     // maximum size of the data

   106     private final int maxDataSize;

   107 

   108     // OAEP: main messagedigest

   109     private MessageDigest md;

   110 

   111     // OAEP: message digest for MGF1

   112     private MessageDigest mgfMd;

   113 

   114     // OAEP: value of digest of data (user-supplied or zero-length) using md

   115     private byte[] lHash;

   116 

   117     /**

   118      * Get a RSAPadding instance of the specified type.

   119      * Keys used with this padding must be paddedSize bytes long.

   120      */

   121     public static RSAPadding getInstance(int type, int paddedSize)

   122             throws InvalidKeyException, InvalidAlgorithmParameterException {

   123         return new RSAPadding(type, paddedSize, null, null);

   124     }

   125 

   126     /**

   127      * Get a RSAPadding instance of the specified type.

   128      * Keys used with this padding must be paddedSize bytes long.

   129      */

   130     public static RSAPadding getInstance(int type, int paddedSize,

   131             SecureRandom random) throws InvalidKeyException,

   132             InvalidAlgorithmParameterException {

   133         return new RSAPadding(type, paddedSize, random, null);

   134     }

   135 

   136     /**

   137      * Get a RSAPadding instance of the specified type, which must be

   138      * OAEP. Keys used with this padding must be paddedSize bytes long.

   139      */

   140     public static RSAPadding getInstance(int type, int paddedSize,

   141             SecureRandom random, OAEPParameterSpec spec)

   142         throws InvalidKeyException, InvalidAlgorithmParameterException {

   143         return new RSAPadding(type, paddedSize, random, spec);

   144     }

   145 

   146     // internal constructor

   147     private RSAPadding(int type, int paddedSize, SecureRandom random,

   148             OAEPParameterSpec spec) throws InvalidKeyException,

   149             InvalidAlgorithmParameterException {

   150         this.type = type;

   151         this.paddedSize = paddedSize;

   152         this.random = random;

   153         if (paddedSize < 64) {

   154             // sanity check, already verified in RSASignature/RSACipher

   155             throw new InvalidKeyException("Padded size must be at least 64");

   156         }

   157         switch (type) {

   158         case PAD_BLOCKTYPE_1:

   159         case PAD_BLOCKTYPE_2:

   160             maxDataSize = paddedSize - 11;

   161             break;

   162         case PAD_NONE:

   163             maxDataSize = paddedSize;

   164             break;

   165         case PAD_OAEP_MGF1:

   166             String mdName = "SHA-1";

   167             String mgfMdName = "SHA-1";

   168             byte[] digestInput = null;

   169             try {

   170                 if (spec != null) {

   171                     mdName = spec.getDigestAlgorithm();

   172                     String mgfName = spec.getMGFAlgorithm();

   173                     if (!mgfName.equalsIgnoreCase("MGF1")) {

   174                         throw new InvalidAlgorithmParameterException

   175                             ("Unsupported MGF algo: " + mgfName);

   176                     }

   177                     mgfMdName = ((MGF1ParameterSpec)spec.getMGFParameters())

   178                             .getDigestAlgorithm();

   179                     PSource pSrc = spec.getPSource();

   180                     String pSrcAlgo = pSrc.getAlgorithm();

   181                     if (!pSrcAlgo.equalsIgnoreCase("PSpecified")) {

   182                         throw new InvalidAlgorithmParameterException

   183                             ("Unsupported pSource algo: " + pSrcAlgo);

   184                     }

   185                     digestInput = ((PSource.PSpecified) pSrc).getValue();

   186                 }

   187                 md = MessageDigest.getInstance(mdName);

   188                 mgfMd = MessageDigest.getInstance(mgfMdName);

   189             } catch (NoSuchAlgorithmException e) {

   190                 throw new InvalidKeyException

   191                         ("Digest " + mdName + " not available", e);

   192             }

   193             lHash = getInitialHash(md, digestInput);

   194             int digestLen = lHash.length;

   195             maxDataSize = paddedSize - 2 - 2 * digestLen;

   196             if (maxDataSize <= 0) {

   197                 throw new InvalidKeyException

   198                         ("Key is too short for encryption using OAEPPadding" +

   199                          " with " + mdName + " and MGF1" + mgfMdName);

   200             }

   201             break;

   202         default:

   203             throw new InvalidKeyException("Invalid padding: " + type);

   204         }

   205     }

   206 

   207     // cache of hashes of zero length data

   208     private static final Map<String,byte[]> emptyHashes =

   209         Collections.synchronizedMap(new HashMap<String,byte[]>());

   210 

   211     /**

   212      * Return the value of the digest using the specified message digest

   213      * <code>md</code> and the digest input <code>digestInput</code>.

   214      * if <code>digestInput</code> is null or 0-length, zero length

   215      * is used to generate the initial digest.

   216      * Note: the md object must be in reset state

   217      */

   218     private static byte[] getInitialHash(MessageDigest md,

   219         byte[] digestInput) {

   220         byte[] result;

   221         if ((digestInput == null) || (digestInput.length == 0)) {

   222             String digestName = md.getAlgorithm();

   223             result = emptyHashes.get(digestName);

   224             if (result == null) {

   225                 result = md.digest();

   226                 emptyHashes.put(digestName, result);

   227             }

   228         } else {

   229             result = md.digest(digestInput);

   230         }

   231         return result;

   232     }

   233 

   234     /**

   235      * Return the maximum size of the plaintext data that can be processed

   236      * using this object.

   237      */

   238     public int getMaxDataSize() {

   239         return maxDataSize;

   240     }

   241 

   242     /**

   243      * Pad the data and return the padded block.

   244      */

   245     public byte[] pad(byte[] data, int ofs, int len)

   246             throws BadPaddingException {

   247         return pad(RSACore.convert(data, ofs, len));

   248     }

   249 

   250     /**

   251      * Pad the data and return the padded block.

   252      */

   253     public byte[] pad(byte[] data) throws BadPaddingException {

   254         if (data.length > maxDataSize) {

   255             throw new BadPaddingException("Data must be shorter than "

   256                 + (maxDataSize + 1) + " bytes");

   257         }

   258         switch (type) {

   259         case PAD_NONE:

   260             return data;

   261         case PAD_BLOCKTYPE_1:

   262         case PAD_BLOCKTYPE_2:

   263             return padV15(data);

   264         case PAD_OAEP_MGF1:

   265             return padOAEP(data);

   266         default:

   267             throw new AssertionError();

   268         }

   269     }

   270 

   271     /**

   272      * Unpad the padded block and return the data.

   273      */

   274     public byte[] unpad(byte[] padded, int ofs, int len)

   275             throws BadPaddingException {

   276         return unpad(RSACore.convert(padded, ofs, len));

   277     }

   278 

   279     /**

   280      * Unpad the padded block and return the data.

   281      */

   282     public byte[] unpad(byte[] padded) throws BadPaddingException {

   283         if (padded.length != paddedSize) {

   284             throw new BadPaddingException("Decryption error");

   285         }

   286         switch (type) {

   287         case PAD_NONE:

   288             return padded;

   289         case PAD_BLOCKTYPE_1:

   290         case PAD_BLOCKTYPE_2:

   291             return unpadV15(padded);

   292         case PAD_OAEP_MGF1:

   293             return unpadOAEP(padded);

   294         default:

   295             throw new AssertionError();

   296         }

   297     }

   298 

   299     /**

   300      * PKCS#1 v1.5 padding (blocktype 1 and 2).

   301      */

   302     private byte[] padV15(byte[] data) throws BadPaddingException {

   303         byte[] padded = new byte[paddedSize];

   304         System.arraycopy(data, 0, padded, paddedSize - data.length,

   305             data.length);

   306         int psSize = paddedSize - 3 - data.length;

   307         int k = 0;

   308         padded[k++] = 0;

   309         padded[k++] = (byte)type;

   310         if (type == PAD_BLOCKTYPE_1) {

   311             // blocktype 1: all padding bytes are 0xff

   312             while (psSize-- > 0) {

   313                 padded[k++] = (byte)0xff;

   314             }

   315         } else {

   316             // blocktype 2: padding bytes are random non-zero bytes

   317             if (random == null) {

   318                 random = JCAUtil.getSecureRandom();

   319             }

   320             // generate non-zero padding bytes

   321             // use a buffer to reduce calls to SecureRandom

   322             byte[] r = new byte[64];

   323             int i = -1;

   324             while (psSize-- > 0) {

   325                 int b;

   326                 do {

   327                     if (i < 0) {

   328                         random.nextBytes(r);

   329                         i = r.length - 1;

   330                     }

   331                     b = r[i--] & 0xff;

   332                 } while (b == 0);

   333                 padded[k++] = (byte)b;

   334             }

   335         }

   336         return padded;

   337     }

   338 

   339     /**

   340      * PKCS#1 v1.5 unpadding (blocktype 1 (signature) and 2 (encryption)).

   341      *

   342      * Note that we want to make it a constant-time operation

   343      */

   344     private byte[] unpadV15(byte[] padded) throws BadPaddingException {

   345         int k = 0;

   346         boolean bp = false;

   347 

   348         if (padded[k++] != 0) {

   349             bp = true;

   350         }

   351         if (padded[k++] != type) {

   352             bp = true;

   353         }

   354         int p = 0;

   355         while (k < padded.length) {

   356             int b = padded[k++] & 0xff;

   357             if ((b == 0) && (p == 0)) {

   358                 p = k;

   359             }

   360             if ((k == padded.length) && (p == 0)) {

   361                 bp = true;

   362             }

   363             if ((type == PAD_BLOCKTYPE_1) && (b != 0xff) &&

   364                     (p == 0)) {

   365                 bp = true;

   366             }

   367         }

   368         int n = padded.length - p;

   369         if (n > maxDataSize) {

   370             bp = true;

   371         }

   372 

   373         // copy useless padding array for a constant-time method

   374         byte[] padding = new byte[p];

   375         System.arraycopy(padded, 0, padding, 0, p);

   376 

   377         byte[] data = new byte[n];

   378         System.arraycopy(padded, p, data, 0, n);

   379 

   380         BadPaddingException bpe = new BadPaddingException("Decryption error");

   381 

   382         if (bp) {

   383             throw bpe;

   384         } else {

   385             return data;

   386         }

   387     }

   388 

   389     /**

   390      * PKCS#1 v2.0 OAEP padding (MGF1).

   391      * Paragraph references refer to PKCS#1 v2.1 (June 14, 2002)

   392      */

   393     private byte[] padOAEP(byte[] M) throws BadPaddingException {

   394         if (random == null) {

   395             random = JCAUtil.getSecureRandom();

   396         }

   397         int hLen = lHash.length;

   398 

   399         // 2.d: generate a random octet string seed of length hLen

   400         // if necessary

   401         byte[] seed = new byte[hLen];

   402         random.nextBytes(seed);

   403 

   404         // buffer for encoded message EM

   405         byte[] EM = new byte[paddedSize];

   406 

   407         // start and length of seed (as index into EM)

   408         int seedStart = 1;

   409         int seedLen = hLen;

   410 

   411         // copy seed into EM

   412         System.arraycopy(seed, 0, EM, seedStart, seedLen);

   413 

   414         // start and length of data block DB in EM

   415         // we place it inside of EM to reduce copying

   416         int dbStart = hLen + 1;

   417         int dbLen = EM.length - dbStart;

   418 

   419         // start of message M in EM

   420         int mStart = paddedSize - M.length;

   421 

   422         // build DB

   423         // 2.b: Concatenate lHash, PS, a single octet with hexadecimal value

   424         // 0x01, and the message M to form a data block DB of length

   425         // k - hLen -1 octets as DB = lHash || PS || 0x01 || M

   426         // (note that PS is all zeros)

   427         System.arraycopy(lHash, 0, EM, dbStart, hLen);

   428         EM[mStart - 1] = 1;

   429         System.arraycopy(M, 0, EM, mStart, M.length);

   430 

   431         // produce maskedDB

   432         mgf1(EM, seedStart, seedLen, EM, dbStart, dbLen);

   433 

   434         // produce maskSeed

   435         mgf1(EM, dbStart, dbLen, EM, seedStart, seedLen);

   436 

   437         return EM;

   438     }

   439 

   440     /**

   441      * PKCS#1 v2.1 OAEP unpadding (MGF1).

   442      */

   443     private byte[] unpadOAEP(byte[] padded) throws BadPaddingException {

   444         byte[] EM = padded;

   445         boolean bp = false;

   446         int hLen = lHash.length;

   447 

   448         if (EM[0] != 0) {

   449             bp = true;

   450         }

   451 

   452         int seedStart = 1;

   453         int seedLen = hLen;

   454 

   455         int dbStart = hLen + 1;

   456         int dbLen = EM.length - dbStart;

   457 

   458         mgf1(EM, dbStart, dbLen, EM, seedStart, seedLen);

   459         mgf1(EM, seedStart, seedLen, EM, dbStart, dbLen);

   460 

   461         // verify lHash == lHash'

   462         for (int i = 0; i < hLen; i++) {

   463             if (lHash[i] != EM[dbStart + i]) {

   464                 bp = true;

   465             }

   466         }

   467 

   468         int padStart = dbStart + hLen;

   469         int onePos = -1;

   470 

   471         for (int i = padStart; i < EM.length; i++) {

   472             int value = EM[i];

   473             if (onePos == -1) {

   474                 if (value == 0x00) {

   475                     // continue;

   476                 } else if (value == 0x01) {

   477                     onePos = i;

   478                 } else {  // Anything other than {0,1} is bad.

   479                     bp = true;

   480                 }

   481             }

   482         }

   483 

   484         // We either ran off the rails or found something other than 0/1.

   485         if (onePos == -1) {

   486             bp = true;

   487             onePos = EM.length - 1;  // Don't inadvertently return any data.

   488         }

   489 

   490         int mStart = onePos + 1;

   491 

   492         // copy useless padding array for a constant-time method

   493         byte [] tmp = new byte[mStart - padStart];

   494         System.arraycopy(EM, padStart, tmp, 0, tmp.length);

   495 

   496         byte [] m = new byte[EM.length - mStart];

   497         System.arraycopy(EM, mStart, m, 0, m.length);

   498 

   499         BadPaddingException bpe = new BadPaddingException("Decryption error");

   500 

   501         if (bp) {

   502             throw bpe;

   503         } else {

   504             return m;

   505         }

   506     }

   507 

   508     /**

   509      * Compute MGF1 using mgfMD as the message digest.

   510      * Note that we combine MGF1 with the XOR operation to reduce data

   511      * copying.

   512      *

   513      * We generate maskLen bytes of MGF1 from the seed and XOR it into

   514      * out[] starting at outOfs;

   515      */

   516     private void mgf1(byte[] seed, int seedOfs, int seedLen,

   517             byte[] out, int outOfs, int maskLen)  throws BadPaddingException {

   518         byte[] C = new byte[4]; // 32 bit counter

   519         byte[] digest = new byte[mgfMd.getDigestLength()];

   520         while (maskLen > 0) {

   521             mgfMd.update(seed, seedOfs, seedLen);

   522             mgfMd.update(C);

   523             try {

   524                 mgfMd.digest(digest, 0, digest.length);

   525             } catch (DigestException e) {

   526                 // should never happen

   527                 throw new BadPaddingException(e.toString());

   528             }

   529             for (int i = 0; (i < digest.length) && (maskLen > 0); maskLen--) {

   530                 out[outOfs++] ^= digest[i++];

   531             }

   532             if (maskLen > 0) {

   533                 // increment counter

   534                 for (int i = C.length - 1; (++C[i] == 0) && (i > 0); i--) {

   535                     // empty

   536                 }

   537             }

   538         }

   539     }

   540 }