geo909
Reputation
Top tag
Next privilege 250 Rep.
 May12 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? They cite something for those proofs: R. Rueppel, Analysis and design of Stream Ciphers, 1986 May12 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? @sarwate Yes, that's right, to my understanding. Now, about the "pairwise coprime" thing: they say without proof that for pairwise coprime LFSR lengths (tapped to give maximal sequences), we get a keystream period equal to $\prod_{i=1}^m 2^{L_i}-1$ (easy to see) and linear span $f(L_1,\dots,L_m)$ (evaluated as we discussed). From their wording I assume that the "pairwise coprime" assumption applies to the latter, too.. May11 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? Good point! "[...] the linear complexity is [...] $L=f(L_1,\cdots,L_m)$ [...] with the latter Boolean function transformed by evaluating the addition and multiplication operations in the function over the integers rather than over $GF(2)$" (Dawson, Simpson, Analysis and Design issues for Synchronous Stream Ciphers). Also this applies when the $L_i's$ are pairwise coprime. May11 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? It seems that ideally one would like linear complexity almost equal to the period of the keystream (and of course, a large period) May11 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? So, that's another good reason not to use combinations of LFSRs.. After reading your answer I looked a bit more carfully and confirmed that if the combiner function is $f$ and the lengths of the $m$ LFSRs are $L_1,\cdots,L_m$, then the linear complexity of the output sequence is $f(L_1,\cdots,L_m)$; in our case that's the sum of the $L_i's$ as you said. So, for lengths that add up to 128 (so we have a 128-bit key), one needs only $2\times 128=256$ bits of the keystream sequence and the Berlekamp-Massey algorithm to break the system. May11 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? You're right! By the reccurent nature of the LFSRs, every output bit of every LFSR can be expressed as a linear combination of the initial state! Then we end up with a system of linear equations and we can perform Gaussian elimination. May11 comment Combining LFSRs for Stream Ciphers: Why do we need high non-linearity? @rphv I think there is another issue about the edit: one needs $2n$ bits if the tap positions are not known. If they are known, one needs $n$ bits. Feb19 comment Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR That's clear; I added an answer with an example demonstrating your answer. If you ever have time you maybe could have a look at my LFSR-related question here? Feb17 comment Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR Thanks a lot for your answer.. There are still some parts that I don't get though. You say in your last sentence that this LFSR will typically not be of length L and the feedback polynomial will typically differ from that of the LFSR of length L that is known to generate (S0,S1,…,Sn−1). But doesn't $L$ refer to the shortest LFSR anyway? That's what you say in the beginning too. Maybe I need to read again 'cause there are lots to absorb but this part is a bit fuzzy.. Thanks! Feb16 comment Berlekamp-Massey algorithm: case when sequence length is less than double the length of the LFSR Due to my low reputation I couldn't add the non-existing tags "LFSR", maybe it makes sense that somebody does that.. Nov15 comment Word-based stream ciphers vs “regular” stream ciphers? I'm not sure what $P'$ is but I do understand the difference now, thanks. I guess regular stream ciphers are more efficient in hardware implementation that block ciphers in CTR or OFB mode, right? Nov15 comment Word-based stream ciphers vs “regular” stream ciphers? You are right about the car user analogy but my perspective is not exactly the driver's. I'm studying finite fields focusing on the non-applied side, however I wanted to have a small look on the applications and see how exactly finite fields are used and why we prefer this or that in cryptography. That is, I am mostly interested to have a sneak peak on the engine rather than going for a ride :) Nov15 comment Word-based stream ciphers vs “regular” stream ciphers? @D.W. You are right! I just realized I misread! There was a small part saying that "ORYX was found to be a seriously flawed design" but much less is known about the security of the rest of the above mentioned word based stream ciphers (i.e. SNOW,PANAMA,SOBER,ORYX), not all stream ciphers in general. Thanks for pointing that out! I removed that part of the question. Nov15 comment Word-based stream ciphers vs “regular” stream ciphers? Yes, they are from Analysis and Design Issues for Synchronous Stream Ciphers by Dawson and Simpson in Lecture Notes Series, Insititute for Mathematical Sciences, National University of Singapore written in 2002. Nov14 comment Word-based stream ciphers vs “regular” stream ciphers? I don't have enough reputation to vote this up, but it answers my question, many thanks.. I was also wondering how one could compare word-based stream ciphers and block ciphers. I do not know much about block ciphers so there may be a very basic and fundamental difference that I do not see, however I can tell that they process blocks of bits at a time, so it seems that they are similar to woed-based stream ciphers in that sense? What is the difference?