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 static final int PAD_BLOCKTYPE_1 = 1;
89 // PKCS#1 v1.5 padding, blocktype 2 (encryption)
90 public static final int PAD_BLOCKTYPE_2 = 2;
91 // nopadding. Does not do anything, but allows simpler RSACipher code
92 public static final int PAD_NONE = 3;
93 // PKCS#1 v2.1 OAEP padding
94 public static final 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 but received "
257 + data.length + " bytes.");
258 }
259 switch (type) {
260 case PAD_NONE:
261 return data;
262 case PAD_BLOCKTYPE_1:
263 case PAD_BLOCKTYPE_2:
264 return padV15(data);
265 case PAD_OAEP_MGF1:
266 return padOAEP(data);
267 default:
268 throw new AssertionError();
269 }
270 }
271
272 /**
273 * Unpad the padded block and return the data.
274 */
275 public byte[] unpad(byte[] padded, int ofs, int len)
276 throws BadPaddingException {
277 return unpad(RSACore.convert(padded, ofs, len));
278 }
279
280 /**
281 * Unpad the padded block and return the data.
282 */
283 public byte[] unpad(byte[] padded) throws BadPaddingException {
284 if (padded.length != paddedSize) {
285 throw new BadPaddingException("Decryption error." +
286 "The padded array length (" + padded.length +
287 ") is not the specified padded size (" + paddedSize + ")");
288 }
289 switch (type) {
290 case PAD_NONE:
291 return padded;
292 case PAD_BLOCKTYPE_1:
293 case PAD_BLOCKTYPE_2:
294 return unpadV15(padded);
295 case PAD_OAEP_MGF1:
296 return unpadOAEP(padded);
297 default:
298 throw new AssertionError();
299 }
300 }
301
302 /**
303 * PKCS#1 v1.5 padding (blocktype 1 and 2).
304 */
305 private byte[] padV15(byte[] data) throws BadPaddingException {
306 byte[] padded = new byte[paddedSize];
307 System.arraycopy(data, 0, padded, paddedSize - data.length,
308 data.length);
309 int psSize = paddedSize - 3 - data.length;
310 int k = 0;
311 padded[k++] = 0;
312 padded[k++] = (byte)type;
313 if (type == PAD_BLOCKTYPE_1) {
314 // blocktype 1: all padding bytes are 0xff
315 while (psSize-- > 0) {
316 padded[k++] = (byte)0xff;
317 }
318 } else {
319 // blocktype 2: padding bytes are random non-zero bytes
320 if (random == null) {
321 random = JCAUtil.getSecureRandom();
322 }
323 // generate non-zero padding bytes
324 // use a buffer to reduce calls to SecureRandom
325 while (psSize > 0) {
326 // extra bytes to avoid zero bytes,
327 // number of zero bytes <= 4 in 98% cases
328 byte[] r = new byte[psSize + 4];
329 random.nextBytes(r);
330 for (int i = 0; i < r.length && psSize > 0; i++) {
331 if (r[i] != 0) {
332 padded[k++] = r[i];
333 psSize--;
334 }
335 }
336 }
337 }
338 return padded;
339 }
340
341 /**
342 * PKCS#1 v1.5 unpadding (blocktype 1 (signature) and 2 (encryption)).
343 *
344 * Note that we want to make it a constant-time operation
345 */
346 private byte[] unpadV15(byte[] padded) throws BadPaddingException {
347 int k = 0;
348 boolean bp = false;
349
350 if (padded[k++] != 0) {
351 bp = true;
352 }
353 if (padded[k++] != type) {
354 bp = true;
355 }
356 int p = 0;
357 while (k < padded.length) {
358 int b = padded[k++] & 0xff;
359 if ((b == 0) && (p == 0)) {
360 p = k;
361 }
362 if ((k == padded.length) && (p == 0)) {
363 bp = true;
364 }
365 if ((type == PAD_BLOCKTYPE_1) && (b != 0xff) &&
366 (p == 0)) {
367 bp = true;
368 }
369 }
370 int n = padded.length - p;
371 if (n > maxDataSize) {
372 bp = true;
373 }
374
375 // copy useless padding array for a constant-time method
376 byte[] padding = new byte[p];
377 System.arraycopy(padded, 0, padding, 0, p);
378
379 byte[] data = new byte[n];
380 System.arraycopy(padded, p, data, 0, n);
381
382 BadPaddingException bpe = new BadPaddingException("Decryption error");
383
384 if (bp) {
385 throw bpe;
386 } else {
387 return data;
388 }
389 }
390
391 /**
392 * PKCS#1 v2.0 OAEP padding (MGF1).
393 * Paragraph references refer to PKCS#1 v2.1 (June 14, 2002)
394 */
395 private byte[] padOAEP(byte[] M) throws BadPaddingException {
396 if (random == null) {
397 random = JCAUtil.getSecureRandom();
398 }
399 int hLen = lHash.length;
400
401 // 2.d: generate a random octet string seed of length hLen
402 // if necessary
403 byte[] seed = new byte[hLen];
404 random.nextBytes(seed);
405
406 // buffer for encoded message EM
407 byte[] EM = new byte[paddedSize];
408
409 // start and length of seed (as index into EM)
410 int seedStart = 1;
411 int seedLen = hLen;
412
413 // copy seed into EM
414 System.arraycopy(seed, 0, EM, seedStart, seedLen);
415
416 // start and length of data block DB in EM
417 // we place it inside of EM to reduce copying
418 int dbStart = hLen + 1;
419 int dbLen = EM.length - dbStart;
420
421 // start of message M in EM
422 int mStart = paddedSize - M.length;
423
424 // build DB
425 // 2.b: Concatenate lHash, PS, a single octet with hexadecimal value
426 // 0x01, and the message M to form a data block DB of length
427 // k - hLen -1 octets as DB = lHash || PS || 0x01 || M
428 // (note that PS is all zeros)
429 System.arraycopy(lHash, 0, EM, dbStart, hLen);
430 EM[mStart - 1] = 1;
431 System.arraycopy(M, 0, EM, mStart, M.length);
432
433 // produce maskedDB
434 mgf1(EM, seedStart, seedLen, EM, dbStart, dbLen);
435
436 // produce maskSeed
437 mgf1(EM, dbStart, dbLen, EM, seedStart, seedLen);
438
439 return EM;
440 }
441
442 /**
443 * PKCS#1 v2.1 OAEP unpadding (MGF1).
444 */
445 private byte[] unpadOAEP(byte[] padded) throws BadPaddingException {
446 byte[] EM = padded;
447 boolean bp = false;
448 int hLen = lHash.length;
449
450 if (EM[0] != 0) {
451 bp = true;
452 }
453
454 int seedStart = 1;
455 int seedLen = hLen;
456
457 int dbStart = hLen + 1;
458 int dbLen = EM.length - dbStart;
459
460 mgf1(EM, dbStart, dbLen, EM, seedStart, seedLen);
461 mgf1(EM, seedStart, seedLen, EM, dbStart, dbLen);
462
463 // verify lHash == lHash'
464 for (int i = 0; i < hLen; i++) {
465 if (lHash[i] != EM[dbStart + i]) {
466 bp = true;
467 }
468 }
469
470 int padStart = dbStart + hLen;
471 int onePos = -1;
472
473 for (int i = padStart; i < EM.length; i++) {
474 int value = EM[i];
475 if (onePos == -1) {
476 if (value == 0x00) {
477 // continue;
478 } else if (value == 0x01) {
479 onePos = i;
480 } else { // Anything other than {0,1} is bad.
481 bp = true;
482 }
483 }
484 }
485
486 // We either ran off the rails or found something other than 0/1.
487 if (onePos == -1) {
488 bp = true;
489 onePos = EM.length - 1; // Don't inadvertently return any data.
490 }
491
492 int mStart = onePos + 1;
493
494 // copy useless padding array for a constant-time method
495 byte [] tmp = new byte[mStart - padStart];
496 System.arraycopy(EM, padStart, tmp, 0, tmp.length);
497
498 byte [] m = new byte[EM.length - mStart];
499 System.arraycopy(EM, mStart, m, 0, m.length);
500
501 BadPaddingException bpe = new BadPaddingException("Decryption error");
502
503 if (bp) {
504 throw bpe;
505 } else {
506 return m;
507 }
508 }
509
510 /**
511 * Compute MGF1 using mgfMD as the message digest.
512 * Note that we combine MGF1 with the XOR operation to reduce data
513 * copying.
514 *
515 * We generate maskLen bytes of MGF1 from the seed and XOR it into
516 * out[] starting at outOfs;
517 */
518 private void mgf1(byte[] seed, int seedOfs, int seedLen,
519 byte[] out, int outOfs, int maskLen) throws BadPaddingException {
520 byte[] C = new byte[4]; // 32 bit counter
521 byte[] digest = new byte[mgfMd.getDigestLength()];
522 while (maskLen > 0) {
523 mgfMd.update(seed, seedOfs, seedLen);
524 mgfMd.update(C);
525 try {
526 mgfMd.digest(digest, 0, digest.length);
527 } catch (DigestException e) {
528 // should never happen
529 throw new BadPaddingException(e.toString());
530 }
531 for (int i = 0; (i < digest.length) && (maskLen > 0); maskLen--) {
532 out[outOfs++] ^= digest[i++];
533 }
534 if (maskLen > 0) {
535 // increment counter
536 for (int i = C.length - 1; (++C[i] == 0) && (i > 0); i--) {
537 // empty
538 }
539 }
540 }
541 }
542 }