Subject: more comments on rijndael draft

From: Marcus Watts <[email-masked]>
Date: Sun, 16 Sep 2001 21:59:52 -0400

Following are some warmed over notes I wrote up on Ken Raeburn's
rijndael draft.  If anything is unclear, please ask me; it's entirely
possible I've left something unclear or even wrong...

There are several things I wanted to follow up on separately; I have
more thoughts on computational complexity, as well as some comparitive
data on the speed of various string to key functions.  I also have some
more general thoughts on salt types and how is is shipped back to the
client as "preauth" data.

{ I hope this is still relevant after the dust from the truely awful
incidents in Washington and NYC settle.  I believe strong cryptography
is important towards defending our nation's communications and
information infrastructure from attack, especially from
cyber-terrorists.  I also also believe that strong and unfettered
cryptography is important to guarantee our freedom and liberty from
tyranny both foreign and domestic.  I am not sure if our leaders really
understand this. }

				-Marcus Watts
				UM ITCS Umich Systems Group
=================================
Good things (about use of PBKDF2):
	non-reversible hash.
	every character significant for 1-64 character pws.
	every pw bit "cryptographically" affects every output bit
	does not rely on "computational" complexity
	does use username+realm in salt
	different crypto systems get different keys

Now some bad things:

#1 Passwords over 64 bytes (sha256) or 128 bytes (sha384, sha512)
are first compressed, so contain absolutely no more entropy than
32/48/64 random bytes.

	>> test vectors should include at least one
	pw > 64 and one > 128.  Maybe 1 exactly 64 too,
	to catch off by 64 errors.

	Better yet, modify hmac - instead of xoring key bits,
	prefix 64-127 pad bytes to ikey and postfix 64-127 pad bytes
	to okey (sufficient to pad to next 0 mod 64 keylen bound).
	This will give the same "twist" as [bck] recommend, without
	weird special cases.  Note that hmac as described in
	RFC 2104 seems primarily intended for applications where
	the key is a relatively small "random" binary byte string,
	not a long english sentence.

#2 sha384 and sha512 are the same underlying algorithm.
Most of the work done by hmac inside of pbkdf2 will see
the same data and many intermediate steps will have the
same value.  If sha384 weren't strong enough (?granted,
seems unlikely?), then it might offer an attack on someone
who could be tricked into using it instead of sha512.

	Might be worth appending the key length to
	the salt passed to PBKDF2 ?

#3 if DK is supposed to be the function krb5_derive_key in the MIT k5
library, then it actually does an encryption, and isn't just a straight
"copy" as might be suggested by the text.  This is actually good,
because it ensures each crypto system has its own separate key space
via a cryptographic mapping.  Note however this extra encryption step
loses maybe a bit worth of keyspace (because of collisions.)

	Might be better to skip the key derivation step,
	and instead append some algorithm dependent constant
	to the salt pased to PBKDF2.

#4
salt has no space betweeen realm & username.  Principals
[email-masked] and [email-masked] share the same salt, FOO.COMoo
This is a generic fault of k5, not specifically this crypto
system.

	{ Ok, so usernames are "supposed" to be all lower-case; it
	still seems unwise, and even in a newly initialized MIT k5
	realm, there are upper-case names... }

	Might be worth specifying a new salt type that interspaces NUL
	between the different components.  Or, why not just use the full
	printable principal name?

Other things to think about:

#5
sha256,sha384,sha512 generate big data.

	I originally thought these were slow too.  When I
	checked the timing against sha1, they seem to be not
	nearly so bad -- but this needs more research.

	More generally, are these checksum algorithms *really*
	necessary, and it is really necessary or desirable to include
	all the output?  For unkeyed hashing, all the digest data is
	needed, because of the birthday problem.  For keyed hashing,
	truncation is useful, because the birthday problem can't
	generally be exploited, and truncation removes information
	useful to the attacker.  Since the checksum is encrypted and
	because a confounder is used, I think this looks much more like
	the keyed hashing case, or perhaps an even further extreme.
	So, I don't believe the birthday problem is a problem here, and
	anyone capable of mounting a birthday problem is probably also
	capable of a much more direct approach such as construction of
	a codebook.

	My guess is that it's almost certainly not useful to have more than
	the underlying key size worth of checksum data, and probably not
	useful to have more than the underlying blocksize of checksum data.
	Even if the checksum is truncated, I suspect it need not be
	double the size to gain plenty of benefit.

	This should be checked with a real cryptographer, but I think,
	keysize	alg		hash bits sent
	128	sha-256		128
	192	sha-256		256 (or 128?)
	256	sha-512/384	256
	*should* have plenty of security.
	(sha-512 or sha-384; since sha-384 is really just sha-512 truncated...)

	I think a case could be made for using sha-1 for all 3,
	though I'd want to ask a lot of cryptographers first.
	This isn't worth it if sha-256 is faster than sha-2.

	For passwords, since they have to be typed in and remembered by
	humans, I think assuming they even have 64 bits of real entropy
	is optimistic, and 40 bits is probably more realistic.
	Given that, even the use of sha-1 (as suggested in PKCS #5/RFC 2898)
	is sufficient for all 3 key sizes, even given hmac's weird behavior
	with passwords > 64 bytes.  The only way to gain more security
	than that is to augment the password with some additional
	authentication mechanism, such as the use of preauth, public/private
	keys, etc.  Even so, I see little harm in using sha-256 etc, it's
	just additional code complexity.

#6
Ciphertext stealing.
	Described in [ac] p. 191.

	Ciphertext is a neat way to to encrypt with less bloat.
	Basically, given plaintext of at least 1 blocksize in size, the
	ciphertext takes up exactly the same number of bytes.  No more
	paddding or other nonsense.  Since in k5, the confounder
	will be one block in size, this means (practically)
	all blocks can be encrypted in place, and given random sized
	blocks, this would save an average of 8 bytes/block over not
	using ciphertext stealing.  This is a big win in the kdc.
	An additional "nice" thing about CTS is there's no more weirdness
	about having to send the plaintext length separately from
	the ciphertext length; now, one *is* the other.

	For best results, the crypto system ought to export a "minsize" as
	well as "blocksize", lest applications be tempted to try encrypting 1 byte.
	This is not necessary for k5 itself internally, but things like
	telnet/telnetd might like to know this.

#7
Raw crypto system type
	No numbers are reserved for a "raw" crypto system.  This
	is a system that just does cbc encryption - no confounder or
	checksum.  In the MIT k5 source, the "raw" crypto system is
	apparently only used by gssapi.  There is hard-wired logic
	there that knows about certain DES and DES3 data types, and
	maps them into the appropriate raw types, after which it does
	its own confounder and checksum logic.  There is enough logic
	elsewhere to suggest that the MIT kdc might support "raw" keys,
	although this seems highly non-wise.

	Simple solution: reserve a number for the "raw" crypto system.

	More complicated but better answer: implement a mechanism in
	the k5 crypto library to access the "raw" crypto system, and
	teach gssapi how to do this.  This might be extensible to
	telnet/telnetd, which have a similar need to do "raw" encryption.

	Alternatively, get rid of the checksum/seal logic in gssapi
	entirely, and have it use the same confounder/checksum as
	everyone else.

[bck] = Bellare, Canetti, Krawczyk. _Keying Hash Functions for Message
Authentication_. IBM June 1996.

[ac] = Schneier, _Applied Cryptography_, Wiley 1996.