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

Jack Lloyd lloyd at randombit.net
Tue Oct 13 13:04:50 EDT 2009


On Tue, Oct 13, 2009 at 04:23:59PM +0100, Paul Clark wrote:

> 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?

Yes, on the decoding side leading zeros will get stripped from an RSA
operation. (I actually can't claim that makes any sense, but it works;
a lot of this code is 5+ years old and was written when I didn't
really know what I was doing (not that I necessarily know what I'm
doing now, of coures).

[...]
> 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.

Yup - looking at the OpenSSL code, it seems to assume that the
algorithm id was already prepended to the hash before calling the RSA
function; it just adds the outer 01FFFF... block.

> 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!

I think your interpretation of the situation is correct.

> 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]*?)

Thanks for mentioning - should be fixed in the next release by only
looking at files named *.txt in those directories, which shouldn't
cause any confusion with CVS droppings or suchlike.

> 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?

Probably so. The most likely culprit being the *Vector
types. Unfortunately it's hard to profile code size and I haven't had
much luck in my attempts to reduce it so far.

> 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?

Ah right I had missed that you are using the thread safe option.

x931_rng isn't necessary unless you really want it - it is only used
as a paranoid PRNG post-processor (basically, it takes the output of
the 'real' PRNG and runs it through the stock X9.31 PRNG (except using
AES instead of 3DES, which I believe is allowed by at least NIST, if
not the ANSI standard - not sure about them), so even if it turns out
that the HMAC_RNG or Randpool implementations are thoroughly broken
somehow, the PRNG will still produce cryptographically random outputs.

You'll need at least hmac_rng and auto_rng, I think - the dependencies
of those should be loaded automatically.

-Jack



More information about the botan-devel mailing list