How often does RSA-OAEP have a leading zero?

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.

-
Did you mean bytes where you wrote bits? A 128-bit RSA key would not bring any security, a 1024-bit key is as yet unbroken but should be at least scheduled for replacement. –  Gilles Jul 1 at 20:32
If your vendor is unwilling to describe precisely what their crypto is doing, that is a strong indication to move to another vendor who is more transparent. The details on how to do strong crypto are not trade secrets; if they're hiding something, the likelihood is that they're hiding how bad their implementation actually is. –  poncho Jul 1 at 20:37
This is unfortunately not an option. We don't actually specify the vendors our customers use. In fact, what I find here won't even change anything, it's just for my edification. –  TBridges42 Jul 1 at 20:52
You don't need to tell me their implementation is crappy. But strictly speaking it's also not necessary. The device in question is physically secured and has no network connectivity, or really any ability to do anything of value. But it's required to be signed anyway. –  TBridges42 Jul 1 at 20:55
If this is about the most significant byte of the ciphertext being zero, it's possible. Padding affects the plaintext. –  CodesInChaos Jul 1 at 20:55

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.

-
Important note: it can also have more than 1 leading zero (2 bytes more than 1/65536 of the time, of course etc. etc.). The chance that there are more than 8 leading zero's is negligable ($2^{64}$), 16 leading zeros is next to impossible given that the encryption routine is correct. I can still remember the phrase: "OK, we've fixed the leading byte problem" pretty well - that's not enough. –  Maarten Bodewes Jul 2 at 11:02
@TBridges42 A key that's one bit short would have the expected number of bytes, yes. But it's unclear to me whether the file with the problematic length even contains a key (and if it does, what makes you sure that it's an RSA key). At that level of remove, it's difficult to know what the vendor did wrong, what your customer is perhaps not reporting faithfully and completely, and what you might be mixing up. –  Gilles Jul 2 at 17:49
You are right both that I do not have enough information and that I'm probably mixing some things up. I gave you the answer because your answer seems clear and well explained, even though I can't reconcile it with the information I am receiving. Hopefully I'll get to read the final write-up when this is all done and that will shed some light. –  TBridges42 Jul 7 at 17:03