How often does RSA-OAEP have a leading zero?

Question

We are working with a third party vendor who is very tight lipped about their security protocols, and one of our customers who used this vendor's products is claiming that approximately one in every 250 times they initialize the system, it generates a key file that is 127 bits instead of 128, and gets rejected. They believe that when the key has a leading zero, that zero is dropped, resulting in a key that is too short and is rejected by the system. My understanding is that in the final step of RSA-OAEP encryption, the key is left-padded with zeroes. I'm not even sure they're using OAEP. (Personally, I think if they were really concerned about security they'd be less worried about hiding their implementation details and more worried about only using a 128 bit key, but the attack surface for this system is very, very small.)

I don't follow all of the math leading up to that step, but how often is the result of the modular exponentiation step exactly the desired number of bits? My expectation is that if it were an issue with dropping leading zeroes, that the error would occur much more often than 1 in ~250 (which I assume is 1 in 256, since most of the process is handled in octet strings).

Edit: I did find clarification that there is an issue in the documentation we received and it is 128 bytes.

Answer 1

Your description of the protocol is rather confused. You seem to jump between a key and an encryption output. It isn't clear whether you're worried about the key generation process, or an encryption operation that happens with this key.

I assume that you're talking about RSA with a 128-byte key, not 128-bit — 128 bits was already insecure when RSA was invented, whereas 1024 bits (128 bytes) is still publicly unbroken but worryingly small nonetheless and deprecated by all major key size recommendations.

An n-bit RSA key (where n is a multiple of 8, which is almost always the case in practice) should usually have a most significant bit that's set, i.e. a most significant byte that's larger than 128. Some systems generate a key that's actually one bit short because they multiply two n/2-bit primes and the result can be anywhere between $2^{2\lfloor (n-1)/2\rfloor}$ and $2^{2\lceil (n-1)/2\rceil}$; that's acceptable, and results in a most significant byte that's between 64 and 128. If the key is supposedly n-bit but is sometimes a whole byte short (8 bits short), that indicates something wrong about the generation process.

RSA-OAEP applies the RSA exponentiation operation to a number which, when written out with the most significant byte first, has 0 as the first byte value and every other byte xor-masked by a pseudorandom string. A xor mask by a pseudorandom string is itself pseudorandom. That is, the number looks like this in hexadecimal: 00rrrrrr…rr where the r digits are pseudorandom. This is only an intermediate value however, so it isn't clear to me why it would be relevant.

The output of RSA encryption is a number modulo $n$ where $n$ is the RSA modulus. That number can be anywhere between $1$ and $n$ in a way that's indistinguishable from uniformly random (or at least pretty close) if you don't have the private key. That means that the most significant byte is biased (in particular, larger values are impossible), and it's 0 more than 1/256 of the time.