Cryptography as a component of security

Jerrold Leichter jerrold.leichter at
Thu Nov 13 10:13:30 EST 2003

| I listened to yet another talk on computer security, which
| incorporated security.  It got me to thinking two things:
|   o Pseudo-random implies pseudo security.
| If you're re-keying by running the old key through a pseudo-random
| function without adding any new entropy, then you're not re-keying at
| all.
That's not true.  Consider a stream cipher:  It "stretches" your original key
into a much longer stream.  By your argument, as soon as there is sufficient
generated stream to uniquely determine the key, no additional entropy is being
introduced, so all the rest is pseudo-security!  But in fact the unicity point
must be reached very quickly, or the generated stream would be too *indepen-
dent* of the key, and an attacker could guess most of the stream without even
knowing the key.

Or consider the following construct:  Suppose we have two encryption functions
E1 and E2, E1 is very fast, but breakable - there is an attack of concern to
us that becomes viable after an attacker has seen (or been able to partially
specify, if you want to think about chosen plaintext attacks) N plaintext/
ciphertext pairs.  E2 is slow, but we consider it to be secure against the
attacks of concern.  To encrypt the stream of plaintext P_i to ciphertext C_i,

	K <- Master key
	Choose n < N
	for i = 0, 1, ...
		// Begin new segment
		SK_i <- E2(K,i)
		for j = 0 .. n-1
			C_{n*i + j} = E1(SK_i,P_{n*i + j})

Even if an attacker breaks into a number of segments and gets those S_i's
(which, BTW, is an assumption about the form of the attack:  Some attacks
reveal the plaintext without revealing the key), what he's left with is a set
of plaintext/ciphertext pairs with which he now has to attack E2 - which is
assumed to be difficult.  (Even worse for the attacker, even if he could mount
a chosen ciphertext attack against E1, he has no control over the plaintexts
fed into E2.)

Note that we assumed E2 was actually very strong.  But even if we assume E2
has the same effective strength as E1 - it can be broken after seeing N
plaintext/ciphertext pairs - then the security guarantees (such as they are;
one would have to be more precise about the nature of "attackable after N
pairs are seen" vulnerability) are pretty much the same until about N^2
plaintext/ciphertext pairs have been sent.
							-- Jerry

The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at

More information about the cryptography mailing list