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

Jack Lloyd lloyd at randombit.net
Tue Oct 13 08:12:56 EDT 2009


On Tue, Oct 13, 2009 at 10:06:47AM +0100, Paul Clark wrote:
> - I downloaded 1.8.7 but it generates libbotan-1.8.2.so

This is for link compatability with previous versions; it allows
distros shipping botan shared libraries like Debian and Fedora to
upgrade with bug fixes without breaking previously shipped
applications. 1.8.2 just happens to be the version number where the
1.8 ABI was frozen for the distros.

> - The examples of PKCS8::load_key in tutorial.pdf sec. 5.2.2 and api.pdf 
> sec. 3.7.2 don't include the RNG parameter (actually, why does a loader 
> need an RNG anyway?)

Thanks for mentioning that, fixed.

When private key material is loaded botan performs some probablistic
tests on the input (such as the Miller-Rabin compositness test), for
which an rng is needed. In older versions there was a single global
PRNG that was used but this switched to passing a PRNG object where
needed in 1.8.

> I have this working using sign() for 'encrypt' and verify() for 
> 'decrypt', but the output of the verify() is still padded to 127 bytes 
> when of course the SHA1 should only be 20.  It looks like the last 20 
> bytes match the original, so for now I'm just comparing those, but this 
> seems rather unsatisfactory.  Is there an operation to remove the 
> padding - essentially, to recover the original message?

The lowest level operations like this need to return their entire
output (in the case of RSA, that's a number about the size of the
modulus) because it doesn't know what (if any) padding scheme it is
being used with - the presence or absence of the zeros might be very
important, depending on the padding scheme in use.

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.

 - Actually: you should verify that all the leading bits are in fact
   zeros; if you don't, it's quite plausible that someone could forge
   a signature by computing a signature that had the low 20 bytes
   being the correct SHA-1 hash and the higher bits being random
   garbage when checked against the public key. (I can't off the top
   of my head think of a technique for generating such a signature,
   but I'd bet a cup of coffee that it's been described somewhere in
   the literature).

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());

In sign_message, an rng is required by the call, but in the case where
you know that a RNG is not actually needed (like for EMSA1, which is
not a probabilistic method), you can use a Null_RNG instead of going
to the (computational) expense of creating an AutoSeeded_RNG that
won't actually be used.

Under the covers, EMSA1 is basically doing the same memcmp that you
are doing (plus checking for zeros and a few other sanity checks); the
advantage being of course that it pushes the complexity down in the
the library instead of being in your application, and makes it easy to
swap out for another safer padding scheme like PSS in the future.

> One last question:  On linking statically with libbotan.a my application 
> size increases by about 2MB...  The above is all I'm currently using, so 
> that seems a bit extreme.  Is there an easy way to shrink the library to 
> just include the SHA1/RSA operations at build time

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

If you need to do key generation, you'll need to add
'sha2,hmac_rng,auto_rng,dev_random,eme1,emsa4' to the --enable-modules
invocation. (EME1 and EMSA4 because they are hardcoded into the RSA
keygen selftest - something I hadn't considered as a problem until I
tried this).

On my Linux/x86-64 box, doing this plus changing the Makefile to
compile for size (-Os), a little application that does a keygen + sig
+ verify ran to about 440 KiB, which is still not great size wise but
20% of the original size is something.

> or (better, in case we want to use it in other applications)
> initialise it in such a way that it doesn't pull in every possible
> algorithm 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.

-Jack



More information about the botan-devel mailing list