Re: XML signature HMAC truncation authentication bypass

2009-07-19 Thread Peter Gutmann
Leandro Meiners quotes:

For example, by specifying an HMACOutputLength of 1, only one bit of the
signature is verified. This can allow an attacker to forge an XML signature
that will be accepted as valid.

This excessive generality is a serious problem in way too many crypto specs, 
and implementations of security protocols.  For example PKCS #11 allows you to 
leak keys out of cryptographic hardware by specifying the use of a 1-bit key 
derivation function, allowing you to guess an entire key one bit at a time 
(fortunately few, if any, implementations actually support this).  In the PKI 
world, virtually no spec requires sensible limits on anything (some years ago 
I brought a CA to a halt by specifying a huge salt and large iteration count 
for the challenge-response protocol they used to authenticate certificate 
issues.  Then I repeated it to make sure it wasn't just a coincidence the 
first time :-).  PGP Desktop 9 uses as its default an iteration count of four 
million (!!) for its password hashing, which looks like a DoS to anything that 
does sanity-checking of input.  Netscape (and obviously this test was done 
some years ago) will happily accept a certificate with a 1MB MPEG of a cat in 
the X.500 DN, but then become what could mildly be described as unresponsive 
once it's stored it in its cert.database.  The SSH oracle attack of a few 
months ago was helped by the fact that the length field wasn't constrained to 
sensible values.  This list goes on and on, it's scary just how vulnerable a 
lot of security software is to anything that can drop a slightly unexpected 
value into a data field.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: work factor calculation for brute-forcing crypto

2009-07-19 Thread David Wagner
Assume for a moment that we have a random number generator which is
non-uniform, and we are using it to generate a key.

What I'd like to do is characterize the work factor involved in
brute-force search of the key space, assuming that the adversary
has knowledge of the characteristics of the random number generator?

You may want to use the guessing entropy.
I've written about it before here: 

Christian Cachin's thesis is a wonderful introduction to entropy
measures, including the guessing entropy.

By the way, I'll make the obvious recommendation: Try to avoid
using a non-uniform random number generator to generate a cryptographic
key, if you can.

The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: 112-bit prime ECDLP solved

2009-07-19 Thread Zooko Wilcox-O'Hearn
By the way, we've recently been planning our next crypto-capabilities  
design for the TahoeLAFS secure distributed filesystem.  This  
involves deciding whether a 192-bit elliptic curve public key is  
strong enough, as well as subtler and more unusual issues involving  
embedding keys directly into filehandles or URLS, multiple-targets  
attacks, and a novel public key scheme that I invented (and that  
therefore I think we shouldn't use):

Your comments would be appreciated!  I've added and to the list of  
addresses that can post to tahoe-dev without being subscribed.



The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

why hyperelliptic curves?

2009-07-19 Thread Zooko Wilcox-O'Hearn
Oh, and by the way the way that TahoeLAFS uses public key  
cryptography highlights some of the weaknesses of current public key  
techniques and some of the strengths of possible future techniques  
such as hyperelliptic curves.  (I know that Tanja Lange has done a  
lot of work on those.)

TahoeLAFS generates a unique public-private key pair for each mutable  
file and each directory.  (Immutable files don't use public key  
cryptography at all -- they are secured solely with a stream cipher  
and secure hashes.)  The file handle or capability to a mutable  
file or directory contains the actual public key (if it is a read- 
only capability) or the actual private key (if it is a read-write  
capability).  Therefore some of our most important measures of  
performance are public key size and keypair generation time.   
Unfortunately, we blundered into using one of the worst possible  
public key signature algorithms for such requirements: RSA!  Our  
current project is replacing RSA with ECDSA.  TahoeLAFS v2.0 will  
support ECDSA-based capabilities (in addition to RSA-based ones for  
backward compatibility).

TahoeLAFS also requires more than two levels of privilege.  With  
traditional public/private keys there are exactly two levels: you  
either know the private key or you don't.  We need to have an  
intermediate level of privilege -- someone who doesn't know the  
private key but who does know something that not everyone knows.   
(Everyone knows the public key.)  We use these three levels of  
privilege to create read-write capabilities, read-only capabilities  
and verify capabilities.   (A verify capability gives the ability to  
check integrity of the ciphertext, which everyone has, because  
everyone knows the public key).  If this doesn't make sense to you  
then see if my longer explanation in lafs.pdf makes any more sense.

Anyway, if it is true that hyperelliptic curves have a security level  
commensurate with the number of bits in the public key, then  
hyperelliptic curves with semi-private keys would be the ideal public  
key crypto signature scheme for TahoeLAFS.  Unfortunately, semi- 
private keys aren't proven secure nor properly peer-reviewed, and  
hyperelliptic curves aren't well implemented or widely appreciated.   
Hopefully someday TahoeLAFS v3.0 will support semi-private- 
hyperelliptic-curve-based capabilities (in addition to RSA and ECDSA  
for backward compatibility).


Zooko Wilcox-O'Hearn

P.S.  Oh, I told a lie in the interests of brevity when I said that  
file handles contain actual public keys or actual private keys.  RSA  
keys are way too big for that.  So instead we go through interesting  
contortions to make a surrogate value which can be used to check  
the correctness of the RSA key (i.e. the surrogate value is derived  
from the RSA key by secure hashing) as well as can be used to control  
access to the RSA key (the RSA key is encrypted with a stream cipher  
using the surrogate value as the symmetric encryption key).  The  
surrogate value therefore offers the same integrity and access  
control properties as the RSA key itself (when the user also has  
access to the encrypted RSA key itself), but it is sufficiently short  
to embed directly into the file handles a.k.a. capabilities.  This  
too is explained more fully in lafs.pdf.


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to

Re: work factor calculation for brute-forcing crypto

2009-07-19 Thread David Malone
On Fri, Jul 17, 2009 at 01:37:43PM -0500, wrote:
 I'm curious if there's a way to express this calculation as a
 mathematical formula, rather than an algorithm, but right now I'm just
 blanking on how I could do it.

This has been dubbed the guesswork of a distribution by some authors,
I think originating with:

John O. Pliam. The disparity between work and entropy in
February 1999

It turns out that its asymoptic behaviour is bit like that of Renyi
entropy, see:

E. Arikan. An inequality on guessing and its application
to sequential decoding. IEEE Transactions on Information
Theory, 42:99105, Janurary 1996.

I did an explanitory writeup of this with some experiments at:


The Cryptography Mailing List
Unsubscribe by sending unsubscribe cryptography to