Good stream cipher (other than ARCFOUR)
Viktor Lundström
It needs to be reasonably fast since it will be used for file
transfer.
I made some searches and came up with the "Pukall Cipher 1" (PC1),
but did not find any analysis of it. Is this a good cipher?
--------------------------------------------
Viktor Lundström
d99...@nada.kth.se
--------------------------------------------
David Wagner
>Does anyone know of a good stream cipher, other than ARCFOUR?
How about SEAL? What about AES-CTR mode?
>I made some searches and came up with the "Pukall Cipher 1" (PC1),
>but did not find any analysis of it. Is this a good cipher?
I don't think I've ever heard of it. Where was it published?
Henrick Hellström
> Viktor Lundström wrote:
> >I made some searches and came up with the "Pukall Cipher 1" (PC1),
> >but did not find any analysis of it. Is this a good cipher?
>
> I don't think I've ever heard of it. Where was it published?
I found some source code at
http://www.multimania.com/cuisinons/pc1/index.html . The cipher seems to
date back to 1991.
The cipher seems to be insecure. Because of the way the plain text is merged
into the key and because of the size of the internal state, there is an
obvious chosen plain text attack with an expected success rate of 2^16:
Let C = (C1,C2) be an authentic cipher text of the plain text message P =
(P1,P2). Choose a string S such that the xor checksum of S is zero. Transmit
(C1,S,C2) to the decryption device. If the decryption of C2 comes out as P2,
then success, otherwise failure.
Here is some pascal source code I assembled from the reference
implementation:
type
TPC1State = record
x0 : Word;
x1 : Word;
x2 : Word;
key : array [0..9] of Byte;
end;
function KeyStream(var State: TPC1State): Word;
var
i: Integer;
function Code(i: Word; var State: TPC1State): Word;
var
a, d: Word;
begin
a := State.x0 * $4e35 + 1;
d := State.x0 * $015a + State.x1 + (State.x2 + i) * $4e35;
State.x1 := State.x0 * $015a;
State.x0 := a;
State.x2 := d;
Code := a xor d;
end;
begin
State.x0 := State.key[0]*256 + State.key[1];
KeyStream := Code(0,State);
for i := 1 to 4 do begin
State.x0 := State.x0 xor (State.key[i*2]*256 + State.key[i*2+1]);
KeyStream := KeyStream xor Code(i,State);
end;
end;
procedure Encrypt(ThisKey, Buffer: PChar; BufferLength: Integer);
// The buffer contains the message to encrypt.
// ThisKey contains the password, 10 characters at max.
// Henrick Hellström: The reference implementation also specified a peculiar
base16 encoding of the cipher text.
var
c: Byte;
x: Word;
i,j: Integer;
State: TPC1State;
begin
// Initialization
ZeroMemory(@State, SizeOf(State));
if ThisKey <> nil then begin
j := 0;
while (j < 10) and (ThisKey[j] <> #0) do begin
State.Key[j] := Ord(ThisKey[j]);
Inc(j);
end;
end;
// Encryption
for i:=0 to BufferLength-1 do begin
c:= ord(Buffer[i]);
x := KeyStream(State);
Buffer[i] := Char(c xor x xor (x shr 8));
// Plain text feedback
for j := 0 to 9 do
State.key[j]:= State.key[j] xor c;
end;
end;
Henrick Hellström
> The cipher seems to be insecure. Because of the way the plain text is merged
> into the key and because of the size of the internal state, there is an
> obvious chosen plain text attack with an expected success rate of 2^16:
>
<correction>
Let C = (C1,C2) be an authentic cipher text of the plain text message
P = (P1,P2). Choose a string S such that the xor checksum of S is zero.
Transmit (P1,S) to the decryption device to obtain C' = (C1,C3). Next transmit
C'' = (C1,C3,C2) to the decryption device. If the decryption of C2 comes
out as P2, then success, otherwise failure.
</correction>
Viktor Lundström
On Thu, 17 Jan 2002, David Wagner wrote:
> Viktor Lundström wrote:
> >Does anyone know of a good stream cipher, other than ARCFOUR?
>
> How about SEAL? What about AES-CTR mode?
I forgot to include this in my original post; it has to be a free
algorithm, and SEAL is patented by IBM.
I'm sort of an encryption novice, so I don't know what CTR stands
for. Making an educated guess, it's about running a block cipher so
it works like a stream cipher, right? Is this easily done, and are
there any code examples available on the web?
Henrick Hellström
> I'm sort of an encryption novice, so I don't know what CTR stands
> for. Making an educated guess, it's about running a block cipher so
> it works like a stream cipher, right? Is this easily done, and are
> there any code examples available on the web?
CTR stands for counter mode:
Let P = P1,P2,P3,P4,...,Pn
1. ctr := IV
2. for i := 1 to n do
2.1. Ci := E_k(ctr) xor Pi
2.2. ctr := ctr + 1
The size of ctr corresponds to a block, so it might have to be padded
with zero bits.
There is basically only one rule for using this mode, and that is to
never use any combination of (k,ctr) twice. It is OK to e.g. always let
IV = 0 as long as each message P is encrypted with a unique key.
Otherwise you'll have to keep track of which ctr values have been used up.
CTR mode is not propagating and does not provide any additional
services, such as message authentication etc. Like OFB mode but unlike
CBC and CFB mode it doesn't recover from loss of data, because the ctr
value must be synchronized with message.
David Wagner
>I'm sort of an encryption novice, so I don't know what CTR stands
>for. Making an educated guess, it's about running a block cipher so
>it works like a stream cipher, right? Is this easily done, and are
>there any code examples available on the web?
Yes, yes, and probably. For lots of details on CTR mode, you can
refer to <http://www.cs.berkeley.edu/~daw/papers/ctr-aes00.ps>.
Another possibility (just as good) is OFB mode. Both OFB and CTR mode
should be described in your favorite crypto textbook: e.g., _Handbook
of Applied Cryptography_ or _Applied Cryptography_.