[GNU Crypto] how to deal with weak keys. was: Documentation

[Raif S. Naffah]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: RIPEMD160

On Wed, 28 May 2003 05:51 am, Casey Marshall wrote:
> On Tue, May 27, 2003 at 12:28:42PM +0200, Marcel Winandy wrote:
> > > the issue is effectively whether to include in the makeKey(...)
> > > method implementations checks for weak keys (and eventually other
> > > massaging functions required by the algorithm) and bailing out
> > > with this new exception if the key material is found to be in
> > > violation of certain pre-conditions; e.g. weak key.  or, do not
> > > apply those checks relying instead on the user alertness for
> > > ensuring the quality of the input key material.
> > >
> > > i'd be also interested in hearing others' opinion on the subject.
> >
> > The point is whether you want to provide a library with raw
> > algorithms or to provide a secure cryptography library. In the
> > former case it is up to the user to decide what is a weak key and
> > how to treat with it. But in the latter case (and I hope that is
> > what you want) the library has to assure that weak keys are
> > rejected or at least the user is being warned.
>
> This sounds more like a documentation issue -- it should suffice to
> mention weak keys and ways of testing them (such as DES.isWeak()).
> Throwing an exception is probably not the best behavior in this case.

this is a relative issue.  what some consider as acceptable, others 
dont.  which is fair enough.


> > The last thing is very important because there may be users who are
> > not very familiar with cryptography and possibly don't know about
> > weak keys or how they defined and what consequences they will have.
>
> I'm of the opinion that if someone is using GNU Crypto to build a
> crypto application they *should* know a thing or two about
> cryptography.
>
> If they don't, then it's to their own peril.

again, as Marcel mentioned it's a responsibility issue.  of course 
disallowing the use of weak keys, does not in itself protect a user 
from leaving their (strong) key exposed or vulnerable to theft, etc.  
the point is whether GNU Crypto should (or not) disallow the use of 
such keys, since we _already_ know that the use of such keys 
compromises the ciphertext.


> > The whole thing is about responsibility: who shall make secure
> > cryptography - the application programmer or the crypto library? I
> > suggest the name of library gives us a hint to answer this
> > question...
>
> Going to the lengths of explicitly disallowing weak keys from ever
> entering the system goes too far; it limits the flexibility of the
> library for something that will probably happen once in a million
> years. If it ever happens that the probability of generating weak
> keys *is* a significant risk, then it's more likely that the cipher
> is flawed.
>
> This is also mostly academic since the cipher in GNU Crypto with the
> most serious weak key issues is DES, and it should not be considered
> secure today anyway.

yes and no.  it sure is academic in the case of DES, but the same issue 
occurs with (a) triple-des, and (b) in possibly current and future 
ciphers.  who knows if tomorrow some researcher will not discover a 
weak key pattern for the AES?  what do we do then?

the opportunity we have here --which is (partly) the raison d'etre of 
GNU Crypto-- is to experiment with ideas and concepts about security 
and its implementations.  if we can come up with a good pattern, or 
lesson, that we can include in the code, then our library would become 
(more) attractive than others.  a good example IMO is what we've done 
with the self-testing.  this is another opportunity of setting a 
precedent.


> My vote is to not check for weak keys. Any user-level applications we
> eventually write for GNU Crypto most definitely *should* check for
> weak keys when they are generated, but I don't think this belongs in
> the library proper.

i hear you.


later, on Wed, 28 May 2003 04:28 am, baz wrote:
> Hello,
>
> OK, my last word on the subject of weak keys:
>
> gnu-crypto is a library and therefore should be as flexible and easy
> to use as possible. When writing a library it's not always possible
> to envisage how that library is going to be used, but one thing is
> for sure: whenever a constraint is added to any piece of software
> then somebody somewhere will no longer be able to use it.
>
> Allowing the use of weak keys does not make the cryptology the
> library provides weak. That is up to the application writer. That
> person may well be someone investigating how to crack cipher text
> encrypted with a weak key. What you are saying by refusing to allow
> weak keys is that he/she won't be able to use this library any more.
>
> Maybe a better example is this: Not everybody will be using this
> library. In the real world, organisations pass data around. If my
> organisation had me write something to decrypt data sent to us and I
> used the gnu-crypto library they'd be happy as it is good and fast.
> However, they will not be happy when one day some data arrives that
> can't be decrypted because the third party used a weak key. I can
> imagine the conversation I'd be having with my boss: "What do you
> mean you can't decrypt it. That key was used to encrypt it. It should
> work for decrypting it too. And after all, it's weak anyway!!"

point taken.


> Do you get where I'm coming from? There is no substitute for good
> documentation as it is this which provides the contract between what
> the library can do and the person using it. Anyone concerned about
> this knows about the problem. Marcel, Raif and myself worry about
> strong encryption so we would write applications that bothered to
> check for weak keys. On the other hand, a student experimenting might
> actually want to use weak keys. After all, as Marcel said, the
> library should provide something for the user regarding weak keys,
> which it does by exposing some methods to call for checking these
> things.
>
> From past experience, I know that somebody would get bitten. After
> all a weak key is not an invalid key. The algorithm works fine as
> data goes in one end and out the other quite happily.
>
> I'll shut up now.


ok.  i see the benefit of allowing even weak keys to go through the 
implementation.  i double checked all the FIPS publications relevant to 
DES, and couldnt find even a warning about weak keys!

here is what i propose; it's similar to what we already do in the PRNG 
class: use of conditional compilation.

* add in each cipher implementation which is known to exhibit weak, or 
semi-weak keys, a private static final boolean CHECK_WEAK_KEYS with a 
default value.  in the makeKey() method we add the code to check for 
weak keys conditioned by the value of CHECK_WEAK_KEYS.

* in the code, distinguish the case of weak keys with a new exception 
that is a subclass of InvalidKeyException.  this way the code will 
remain backward compatible.

* add a warning in the documentation, incl. the README about the set 
default for CHECK_WEAK_KEYS, and how the user can change it to get the 
desired effect if it is not set to the appropriate value.


how does this sound?


- -- 
cheers;
rsn
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.7 (GNU/Linux)
Comment: Que du magnifique

iD8DBQE+1I97+e1AKnsTRiERA2bqAJ9F1VBBwV0ruNTj95ESei8WWW/bmgCg1bKt
eokypfocpIBkd8LPBRDUxDM=
=xBGG
-----END PGP SIGNATURE-----