- stream ciphers process the message bit by bit (as a stream)
- typically have a (pseudo) random stream key
- combined (XOR) with plaintext bit by bit
- randomness of stream key completely destroys any statistically properties in the message
- what could be simpler!!!!
Ci = Mi XOR StreamKeyi
Conceptually a stream cipher is very simple - have a collection of random (or random looking) stream key bits, and just XOR with message (could use other combining operator, but XOR is by far the easiest and most common). If the stream key is indeed random, then no information about the message can leak through.
- probably the most famous stream cipher
- also known as the one-time pad
- invented by Vernam, working for AT&T, in 1917
- simply add bits of message to random key bits
- originally chose random number from a hat, punched onto paper tape
- then combined using XOR with a telegraph message
- is unconditionally secure provided key is truly random
Vernam Cipher Emphasize that the Vernam Cipher is the only cipher we know to be unconditionally secure BUT this only holds if the key stream is truly random and used once only! However given these limitations, it IS used for the most sensitive govt/military communications.
- in practise have some issues when using this
- most critically you need as many key bits as message
- can be difficult in practise
- eg can distribute on a mag-tape or CDROM
- have no chaining since the stream key is independent of the message
- hence need to use other methods to verify integrity
- and critically must never ever reuse a stream key
- since if have two messages encrypted by XOR with same key
- can combine these to remove effect of key giving a book cipher
C1i = M1i XOR StreamKeyi C2i = M2i XOR StreamKeyi C1i XOR C2i = M1i XOR StreamKeyi XOR M2i XOR StreamKeyi = M1i XOR M2i
Emphasise the limitations of the Vernam cipher - must distribute large quantities of key material, securely, in advance, and limit messages to the amount of key available. Also that have to use other methods to ensure integrity (need a crypto checksum or similar). And most critically, must ensure key material is never ever recycled (unlike politicians promises!!!!!)
However, WRT to key distribution, never underestimate the "bandwidth" (capacity) of a briefcase full of Exabyte tapes or CDROMs (many many GB's)!
- given the problems of key distribution for a Vernam Cipher
- suggestion is to generate a keystream from a smaller (base) key
- using some pseudo-random function
- superficially look very attractive
- in practise is extremely difficult to find a good fast pseudo-random function that is cryptographically strong
- that is, one which is unpredictable
- this is still an area of much research
Stream Cipher Using a PRG Quite a lot of effort has gone into trying to devise some way of "expanding" a small amount of key (randomness) into a much larger amount, which can then be used as the "stream key" in a Vernam-like cipher. The problem is that the "stream key" has to be not just statistically random but also cryptographical strong ie unpredictable. The usual "random number generators" on computers are statistically random, but are highly predictable (for reasons of easy implementation and reproducability of results) - good for lots of purposes, useless for crypto!!!
- when using a Pseudo-Random Generator (PRG)
- the generated stream must be:
- statistically random (like result of coin tossing)
- (know part of seq not enough)
- PRG may be controlled just by key influencing:
- next-state function (output feedback mode)
- output function (counter mode)
- PRG may be controlled both by data and key:
- output function (cipher feedback mode)
- have already seen block ciphers used as a PRG
- Output Feedback Mode uses a block cipher as a PRG
- with the cipher being the next-state function
- with a null output function
Ci = Pi XOR Oi Oi = DESK1(Oi-1) O-1 = IV
- also have a Counter Mode
- where internal state is a counter incremented by next-state function
- encrypt this value using block cipher as an output function
Ci = Pi XOR Oi Oi = DESK1(i)
Note the obvious PRG is just to use a block cipher. Can use OFB or Counter modes to generate a "stream key" that is independent of the message.
- Cipher Feedback Mode has PRG controlled by both data and key
- internal state is derived from ciphertext
- and the block cipher is used as the next state function
Ci = Pi XOR DESK1 (Ci-1) C-1 = IV
- all of these work well
- block ciphers make a strong PRG
- BUT want more efficient PRGs than these
Can use CFB mode to generate a "stream key" that depends on both key and message. All work quite well - but block ciphers are still complex and at least moderately computationally expensive. Would really like a faster, simpler PRG.
- LFSRs are often proposed for use as a PRG in stream ciphers
- comprise a shift register (of binary bits) of some length
- along with a linear feedback function of some of those bits
- each time a bit is needed, all bits are shifted one place
- the bit bumped out is the bit used as output from the LFSR
- a new bit is formed from the linear feedback function of other bits
- this form is known as the fibonacci configuration
- an alternate galois configuration is easier to code in s/w
- correctly designed they generate a very long sequence before repeating
- the generated sequence is also statistically pretty random
Linear Feedback Shift Register LFSR's are the basic building block of the majority of stream ciphers. Compare to general model: shift register is "internal state", feedback polynomial is the "next state function", bumped bit is "output function". See Schneier for details of the fibonacci vs galois configurations, which are cryptographically equivalent, but easier to implement in h/w & s/w respectively. Variations of this are what most computers use for their "random number" function.
- given a suitable sized register
- can use the key to initialise one or both of:
- the initial state (value) in the shift register
- the feedback function used
- an n-bit shift register can generate a sequence of 2n-1 bits
- need to use a primitive polynomial linear function to do this
- for greater security should use dense (not sparse) polynomials
- these are well known for common register sizes (see Number Theory lecture)
- eg. above diagram uses:
p(x) = x32+x7+x5+x3+x2+xUsually use the key to set the initial register state - if using for the feedback polynomial then have to take care to select "primitive polynomials" (or accept the loss in size & security of not using them). Briefly, "primitive polynomials" are "prime polynomials", that is, they have no factors (cannot be written as the product of) of any other polynomials except 1 and itself. Finding them is similar to finding prime numbers, easy if small, rather harder as they get larger. See Schneier for a description of how to use any "primitive polynomial" to construct an LFSR.
- LFSR's can generate a very large key
- which is why they're often used
- BUT they are insecure - statistically random but predictable
- given an
nbit shift register - just
2nbits is enough to completely predict sequence - using the well known Berlecamp-Massey algorithm for reconstructing a LFSR from a stream of bits
- any stream of bits can be approximated by an LFSR
- (at worst just one big register with the complete stream)
- in practice can often do much better
- given an
- even so, LFSRs do form the basis though of most stream ciphers
- but design attempts to hide the underlying LFSR structure
The big problem is that superficially LFSR's look good, but underneath they're fundamentally insecure. Its depressing how often this has been overlooked and how often they've been used in "so called" security products (which then get totally broken).
- Rueppel has codified stream ciphers design criteria:
- long period with no repetitions
- statistically random
- large linear complexity (based on size of equiv LFSR)
- correlation immunity (have tradeoff with linear complexity)
- confusion (output bits depend on all key bits)
- diffusion
- use of highly non-linear boolean functions
There are lots of general pointers to designing good stream ciphers, but in practise this is very difficult. Note that some of the design criteria are in conflict, have to tradeoff between them.
- general idea is to take several LFSRs of different sizes & feedback polys
- then combine them to try & obscure the underlying LFSRs by:
- combining outputs of several LFSRs using a non-linear function
- selecting the output from the LFSRs using a multiplexor
- controlling the clocking of some LFSRs by another
- only selecting some of the output bits (decimating the output)
- virtually all of these proposals have identified flaws
- incl. all current mobile phone algorithms are broken
- currently when LFSRs are used, they are re-keyed extremely often:
- fast enough so attacks will yield little info
- slow enough for a block cipher to be used to create keying information
- A5 is the stream cipher used to encrypt GSM phones
- was protected as a "trade secret"
- but has subsequently been reverse engineered (fully at SCARD'99)
- actually has several variants (A5, A5/1, A5/2)
- all have been broken (A5/2 in Aug99, A5/1 in Apr 2000)
- A5/1 uses 3 LFSR's of 19, 22 and 23 bits using sparse feedback polys
- basic attack has complexity
240 - guess state of LFSR's 1 & 2, try to determine 3 from keystream
- A5/2 is weakened version with clocking from 4th LFSR, easily attacked
- real problem is registers are too small & feedback poly's are sparse
A5 is the algorithm used to encrypt the air interface of GSM phones (note other algs are used for key generation & authentication). Originally designers tried to keep algorithm secret using secrecy agreements between all manufacturers. Initially reverse engineered in early 90's - not quite correct. Completely reverse engineered at Smart Card Developers Conf in 1999 - see www.scard.org.
- a Australian designed (98) stream cipher using an LFSR
- but instead of binary values for x use nicer sized words
- several versions for different word sizes (t8, t16, t32)
- has fast keying, small memory, fast implementation
- each element is 8, 16 or 32-bits (a Galois polynomial)
- use XOR and modular polynomial multiplication as operations
- LFSR is updated using (polynomial) evaluation of
Sn+17 = 99 x Sn+15 + Sn+4 + 206 x Sn
- equivalent to a 136-bit binary shift register, period is
2136-1 - uses a non-linear (integer) function on selected values
- and stutters (decimates) output based on some of output
Vn = ROTL(Sn+Sn+16) + Sn+1 + Sn+6 + Sn+13
- analysis of original version identified some flaws
- has subsequently been redesigned
- current analysis appears very promising
- extremely efficient implementation in s/w
- SOBER-t16 being considered for new digital mobile phone standards
- see Rose, ACISP98 & FSE99 proceedings for details of design & analyses
- a proprietary cipher created by RSA Data Security Inc
- not an LFSR but rather a more general PRG design
- another Ron Rivest design, simple but effective
- now a widely licenced commercial cipher
- was kept secret, but has been reverse engineered
- ftp:///ftp.dsi.unimi.it/pub/security/crypt/code/rc4.revealed.gz
- turns key into random permutation of 256 8-bit values
- uses that permutation to scamble input info processed a byte at a time
- basic idea is to start with an array of numbers: 0..255
- and well and truly shuffle this up, controlled by the key
- this array
Sforms the internal state of the cipher - given a key
kof lengthlbytesi = j = 0 initialise array S to {0, 1, 2, ..., 255} repeat 256 times j += S[i] + k[i mod l] (mod 256) swap(S[i], S[j]) increment iThe RC4 key schedule intialises the state S to all number 0..255, and then walks thru each entry in turn, using its current value plus the next byte of key to pick another entry in the array, and swaps their values over. After doing this 256 times, the result is a well and truly shuffled array. The total number of possible states is 256! - a truly enormous number, much larger even that the
2048-bit (=256*8)max key allowed can select.
- to encrypt we continue to shuffle array entries
- and use the sum of the pair we shuffled as the "stream key"
- which then XOR with the next byte of the message
i = j = 0 for each message byte i = i + 1 (mod 256) j = j + S[i] (mod 256) swap(S[i], S[j]) t = (S[i] + S[j]) (mod 256) C = M XOR S[t]
- is claimed secure against known cryptanalyses
- result is very non-linear
- the first group of outputs correlate with key
- so in practise should discard first 256 outputs
- also, being a stream cipher, should never reuse a key
- also after a few GB, see some values occuring slightly too often
- but none of these really a major practical issue
RC4 is widely used, in SSL for secure web transactions amongst other uses. Currently its regarded as quite secure, if used correctly. nb. the comment about the first few values, for example S[0] is very likely the first byte of key. Should step past these.
- many other proposals have been made
- see Schneier for many descriptions
- nearly all have problems
- the frequency of successful attacks on new stream cipher proposals is very worrying
- great care currently should be taken in selecting any for use
- European Community has a call for new algs, including stream ciphers
- may see major advances similar to those AES has pushed
- have several schemes based on public key algorithms, eg RSA
- simplest, best, known and most efficient is the "Blum, Blum and Shub"
(BBS) generator
xi+1 = xi2 mod n and use bi the LSB of xi where n=p.q, primes p,q=3 mod 4
- security rests on difficulty of factoring N
- is unpredictable given any run of bits
- slow, since very large numbers must be used for security
- too slow for cipher use, but good for key generation
Will look at number theory and public key algs next, but note here that like block ciphers, they also can be used as "good" if "extrememy slow" PRGs.