Cryptography Reference
In-Depth Information
in the keystream, then the attacker may get relevant information about the
key by analyzing the keystream.
Key Weaknesses originate from different scenarios.
1. Key-Output Correlation: It is desirable that a single bit flip in the secret
key flips each bit of the keystream with probability 2 . Otherwise, secret
key bits may be recovered in a complexity less than the brute force
search.
2. Related Key: Given a known relationship between two keys should not
produce a known relationship in the keystream. Otherwise, such rela-
tionship can be used to mount what is called a related key attack.
3. IV Weakness: If the IVs are not used with proper care, they may leak
secret key information in the keystream.
2.2.3 Distinguishers
A distinguisher is an algorithm that takes as input n bits of data, which
are either taken from the keystream of a stream cipher or are completely
random data, and decides which one of these two categories the input belongs
to. If this decision is correct with a probability more than the random guess,
then we have a distinguisher of complexity n. More details on these types of
attacks (called distinguishing attacks) can be found in Chapters 6 and [187].
2.3 Hardware Stream Ciphers
Initially, stream ciphers were targeted toward hardware only. In hardware
domain, mostly LFSRs are used as linear elements and combining functions
(may be with some amount of memory) are used as nonlinear elements.
Let us first discuss bit-oriented LFSRs. An example is shown in Figure 2.1.
The recurrence relation connecting the LFSR output bit and the internal
state bits is given by s t+6 = s t+4 ⊕s t+1 ⊕s t . The corresponding connection
polynomial over GF(2) is given by x 6 + x 4 + x 1 + 1, which is a primitive
polynomial of degree 6. It is known that a primitive polynomial of degree d
provides maximum length cycle, i.e., of length 2 d −1. Such sequences are well
known as m-sequences [96].
By itself, an LFSR is not cryptographically secure, but it is a useful build-
ing block for pseudo-randomness. In the domain of communications, pseudo-
random sequences are known as p-n sequences. LFSRs find easy and e cient
implementation in hardware, using registers (Flip Flops) and simple logic
gates. Research in LFSR-based stream ciphers has incurred deep mathemati-
Search WWH ::




Custom Search