[Botan-devel] Thanks, minor issues & questions on RSA sign/verify padding, binary size

Paul Clark paul at packetship.com
Tue Oct 13 11:23:59 EDT 2009


Jack Lloyd wrote:

(Many thanks for your amazingly fast and comprehensive reply!)

[Removing padding from verify result]
> If you check the padding bytes at the start, you'll see they are all
> zeros; the return value is in fact the SHA-1 hash, expressed as a 1024
> bit integer (well, 1024-8 bit, actually); since the SHA-1 hash is only
> 160 bits long, of course, all but the low 20 bytes are zeros.
...
> If you use the somewhat higher level operations in pubkey.h and
> look_pk.h, you can specify using EMSA1(SHA-1) as the padding scheme to
> get a compatible signature. Something like:
>
>  Null_RNG null_rng;
>  std::auto_ptr<PK_Signer> signer(get_pk_signer(my_priv_rsa_key, "EMSA1(SHA-1)"));
>  SecureVector<byte> signature =
>     signer->sign_message((const Botan::byte *)text.data(), text.size(), null_rng);
>
> and
>
>   std::auto_ptr<PK_Verifier> verifier(get_pk_verifier(my_pub_rsa_key, "EMSA1(SHA-1)"));
>   bool signature_ok =
>     verifier->verify_message((const Botan::byte *)text.data(), text.size(),
>                              (const Botan::byte *)sig.data(), sig.size());

OK, I tried these, and got some interesting results...

1) The EMSA1(SHA-1) operations are of course fine between themselves.

2) The EMSA1(SHA-1) signature is the same as the lower-level SHA1+RSA 
one I did before with Botan (this surprised me, actually, because I had 
expected some randomness and a change of padding, but I do now 
understand why - EMSA1 is predictable, and I guess is effectively the 
default because zero-padding is going to happen for BigInt maths anyway).

3) Our old OpenSSL verifier doesn't like the Botan EMSA1(SHA1) signature

4) The Botan EMSA1(SHA1) verifier doesn't like the signature from the 
old OpenSSL signer

5) The previous Botan low-level SHA1+RSA verifier *will* accept the 
signature from the old OpenSSL signer, if I arbitrarily bobbit the 
padding bits as previously described.

6) The old OpenSSL verifier *won't* accept the signature from the 
low-level Botan SHA1+RSA signer, contrary to what I previously thought 
(I had tested (5) and stupidly assumed it would be symmetric!)

So it looks like the difference between OpenSSL and Botan is in the 
padding...

Here is the binary output of the RSA_PublicKey::verify() output from an 
OpenSSL-created signature:

0000: 01ffffff ffffffff ffffffff ffffffff | ................
0010: ffffffff ffffffff ffffffff ffffffff | ................
0020: ffffffff ffffffff ffffffff ffffffff | ................
0030: ffffffff ffffffff ffffffff ffffffff | ................
0040: ffffffff ffffffff ffffffff ffffffff | ................
0050: ffffffff ffffffff ffffffff ffffffff | ................
0060: ffffffff ffffffff ffff0048 eb9f1547 | ...........H...G
0070: e2512274 a8d501b8 0b390397 a3cee2 | .Q"t.....9.....

Here's the same from a Botan EMSA1(SHA1) signature of the same document:

0000: 48eb9f15 47e25122 74a8d501 b80b3903 | H...G.Q"t.....9.
0010: 97a3cee2 | ....

Note that when it's an EMSA1(SHA1) signature, RSA_PublicKey::verify() 
seems to 'unpad' it itself. Is that expected? I guess it's just 
suppressing leading zeros?

So it looks like the padding we were using in OpenSSL wasn't EMSA1... 
Indeed looking at the old code, we requested RSA_PKCS1_PADDING (which 
should have been a clue, if I had understood the nomenclature!)... 
Having worked out that in Botan this is EMSA3, I tried "EMSA3(SHA1)" 
instead of "EMSA1(SHA1)". But alas, still no joy... Here's the binary 
low-level verify() output now:

0000: 01ffffff ffffffff ffffffff ffffffff | ................
0010: ffffffff ffffffff ffffffff ffffffff | ................
0020: ffffffff ffffffff ffffffff ffffffff | ................
0030: ffffffff ffffffff ffffffff ffffffff | ................
0040: ffffffff ffffffff ffffffff ffffffff | ................
0050: ffffffff ffffffff ffffff00 30213009 | ............0!0.
0060: 06052b0e 03021a05 00041448 eb9f1547 | ..+........H...G
0070: e2512274 a8d501b8 0b390397 a3cee2 | .Q"t.....9.....

Again, the last 20 bytes are the same, but we seem to have gained 
another 15 bytes, which from the code I see (as through a glass, darkly) 
is the SHA-160 PKCS#1 'hash ID'. It looks like the OpenSSL version 
doesn't have this - but I got as far as actually reading PKCS#1 section 
9.2 (EMSA-PKCS1-v1_5) and it looks like this 'AlgorithmIdentifier' is 
mandatory.

Here's my guess: because we naughtily did an 'encrypt' operation with 
the private key in OpenSSL (RSA_private_encrypt(..., RSA_PKCS1_PADDING) 
- OpenSSL allows it!) it doesn't have a hash identifier so it just 
leaves it out, which means Botan's EMSA3 rejects it. Conversely, OpenSSL 
RSA_public_decrypt() doesn't like Botan's EMSA3 which does have the hash 
identifier. Put another way, OpenSSL really shouldn't provide 
RSA_private_encrypt/RSA_public_decrypt() at all, it's a trap for the 
unwary...

If this is right, it looks like I might have to revert to my low-level 
RSA operations and implement the (broken? hash-identifier-less) PKCS#1 
padding myself - no big deal, but it would be nice to know if I've 
understood it roughly right. I do of course agree that if it weren't for 
the legacy problem, we should be doing it properly with EMSA-PSS!

[Reducing library size]
> Yes, this is pretty easy if you're using the Python build script in
> 1.8.7:
>
> ./configure.py --no-autoload --enable-modules=rsa,sha1,emsa1

OK, that's great. Actually I was using the configure.pl script because 
the configure.py failed on first attempt - this lead me to work out why. 
It's because I've imported Botan into our CVS and there are CVS 
directories in the build-data/arch (etc.) directories. I guess the 
script is wildcarding the directory and gets confused by the CVS subdir. 
For now I just deleted the CVS dirs and it works fine, but it would be 
good if it could ignore them (maybe wildcard on [a-z]*?)

With the library cut down like this Botan is adding about 1MB to the 
app. Much better than 2MB, but still quite a lot. But I can live with 
that, this isn't really a space-sensitive application, I was just 
surprised... There doesn't seem to be enough code in the stripped down 
library to fill it - maybe there's a lot of template expansion going on?

Unfortunately it won't run like this! First it complained about no 
thread mutex, so I added back 'pthread' - thats fine. Now it's 
complaining that "No usable RNG found enabled in build". I tried adding 
'dev_random' and 'x931_rng' but no luck. Which are the minimum modules 
you need to use AutoSeededRNG?

[Reducing size of a fully configured library at load time]
> This is unfortunately significantly harder to do; you could do it by
> writing a new Engine class which just implemented the algorithms you
> wanted, but this would be a good bit of work, fragile, and you'd have
> to directly patch the sources to hook it in. :/ Let me know if you
> want to go this route and I'll try to help out, but I really couldn't
> recommend it much.

OK, fair enough. We could always build variants of the library if it 
came to it, but the chances are we'll only need the basic SHA1/RSA/DES 
type things anyway.

Many thanks again

Paul




More information about the botan-devel mailing list