Cryptography-Digest Digest #773, Volume #13 Thu, 1 Mar 01 22:13:00 EST
Contents:
Re: AES FIPS ("Brian Gladman")
Re: RC4 like stream cipher ("Henrick Hellstr�m")
Re: RC4 like stream cipher ("Tom St Denis")
Re: RC4 like stream cipher ("Tom St Denis")
Re: RC4 like stream cipher ("Tom St Denis")
Re: OverWrite freeware completely removes unwanted files fromharddrive (those who
know me have no need of my name)
Re: Keystoke recorder (HiEv)
Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep Boys
("Mxsmanic")
Re: encryption and information theory ("Mxsmanic")
Re: Keystoke recorder (nemo outis)
Re: encryption and information theory ("Mxsmanic")
Re: => FBI easily cracks encryption ...? ("Jeff Moser")
Rabin's Unbreakable Code (Bob Harris)
----------------------------------------------------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: AES FIPS
Date: Thu, 1 Mar 2001 23:15:55 -0000
"Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
news:97mjjn$i0b$[EMAIL PROTECTED]...
>
> Brian Gladman <[EMAIL PROTECTED]> wrote in message
> news:ojan6.1$Jw.48@wards...
> > The AES draft FIPS is now available at:
> >
> > http://csrc.nist.gov/encryption/aes/
> >
> > for comment.
>
> I didn't see anything on modes-of-operation. Am I being even more
clueless
> than usual, or is it, in fact, missing?
You are right - modes of operation (and padding) will be the subject of a
separate exercise.
There are currently quite a number of proposals for new modes of operation
reported on the NIST AES web site. This also outlines this part of the
effort.
It is widely recognised that a new mode is needed that can be efficiently
parallelised and quite a few of the new modes on offer are looking to
provide both confidentiality and integrity with low additional overhead.
Brian Gladman
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: RC4 like stream cipher
Date: Fri, 2 Mar 2001 01:05:02 +0100
I found a crack with a 90% success rate and less than 7% false hits given
2048 bytes of known plain text. The major problem is step 4. Your proposed
modification of step 3 did not have any impact whatsoever on the success
rate of this attack. I simply exploited the weakness intruduced by step 4
you outlined yourself and wrapped it in a brute force attack on the 2-byte
state.
Here is the pascal code:
...
const
MaxUInt8 = 255;
OutputLen = 2048;
AttackCount = 1024;
type
UInt8 = 0..MaxUInt8;
TSBox = array [0..MaxUInt8] of UInt8;
TOutput = array [0..OutputLen-1] of UInt8;
(* Types specific to the attack: *)
Int16 = -1..MaxUInt8;
TElement = record
OrgPos: Int16;
Value: Int16;
end;
TKnowledge = array [0..MaxUInt8] of TElement;
var
S, OrgS: TSBox;
OrgSx, OrgSy, FSx, FSy: UInt8;
Output: TOutput;
(* Variables used by the attack: *)
AttackNo, Hits, FalseHits, SemiFalseHits, FinalHits, Fails: Integer;
Sx0, Sy0, sx, sy, t: UInt8;
i: Integer;
Knowledge: TKnowledge;
Success: Boolean;
te: TElement;
(* Variables used for display purposes: *)
S0: TSBox;
Errors: Integer;
ShadowHits: Integer;
procedure CreateSBox(var ASBox: TSBox);
var
i, j, x: UInt8;
begin
for i := 0 to MaxUInt8 do ASBox[i] := i;
for i := MaxUInt8 downto 1 do begin
j := Random(i + 1);
x := ASBox[i];
ASBox[i] := ASBox[j];
ASBox[j] := x;
end;
end;
procedure KeyStream(var ASBox: TSBox; var ASx, ASy: UInt8; var AOutput:
TOutput);
var
i: Integer;
t: UInt8;
begin
for i := 0 to OutputLen-1 do begin
t := ASBox[Asx];
ASBox[Asx] := ASBox[Asy];
ASBox[Asy] := t;
{$IFDEF MODIFIED}
Asy := (Asx + Asy + 1) mod (MaxUInt8 + 1);
{$ELSE}
Asy := (Asx + 1) mod (MaxUInt8 + 1);
{$ENDIF}
Asx := t;
AOutput[i] := t;
end;
end;
procedure InitKnowledge(var AKnowledge: TKnowledge);
var
j: Integer;
begin
for j := 0 to MaxUInt8 do
with AKnowledge[j] do begin
(* -1 means unknown to the attacker: *)
OrgPos := j;
Value := -1;
end;
end;
begin
(* Initialize: *)
Randomize;
Hits := 0;
FalseHits := 0;
SemiFalseHits := 0;
FinalHits := 0;
ShadowHits := 0;
Fails := 0;
(* Main: *)
for AttackNo := 0 to AttackCount-1 do begin
(* Create key to be attacked: *)
CreateSBox(S);
Move(S,OrgS,SizeOf(S));
OrgSx := Random(256);
OrgSy := Random(256);
(* Create output to be attacked: *)
FSx := OrgSx;
FSy := OrgSy;
KeyStream(S,FSx,FSy,Output);
(* Perform attack: *)
for Sx0 := 0 to MaxUInt8 do begin
for Sy0 := 0 to MaxUInt8 do begin
(* This is our current hypothesis: *)
sx := Sx0;
sy := Sy0;
Success := True;
(* Initialize the attack state: *)
InitKnowledge(Knowledge);
(* Evaluate the hypothesis: *)
for i := 0 to OutputLen-1 do begin
(* Fetch evidence: *)
t := Output[i];
(* Is the value of t consistent with the hypothesis? *)
if Knowledge[sx].Value = -1 then
(* Yes, it is consistent, but not supported by evidence. *)
Knowledge[sx].Value := t
else if Knowledge[sx].Value <> t then begin
(* No, skip this attempt and continue with the next hypothesis.
*)
Success := False;
Break;
end;
(* else do nothing - t is supported by previous evidence. *)
(* Update the SBox: *)
te := Knowledge[sx];
Knowledge[sx] := Knowledge[sy];
Knowledge[sy] := te;
(* Update state: *)
{$IFDEF MODIFIED}
sy := (sx + sy + 1) mod (MaxUInt8 + 1);
{$ELSE}
sy := (sx + 1) mod (MaxUInt8 + 1);
{$ENDIF}
sx := t;
end;
(* Do we have a hit? *)
if Success then begin
for i := 0 to MaxUInt8 do begin
Success := Knowledge[i].Value <> -1;
if not Success then Break;
S0[Knowledge[i].OrgPos] := Knowledge[i].Value;
end;
if Success then begin
(* Evaluate result: *)
Errors := 0;
for i := 0 to MaxUInt8 do
if S0[i] <> OrgS[i] then Inc(Errors);
if Errors > 0 then Inc(FalseHits)
else if (Sx0 <> OrgSx) or (Sy0 <> OrgSy) then Inc(SemiFalseHits)
else Inc(Hits);
Errors := 0;
for i := 0 to MaxUInt8 do
if Knowledge[i].Value <> S[i] then Inc(Errors);
if (Errors = 0) and (FSx = sx) and (FSy = sy) then
Inc(FinalHits);
Break;
end else begin
Inc(Fails);
Errors := 0;
for i := 0 to MaxUInt8 do
if Knowledge[i].Value <> S[i] then Inc(Errors);
ShadowHits := ShadowHits + MaxUInt8 + 1 - Errors;
end;
end;
end;
if Success then Break;
end;
end;
Memo1.Lines.Add(Format('Genuine hits: %d',[Hits]));
Memo1.Lines.Add(Format('False hits (Wrong SBox): %d',[FalseHits]));
Memo1.Lines.Add(Format('Semi false hits (Wrong state):
%d',[SemiFalseHits]));
Memo1.Lines.Add(Format('Final state and sbox hits: %d',[FinalHits]));
Memo1.Lines.Add(Format('No exhaustive solution found: %d',[Fails]));
if Fails > 0 then
Memo1.Lines.Add(Format('Avg. shadow success rate:
%f',[ShadowHits/Fails]));
end;
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
"Tom St Denis" <[EMAIL PROTECTED]> skrev i meddelandet
news:1fyn6.266067$[EMAIL PROTECTED]...
> I invented a cute RC4 like keystream generator. It's basically a mix of
RC4
> and Knuth's Algorithm B (Vol2). The C code is below.
>
> The idea is to fill a 256 byte state with a permutation of 0..255 and
> maintain two 8-bit indicies into the array. To get the next byte you
> perform the following.
>
> 1. t1 <= S[sx]
> 2. Swap S[sx] with S[sy]
> 3. sy <= (sx + 1) mod 256
> 4. sx <= t1
> 5. return t1
>
> The algorithm is very fast too. I can make 16mbyte of output in about 3
> seconds (this includes writting to a file) using TurboC (a 16-bit
compiler).
>
> The swap in step two is to update the state of the permutation such that
it
> changes over time making ("in theory") harder to break. The addition in
> step 3 is to avoid small cycles much like the addition in RC4. The thing
I
> can't wrap my head around is if returning "sx = t1" is a good idea. In
two
> consecutive bytes you will know (?, sx), (sx + 1, sx'), we know now that
sx'
> = S[sx], so we learn a byte of the table, but since we don't know the
first
> sy we don't know what S[sx] has after the first byte.
>
> However, looking at the 2nd and 3rd byte we have { (sx + 1, sx'), (sx' +
1,
> sx'') } where we know the "first" sy value.
>
> Perhaps step three should read
>
> 3. sy <= (sy + sx + 1) & 255
>
> Thus sy is never directly revealed.
>
> Tom
>
> /* state */
> unsigned char s[256], sx, sy;
>
> /* get the next byte */
> unsigned char nbyte(void)
> {
> unsigned char t1, t2;
>
> /* get current value */
> t1 = s[sx];
>
> /* swap s[sy] with s[sx] */
> t2 = s[sy]; s[sy] = s[sx]; s[sx] = t2;
>
> /* update the indices */
> sy = (sx + 1) & 255;
> sx = t1;
>
> return t1;
> }
>
>
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: RC4 like stream cipher
Date: Fri, 02 Mar 2001 00:13:01 GMT
"Henrick Hellstr�m" <[EMAIL PROTECTED]> wrote in message
news:97mo69$2c3$[EMAIL PROTECTED]...
> I found a crack with a 90% success rate and less than 7% false hits given
> 2048 bytes of known plain text. The major problem is step 4. Your proposed
> modification of step 3 did not have any impact whatsoever on the success
> rate of this attack. I simply exploited the weakness intruduced by step 4
> you outlined yourself and wrapped it in a brute force attack on the 2-byte
> state.
Ouch. Could you explain your attack better? I had a hunch that giving out
an index was bad but how so?
As a side note Diehard likes this PRNG (despite the fact it's insecure).
Any hints on how to generate an output without falling victim to the attack?
How about changing step 1 to read "t1 <= (s[sx] + s[sy]) mod 256".
I.e
1. t1 <= (S[sx] + S[sy]) mod 256
2. swap S[sx] with S[sy]
3. sy <= (sy + sx + 1) mod 256
4. sx <= t1
return t1
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: RC4 like stream cipher
Date: Fri, 02 Mar 2001 00:16:59 GMT
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:hABn6.263$[EMAIL PROTECTED]...
> 1. t1 <= (S[sx] + S[sy]) mod 256
> 2. swap S[sx] with S[sy]
> 3. sy <= (sy + sx + 1) mod 256
> 4. sx <= t1
> return t1
It turns out this doesn't work at all... back to the drawing board.
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: RC4 like stream cipher
Date: Fri, 02 Mar 2001 00:22:42 GMT
"Henrick Hellstr�m" <[EMAIL PROTECTED]> wrote in message
news:97mo69$2c3$[EMAIL PROTECTED]...
> I found a crack with a 90% success rate and less than 7% false hits given
> 2048 bytes of known plain text. The major problem is step 4. Your proposed
> modification of step 3 did not have any impact whatsoever on the success
> rate of this attack. I simply exploited the weakness intruduced by step 4
> you outlined yourself and wrapped it in a brute force attack on the 2-byte
> state.
Hmm if you wrote your attack in C I could try this myself but...
Try changing to
1. t1 <= S[sy]
2. swap S[sy] with S[sx]
3. sy <= (sy + sx + 1) mod 256
4. sx <= t1
5. return t1
This way sx does equal t1 but it's not used directly in the next
construction. Thus you get (?, S[sy]), (? + S[sy] + 1, S[? + S[sy] + 1]),
etc... where ? means information missing. I think it should be harder to
reconstruct the state from this.
And this modification passes diehard, so at least it's statistically sound.
Tom
Full C source code...
/* state */
struct gum_key {
unsigned char s[256], sx, sy;
};
/* get the next byte */
unsigned char gum_next(struct gum_key *k)
{
unsigned char t1, t2;
/* get current value */
t1 = k->s[k->sy];
/* swap s[sy] with s[sx] */
t2 = k->s[k->sy]; k->s[k->sy] = k->s[k->sx]; k->s[k->sx] = t2;
/* update the indices */
k->sy = (k->sx + k->sy + 1) & 255;
k->sx = t1;
return t1;
}
/* key setup */
void gum_setup(struct gum_key *k, unsigned char *key, int len)
{
unsigned char t1, t2;
int x;
k->sx = 0; k->sy = 128;
for (x = 0; x < 256; x++) k->s[x] = x;
for (x = 0; x < 2048; x++) {
t1 = k->s[(k->sx + key[x % len]) & 255];
t2 = k->s[k->sy]; k->s[k->sy] = k->s[k->sx]; k->s[k->sx] = t2;
k->sy = (k->sy + k->sx + 1) & 255;
k->sx = t1;
}
}
------------------------------
From: [EMAIL PROTECTED] (those who know me have no need of my name)
Crossposted-To: alt.hacker,alt.usenet.kooks
Subject: Re: OverWrite freeware completely removes unwanted files fromharddrive
Date: Fri, 02 Mar 2001 00:37:30 -0000
[discussion re the effects of caching on wiping a file, wherein anthony
does not believe that two writes to the same sector might result in the
older request being discarded if not already initiated before the newer
request is enqueued.]
<[EMAIL PROTECTED]> divulged:
>You only talk a good stick.
>
>Yet you have done nothing but a bunch of hand waving.
you're a loon. i'm happy i don't have one line of your code anywhere
near my machine.
>give us a few references from expert computer engineers /
>manufacturers supporting your exact position.
sci.crypt is only peripherally interested in caching. you'll find lots
more people interested in the effects of caching (cpu, memory, and disk)
on wiping files in the security or privacy newsgroups.
--
okay, have a sig then
------------------------------
From: HiEv <[EMAIL PROTECTED]>
Subject: Re: Keystoke recorder
Date: Fri, 02 Mar 2001 01:55:24 GMT
nemo outis wrote:
>
> First of all the trojan is by definition an executable. The .txt file will not
> spontaneously rename itself. The principle is to look for new or modified
> executables and some things (such as trojans and viruses) may be detected with
> other means than the MD5 hash.
[snip]
No, he isn't suggesting that. What he is saying is that you could have
a trojan (with an EXE extension) that would be run when Windows starts,
it would then rename itself to *.TXT so that a virus/trojan sniffer
would overlook it, and then rename itself back to *.EXE when it detects
that Windows is shutting down so that it could start up again the next
time you turn on your computer.
However, when an executable is being run by Windows it will normally
lock the file, so you can't rename it. But there is probably a way
around that. :-)
------------------------------
From: "Mxsmanic" <[EMAIL PROTECTED]>
Subject: Re: The Key Vanishes: Scientist Outlines Unbreakable Code, Read it and Weep
Boys
Date: Fri, 02 Mar 2001 02:29:40 GMT
<[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Obviously any system which can transmit data down
> a fiber can do so through empty space.
That is not obvious to me. Fiber ensures a clear path from start to
finish. An atmosphere does not.
> Because you can prove that even using relatively
> insecure PRNGs you can still get provable security
> by using them to index into a random source larger
> than will fit into the eavesdropper's memory. That's
> right, you can prove it. Surprised?
If the random source is larger than the eavesdropper's memory, why do
you need a PRNG at all? You can just start at any convenient point,
because if your spook doesn't have a recording of the stream, he cannot
reconstruct it, even if he knows where you started.
Conversely, if your eavesdropper has enough memory to hold all the
random bits, using a PRNG to pick a starting point will not help you.
And since the number of bits from which you can choose is constrained by
time (you cannot use streams from the past, and you cannot index too far
into the future to be practical), the amount that your enemy must
memorize may well be quite manageable.
> The PRNG is not secure, yet by using it to index
> into the random bit stream, you get provable security,
> even though the bit stream is public.
See above. If your enemy doesn't have the random bit stream, you can
start anywhere you want--you don't need a PRNG to pick a spot.
Conversely, if your enemy has the bit stream, it doesn't matter how you
choose your starting point, because he will compromise your encryption
in any case.
> That's what is proven; read the papers (Maurer 97, Rabin 99).
Where are they?
> The shared secret can be of modest size, yet you
> get far more security than that.
The shared secret is either unnecessary or useless. As I've said above,
if the bad guys have the entire bit stream, they don't need your key
into that stream; they can just shift it back and forth until your
message pops out--so keeping your key secret accomplishes nothing.
Conversely, if they don't have your bit stream, then they'll never
decrypt your message, even if you publish your starting point in the New
York Times.
There's another problem with this. It may be fine for real-time
encryption and decryption, but what if you want to store encrypted data?
It won't suffice to keep just the starting point that you use as your
shared secret; you'll have to keep the entire random bit stream, and it
will be as long as the ciphertext. And you'll have to keep _all_ of it
secret, somehow. So you'll need someplace very secure to hold all those
bits; but since they are of the same length as the ciphertext, why
bother? Just store the plaintext in that secure location instead, and
forget the random bits. But then you no longer have the encrypted form,
so you'd have to generate it again if you needed it.
> So this scheme actually amplifies the security beyond
> the size of the shared secret!
The shared secret has nothing at all to do with security. The entire
scheme depends on how much memory your opponent has. If he has enough,
he'll crack your encryption, no matter what shared secret you use; if he
doesn't have enough, he'll never crack your encryption, even if you make
your "secret" key public.
> And it does so in a provable fashion. Starting to
> sound more revolutionary?
No.
------------------------------
From: "Mxsmanic" <[EMAIL PROTECTED]>
Subject: Re: encryption and information theory
Date: Fri, 02 Mar 2001 02:38:41 GMT
"John Savard" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> More precisely: if the message contains N bits of
> information, and occupies M bits of bandwidth, and
> the K is K bits long, the entropy of the encrypted
> message is N+K bits, *or* M bits, whichever is less.
The entropy can never be less than N+K, or the original plaintext
message will be lost (because information has been permanently lost).
Thus, M must always be equal to or greater than N+K, if the original
message is ever to be recovered.
Similarly, if you have a message that contains N bits of information,
you cannot compress it into M bits of information, where M<N. All
compression methods, when used to encrypt random data, will generate, on
average, at least as many bits in the "compressed" result as were
present in the uncompressed original. The only reason compression
methods work at all is that they make certain useful assumptions
concerning the type of redundancy present in the uncompressed message;
if these assumptions are correct (and in practice, they usually are),
the compressed message takes up less space, but if they are incorrect,
the compressed message takes up more space. If the uncompressed message
is random (entropy and information content equal the length of the
message), any compression algorithm will produce output at least as long
as the random input.
------------------------------
From: [EMAIL PROTECTED] (nemo outis)
Subject: Re: Keystoke recorder
Date: Fri, 02 Mar 2001 02:41:48 GMT
There are only a few places from which a trojan can load itself at startup,
and ways to start up, and these are easily examined.
What is being described is a variant on stealth viruses but applied to
trojans. Virus checking (rogue processes, etc.) is a standard problem for
which there are good (but not perfect) solutions.
I start from a boot CD containing my "known-good" versions of the OS,
registry, ini files, etc.
Is it perfect? No, but it's pretty solid.
Regards,
In article <[EMAIL PROTECTED]>, HiEv <[EMAIL PROTECTED]>
wrote:
>nemo outis wrote:
>>
>> First of all the trojan is by definition an executable. The .txt file will
> not
>> spontaneously rename itself. The principle is to look for new or modified
>> executables and some things (such as trojans and viruses) may be detected
> with
>> other means than the MD5 hash.
>[snip]
>
>No, he isn't suggesting that. What he is saying is that you could have
>a trojan (with an EXE extension) that would be run when Windows starts,
>it would then rename itself to *.TXT so that a virus/trojan sniffer
>would overlook it, and then rename itself back to *.EXE when it detects
>that Windows is shutting down so that it could start up again the next
>time you turn on your computer.
>
>However, when an executable is being run by Windows it will normally
>lock the file, so you can't rename it. But there is probably a way
>around that. :-)
------------------------------
From: "Mxsmanic" <[EMAIL PROTECTED]>
Subject: Re: encryption and information theory
Date: Fri, 02 Mar 2001 02:47:04 GMT
"Benjamin Goldberg" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Consider symettric encryption. Is there information
> added to the message during encryption which the attacker
> does not know?
No.
> YES, the secret key is added, and the attacker does not
> know the secret key.
The secret key is not added to the message. Nothing is added to the
message. Parts of the message are transposed, and parts are
substituted, but the overall information content remains the same.
------------------------------
From: "Jeff Moser" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,talk.politics.crypto
Subject: Re: => FBI easily cracks encryption ...?
Date: Thu, 1 Mar 2001 21:55:11 -0500
It wouldn't surprise me if some micro-transmitter was attached to his
keyboard cable (or inside the keyboard itself).. then just look at that for
PGP (or some other program) pass phrases. The point is, I don't think this
guy was stupid enough to use poor encryption. Same idea since the Xerox
camera in Russia 40-50 (?) years ago.
Just my 2.71828 cents,
Jeff
------------------------------
From: Bob Harris <[EMAIL PROTECTED]>
Subject: Rabin's Unbreakable Code
Date: Thu, 01 Mar 2001 22:02:17 -0500
Howdy,
I read an AP article in today's newspaper about a proof by Michael Rabin and
Ynazhong Ding (aparently a Havard CS professor and a doctoral student) that
can be used to "make a code indecipherable by even the most powerful
computers." As is common for such an article, the quoted sentence fragment
is the extend of the mathematical detail it contained.
I searched the web, and this newsgroup, but haven't been able to find a
reference to this proof. Does anyone here have any info about it?
Thanks in advance, and apologies if it's in the FAQ. I searched the group
postings and found not faq or anything I could identify by title that had
any relevance to this.
Bob Harris
------------------------------
** FOR YOUR REFERENCE **
The service address, to which questions about the list itself and requests
to be added to or deleted from it should be directed, is:
Internet: [EMAIL PROTECTED]
You can send mail to the entire list by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
