Cryptography-Digest Digest #748, Volume #13 Sun, 25 Feb 01 18:13:01 EST
Contents:
Re: Diffie-Hellman via Complex Associative Hash Functions (Mok-Kong Shen)
Re: Simple, possibly flawed, stream cipher ("Henrick Hellstr�m")
Re: SHA-1 (was Re: Password authentication ...) (Tim Tyler)
Re: fiat shamir (David Hopwood)
Re: super-stong crypto, straw man phase 2 (William Hugh Murray)
Re: OverWrite freeware completely removes unwanted files from harddrive (Anthony
Stephen Szopa)
Re: OverWrite freeware completely removes unwanted files from harddrive (Benjamin
Goldberg)
Fair(er)play (JPeschel)
Re: Fair(er)play (JPeschel)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Diffie-Hellman via Complex Associative Hash Functions
Date: Sun, 25 Feb 2001 20:37:49 +0100
Jim Steuert wrote:
>
> Why can't Diffie-Hellman be accomplished using
> associative (and balanced) hash functions? If both Alice and Bob
> start with a common very long public initial seed, and their secret exponents are
>
> not so large as to compress it to nothing (an important requirement), then
> common secret = bob's: (Seed^a)^b will equal alice's: (Seed^b)^a where
> where a is alice's part of the secret and b is bob's part of the secret.
> In this usage, a nesting of xor and prime-modulus associative operators
> may work.
I don't understand why do you need the concept of a 'hash
function'. (Do you have any concrete hashing function in
mind that works in the current context?) I suppose that what
you require is a (general) multiplication operator (that is
associative), as you said in your original article. If you
choose such an operator (other than the normal one on
integers) like the one for a vector (of integers) of your
previous post, then I guess that you are faced with three
tasks: (1) Prove that the operator is associative. (2) Show
that taking the logarithm is hard. (3) Demonstrate that it
is more efficient/economical than the scheme currently being
used.
M. K. Shen
------------------------------
From: "Henrick Hellstr�m" <[EMAIL PROTECTED]>
Subject: Re: Simple, possibly flawed, stream cipher
Date: Sun, 25 Feb 2001 20:36:57 +0100
"Scott Fluhrer" <[EMAIL PROTECTED]> skrev i meddelandet
news:97bhlf$7ql$[EMAIL PROTECTED]...
> However, from it appeared what you were doing, well, it didn't appear to
be
> exactly what I was thinking of. Some comments about what those variables
> were would definitely help. Perhaps I'll throw together my own analysis
> program.
Here are some comments:
* By convention, arguments of functions and procedures are prefixed with the
letter 'A' to distinguish them from constants and local and global
variables.
* IBox is the "inverse" of the function f(s) = (SBox[s] xor SBox[s+1]), or,
rather, IBox[x] contains the solutions s to the equation x = (SBox[s] xor
SBox[s+1]).
* Key is the initial value of State. It is only kept for display purposes.
* Guess is the result of the attack, i.e. the guessed value of Key.
* I count the frequencies of solutions s to the equation (x xor y) =
(SBox[offset + s] xor SBox[offset + s+1]), where x is the present adjusted
output value (the impact of lower state values is eliminated), y is the
previous adjusted output value, and offset is the offset from the initial
value of state[i]. If there is no solution, the event is not counted.
Otherwise the frequency of each solution is incremented by 1/count, where
count is the number of solutions.
* Dev is the deviation of the most frequent solution. It is only calculated
for display purposes.
BTW I detected one error in the procedure Analyze1, but it seems as if it
did not have any major impact on the success rate. The correct code should
be:
procedure Analyze1(const AOutput: TOutputArray;
const ASBox: TSBox;
const AState: TStateArray;
const Index: Integer;
const AIBox: TInverseSBox;
var AFreq: TFrequencies);
var
i, j, k, count, offset: Integer;
s: TStateArray;
x, y, dx: Byte;
df: Real;
yval: Boolean;
begin
(* Transfer the known initial values of State[i] to a local variable: *)
for i := 0 to Index - 1 do
s[i] := AState[i];
(* We don't know the initial value of State[Index], of course, but we will
calculate the offset from the initial value: *)
s[Index] := 0;
(* We don't have any previous adjusted value yet: *)
yval := False;
for j := 0 to HighOutput do begin
x := 1;
(* Step through the state update procedure, up to Index: *)
for i := 0 to Index-1 do begin
if Odd(x shr i) then s[i] := (s[i] + 1) mod 256;
x := x xor ASBox[s[i]];
end;
(* Do we have a possibly valid hit? *)
if Odd(x shr Index) then begin
s[Index] := (s[Index] + 1) mod 256;
(* Calculate the offset from the initial value of State[Index]: *)
Offset := 256 - s[Index];
(* Adjust the output value: *)
x := x xor AOutput[j];
(* Do we have a previous adjusted output value? *)
if yval then begin
dx := x xor y;
count := AIBox[dx,0];
(* Do we have any solutions to the equation? *)
if count > 0 then begin
for i := 1 to count do begin
(* k is a possible initial value of State[Index]. *)
k := (AIBox[dx,i] + offset) mod 256;
Freq[k] := Freq[k] + 1/count;
end;
end;
end;
end else
x := x xor AOutput[j];
(* Store the value of x, so that we might calculate dx at the next position:
*)
y := x;
(* We have an adjusted output value: *)
yval := True;
end;
end;
--
Henrick Hellstr�m [EMAIL PROTECTED]
StreamSec HB http://www.streamsec.com
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: SHA-1 (was Re: Password authentication ...)
Reply-To: [EMAIL PROTECTED]
Date: Sun, 25 Feb 2001 19:49:03 GMT
"Henrick Hellstr�m" <[EMAIL PROTECTED]> wrote:
: I am referring to the random excursions and random excursions variant tests
: described in NIST Special Publication 800-22, applied on the SHA1 generator
: implemented in the accompanying software.
: I have two things to say about this:
: Firstly, I'd be a fool if I completely ruled out the possibility that I made
: some kind of implementation error. If I am wrong, I am sorry if I wasted
: anyone's time and attention.
What you describe would be very, very suprising. Are you using SHA1 in
counter mode? OFB mode? If you are feeding it repeating values that
might explain your results.
Your results with 3DES are equally astonishing. What chaining mode are
you using?
--
__________
|im |yler [EMAIL PROTECTED] Home page: http://alife.co.uk/tim/
------------------------------
Date: Sun, 25 Feb 2001 20:20:37 +0000
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: fiat shamir
=====BEGIN PGP SIGNED MESSAGE=====
zipa wrote:
> In Fiat-Shamir the prover chooses a random r<n in the first step.
> If the prover sends X=r^2 +m*n (for some random m<n) instead of
> X=r^2 (mod n) can the verifier find r ?
No, assuming m is independent of r. Why do you ask?
- --
David Hopwood <[EMAIL PROTECTED]>
Home page & PGP public key: http://www.users.zetnet.co.uk/hopwood/
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
Nothing in this message is intended to be legally binding. If I revoke a
public key but refuse to specify why, it is because the private key has been
seized under the Regulation of Investigatory Powers Act; see www.fipr.org/rip
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOplKFzkCAxeYt5gVAQEtuggAm7rNVMa0maVmX2M1L0qWKiWuwFP21t4T
TqWF0YbAGQ9ytQ+X3iPsyT2p8Fasc3jmtI+Tv97l0udz+VWCp+30MhdsGBuzPrmT
eyb+cx239rIBb3kDZaobBn7sLM/v8/o84zVmsFhAtXmWkUOFFEqMxY5Gy4wXGCzY
qxMLJ5AXcBRuxjjeixW8xDAGdNGknaFIQjC8ZJFiz3H0oEUBIyfS530UfcqyKrQx
LfV1qdYEyiQ3s+g3+CQWg5r2IO/VFFaOMAXqz6D3b7521X1la0ymOXVNIJa+GM8V
pdQ9ZFzoKM5V3v+up83Tdhks0/5r+Z/oK6O7DVNB04WYNzdD8UtZoA==
=QUsZ
=====END PGP SIGNATURE=====
------------------------------
From: William Hugh Murray <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: super-stong crypto, straw man phase 2
Date: Sun, 25 Feb 2001 20:55:38 GMT
Nicol So wrote:
> William Hugh Murray wrote:
> >
> > Nicol So wrote:
> >
> > > I don't think we know enough about DES to be able to say that [adding
> > > an extra round to DES adds no protection.] There may
> > > be more efficient attacks than currently known/published. And round 17
> > > may make such attacks less effective or less efficient. Unless we know
> > > that no such attacks exist, we really cannot say for sure that round 17
> > > adds no protection.
> >
> > It is not necessary to know that there is not a more efficient attack than
> > brute force. It is sufficient to know that brute force against the key is
> > the most that anyone will spend. That is to say, an exhaustive attack
> > against the key is the most that any one will spend without regard to what
> > else they know. They may not spend that much if they know a more efficient
> > attack but they will clearly not spend more. ...
>
> At the risk of oversimplifying the multi-faceted nature of attacks, we
> can think of the "strength" of cipher as determined by the most
> efficient attack (relative to a given cost measure). Exhaustive search
> and other published attacks represent known upper bounds on the strength
> of DES, but they don't tell us the true strength of DES. The kind of
> results we need are tight lower bounds, which are few and far in between
> in complexity theory.
I agree to both points. However, I was not addressing either. Rather, I was
addressing the claim that differential cryptanalysis was a cheap tool.
> For all we know, some government agency *could* have much better
> cryptanalytic techniques against DES than the public know of.
However unlikely it is that anyone could keep such a secret, I must grant your
point, at least for "sake of argument." I often grant that a nation state can
read any message that it wants.
> For the
> sake of argument, let's say they have a technique that requires about
> 1000 plaintext-ciphertext pairs, succeeds with a probability of about
> 0.5 and requires an amount of work comparable to 100000 trial
> encryptions. Suppose a 17-th round degrades the technique by increasing
> the required plaintext-ciphertext pairs (say to 2000), decreasing the
> probability of success (say to 0.25), or increasing the complexity of
> the computation (say by doubling it). To me, that's added protection.
> The fact that exhaustive search and differential cryptanalysis are not
> materially affected is irrelevant.
Irrelevant to your point but not to mine.
> > What differential cryptanalyis told us was that, for the DES, there was a
> > subtle balance between the number of rounds and the length of the key. A
> > longer key would not add much protection if the number of rounds was held
> > constant. Additional rounds would not add much protection if the key were
> > kept constant. Until Biham and Shamir published, many people thought that a
> > longer key, for example, 64 bits, which would raise the cost of an exhaustive
> > attack dramatically but not that of differential cryptanalysis, would add
> > protection.
>
> I think the above assessment overestimates the significance of the
> differential cryptanalysis results.
Perhaps. Opinion is difficult to dispute.
> Just because 16 rounds are optimal
> for resistance to (a particular version of) differential cryptanalysis....
I do not think that Biham and Shamir made that claim or that that is what their
analysis showed. They did not claim that 16 rounds was optimal so much as that at
a lower level of complexity the cost of attack was dramatically lower than an
exhaustive attack against the key.
> .....doesn't mean that it is the optimal choice w.r.t. other potentially
> practically more significant attacks.
Agreed. However, it is in the nature of both science and rhetoric that it is
easier to demonstrate what is than it is to demonstrate what is not, the set of
"what is" being bounded while the set of what is not is unbounded. We should not
dismiss the significance of the former simply because the latter would be so nice
to have.
Now, the above is to my point. What follows it to yours.
Nice to have does not equate to necessary. While certainty would be nice to have
in many areas, certainty remains elusive. We get along very well with first order
approximations in many spaces. We have managed in the cryptography space for
millenia. Until this century no one had even raised the question of proof. Until
Shannon no one had suggested provable, much less both provable and practical.
Practical cryptography is a sufficiently difficult problem to occupy many, not to
say most, of us. We will continue to manage even as the use, uses, and users
increase. The difference between provable cryptography and strong cryptography is
not as great as the difference between that of strong cryptography and the other
security mechanisms necessary to sustain it. Yes, I understand and expect that you
will claim that this assertion is not provable. Nonetheless, if modern
cryptography is the weak link in your security, then you are very secure indeed. I
do not need proof for that assertion.
Schneier says that cryptogrpahy is like a high pole in your front yard that you
encourage your enemy to run into rather than run around.
To the extent that he is correct, proof that the pole is too high for your
adversary to climb over is not terribly important. .
It is not clear to me that those who seem to insist upon "provably secure
cryptography," or even provable, are not in the paradoxical position of trying to
prove a negative. That may be why, while this topic has been under almost constant
discussion in this forum since its inception, I still await a statement of the
problem that permits of a solution. In any case, it does not rise much higher than
useful.
William Hugh Murray, CISSP
> --
> Nicol So, CISSP // paranoid 'at' engineer 'dot' com
> Disclaimer: Views expressed here are casual comments and should
> not be relied upon as the basis for decisions of consequence.
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: alt.hacker
Subject: Re: OverWrite freeware completely removes unwanted files from harddrive
Date: Sun, 25 Feb 2001 13:29:29 -0800
Michael Brown wrote:
>
> <SNIP>
> > >
> > > I checked the web pages, but I can't find any description for how the
> > > program ensures that the multiple overwrites actually take place. There
> > > are several ways it could fail for a naive implementation:
> > >
> > > - The OS may allocate new disk blocks when writing the patterns, leaving
> > > the old data unaltered
> > > - The OS may cache the writes, only actually writing the last pattern to
> > > disk (or not even that if the file is removed afterwards)
> > > - The SCSI controller may cache the writes
> > >
> > > I'm interested in how you've solved this.
> > >
> > > Andreas
> > >
> > > --
> > > Andreas Gunnarsson <[EMAIL PROTECTED]>
> > > +46 31 7014268
> >
> >
> > I don't see what you suggest could happen happening.
> >
> I can. My HDD has 2mb cache. Having tested various things I can shove far
> more data that I should be able to through the HDD. In other words, it ain't
> writing it all.
>
> > Give us a specific example where you have written source code that
> > says to open a file and write to the file where the computer did not
> > carry out this instruction.
The code specifically instructs that the file to be overwritten
is to be:
opened in binary mode at the first byte
overwritten byte by byte with the given overwrite sequence
at the end of file the file is closed.
These steps occur with each overwrite sequence pass.
The code instructs the computer to do this.
What you are saying is that even though the code says to do
this that the OS will ignore this code? For example, the file
will not be opened? Is that so?
Give us an example of an OS that sane people are still using
that ignores a hard coded instruction?
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Crossposted-To: alt.hacker
Subject: Re: OverWrite freeware completely removes unwanted files from harddrive
Date: Sun, 25 Feb 2001 21:55:15 GMT
Anthony Stephen Szopa wrote:
>
> Michael Brown wrote:
> >
> > <SNIP>
> > > >
> > > > I checked the web pages, but I can't find any description for
> > > > how the program ensures that the multiple overwrites actually
> > > > take place. There are several ways it could fail for a naive
> > > > implementation:
> > > >
> > > > - The OS may allocate new disk blocks when writing the patterns,
> > > > leaving the old data unaltered
> > > > - The OS may cache the writes, only actually writing the last
> > > > pattern to disk (or not even that if the file is removed
> > > > afterwards)
> > > > - The SCSI controller may cache the writes
> > > >
> > > > I'm interested in how you've solved this.
> > > >
> > > > Andreas
> > > >
> > > > --
> > > > Andreas Gunnarsson <[EMAIL PROTECTED]>
> > > > +46 31 7014268
> > >
> > >
> > > I don't see what you suggest could happen happening.
> > >
> > I can. My HDD has 2mb cache. Having tested various things I can
> > shove far more data that I should be able to through the HDD. In
> > other words, it ain't writing it all.
> >
> > > Give us a specific example where you have written source code that
> > > says to open a file and write to the file where the computer did
> > > not carry out this instruction.
>
> The code specifically instructs that the file to be overwritten
> is to be:
>
> opened in binary mode at the first byte
> overwritten byte by byte with the given overwrite sequence
> at the end of file the file is closed.
>
> These steps occur with each overwrite sequence pass.
>
> The code instructs the computer to do this.
>
> What you are saying is that even though the code says to do
> this that the OS will ignore this code? For example, the file
> will not be opened? Is that so?
>
> Give us an example of an OS that sane people are still using
> that ignores a hard coded instruction?
Suppose my HDD (either in hardware, or in the driver) stores the last N
"write" operations requested in memory, but doesn't immediatly perform
any disk operation, defering the disk operations till later. Now
suppose I write a few more bytes to those exact same disk locations.
The HDD (or the driver) says, AHA! He's writing to the same place more
than once, there's no need to do two seperate writes, I can just change
the data I have in memory.
Note that "open file" and "close file" operations are things for the OS
to deal with file descriptors, etc, and don't send any kind of requests
to the HDD driver or the hardware.
Curiously, on some unixes, there's a command called "sync" which is
supposed to make the disk driver write out any buffers it has cached.
There isn't, however, any such command or function in dos/win.
--
A solution in hand is worth two in the book.
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 25 Feb 2001 22:19:18 GMT
Subject: Fair(er)play
To my web site, I've just added Gunnar Andersson's new
release of Fairplay, a Playfair hill-climber, dated 2/18/2001.
This version will crack Playfairs in which either an I
or a J has been used in the ciphertext.
Gunnar Andersson is part of the team that cracked all
10 stages of <i>The Code Book Challenge.</I>
He has included in this release six ciphertext examples,
two of which give Fairplay trouble:
ecoo1999.txt An example from www.ecoo.org/sigcs/finals/fin1994p4.html.
hg149.txt Taken from Helen Gaines' book "Cryptanalysis".
hg150.txt - " " -
hg153.txt - " " -
nova.txt From the Nova competition.
stage6.txt Stage 6 of the cipher challenge in "The Codebook"
by Simon Singh.
My P-1.4 cracks four of ciphertexts in roughly this order:
stage6.txt, hg153, hg150, and nova.txt.
It has trouble with hg149 and ecoo1999. I suspect the
hg149 ciphertext is too short for Fairplay to crack. Ecoo1999,
on the hand, includes plenty of ciphertext, but the plaintext
has an high occurrence of an unusual digram.
Let me know if you have better luck than I did cracking
ecoo1999 and hg149, or if you have suggestions about cracking
them.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Date: 25 Feb 2001 22:48:33 GMT
Subject: Re: Fair(er)play
[EMAIL PROTECTED] (JPeschel) wrote:
> but the plaintext
>has an high occurrence of an unusual digram.
>
but he meant to write trigram.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
** 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
******************************
