RSA with OAEP fails nondeterministically

[peter-meemo]

Unless I am screwing up implementation (possible), it seems like RSA/OAEP fails some small fraction of the time. (I am guessing that there may be a problem with the random oracle inside OAEP?)

Unit test:

import 'dart:typed_data';
import 'dart:math';

import 'package:collection/collection.dart';
import 'package:test/test.dart';

import 'package:pointycastle/pointycastle.dart';

const _rsaPublicExponent = 65537;
const _rsaKeySize = 2048;
const _rsaCertainty = 12;

Uint8List _randomBytes(int numBytes) {
  final random = Random.secure();
  final bytes = Uint8List(numBytes);
  for (int i = 0; i < numBytes; i++) {
    bytes[i] = random.nextInt(255);
  }
  return bytes;
}

SecureRandom _secureRandom() {
  final secureRandom = SecureRandom('Fortuna');
  final seeds = _randomBytes(32);
  secureRandom.seed(KeyParameter(seeds));
  return secureRandom;
}

void main() {
  test('repeated RSA.', () {
    final rsapars = RSAKeyGeneratorParameters(
        BigInt.from(_rsaPublicExponent), _rsaKeySize, _rsaCertainty);
    final secureRandom = _secureRandom();

    final params = ParametersWithRandom(rsapars, secureRandom);
    final keyGenerator = KeyGenerator('RSA')..init(params);

    final keyPair = keyGenerator.generateKeyPair();

    final publicKeyParameter = PublicKeyParameter<RSAPublicKey>(keyPair.publicKey);
    final privateKeyParameter = PrivateKeyParameter<RSAPrivateKey>(keyPair.privateKey);

    final cipher = AsymmetricBlockCipher('RSA/OAEP');
    final inputData = _randomBytes(32);

    for (int i = 0; i < 10000; i++) {
      print('Round $i');
      cipher..reset()..init(true, publicKeyParameter);
      final encData = cipher.process(inputData);
      cipher..reset()..init(false, privateKeyParameter);
      final decData = cipher.process(encData);
      assert(ListEquality().equals(inputData, decData));
    }
  });
}

This does not fail if the cipher is defined as 'RSA' or 'RSA/PKCS1', only for 'RSA/OAEP'.

[peter-meemo]

(Of note: this also fails if we create new AsymmetricBlockCipher objects for each encryption/decryption pass, so it is not related to some persistent state inside those.)

[duncanhoggan]

@peter-fingo Please feel welcome to scrutinise the implementation, it's based off the bouncy castle implementation but I may have missed something. Also the test coverage around OAEP needs attention. Any contribution is welcome, I will investigate too when I have a chance.

[hoylen]

Since I needed to do a deep-dive into understanding how to use OAEP and what the specifications said about it, I thought I'll have a quick look at this issue...

Yes, there is a bug in the Pointy Castle code.

Short answer: I'll submit a pull request for the fix.

Though I suggest using processBlock instead of process to do the encryption, since process with throw an exception if the data it is passed is too big. And what is "too big" depends on the bit-length of the key used. So unless you can guarantee the size of the keys and the size of the data, code using process could fail. Or at least check the data against the inputBlockSize and failing in your code.

Long answer: the bug was non-deterministic because it depended on what random seed value was used in the encoding operation.

The OAEP encryption operation essentially builds up a block of data (from the input data and a randomly generated seed) and encrypting that block using the underlying RSA algorithm. The problem occurs when the block of data starts with one or more zero bytes (0x00). Since the seed is randomly generated, that would happen randomly with a probability of 1 in 256.

Encryption involves interpreting the bytes of the block as a huge integer. Decryption results in a huge integer that is then represented as a sequence of bytes.

When the block starts with 0x00, the huge integer does not need the leading zero bytes to represent it. Therefore, the RSA decryption returns a shorter sequence of bytes (the same bytes and in the original block, but without any leading zero bytes). And therefore, is different to what is expected.

As an illustration, if the original block consisted of these bytes [ 0x00, 0x01, 0x02 ], the decryption produced [ 0x01, 0x02 ] which does not match the original block.

From a specification point of view, the decryption operation in section 7.1.2 of RFC 2437 uses the I2OSP (integer to octet string primitive) to convert the huge integer into bytes. That I2OSP operation takes the number and an intended length -- the result is left-padded with zero bytes to make sure the block produced is that long.

The Bouncy Castle OAEPEncoding.java handles this situation by copying the bytes to a bigger block when it is necessary (lines 220-234). This is what lines 169-175 from v1.0.2 of Pointy Castle's oaep.dart is supposed to be doing, but doesn't.

[hoylen]

The fix has been merged into the new repository at https://github.com/bcgit/pc-dart via Pull Request https://github.com/bcgit/pc-dart/pull/11.

[stevenroose]

Thanks!