Cryptography-Digest Digest #596, Volume #11 Fri, 21 Apr 00 14:13:01 EDT
Contents:
Re: The Illusion of Security (Tom St Denis)
Re: OAP-L3: Semester 1 / Class #1 All are invited. (cont.) (Anthony Stephen Szopa)
Problems with NTRU (Tom St Denis)
Re: Number Theory Book (Tom St Denis)
Re: Requested: update on aes contest (David Crick)
Re: Primality Test-how many iterations suffice for n digit number ? (Francois Grieu)
Re: SSL and "man in the middle" attack (Paul Rubin)
Re: SSL and "man in the middle" attack (Paul Rubin)
----------------------------------------------------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: The Illusion of Security
Date: Fri, 21 Apr 2000 17:12:28 GMT
Terry Ritter wrote:
>
> On Fri, 21 Apr 2000 16:41:57 GMT, in <[EMAIL PROTECTED]>,
> in sci.crypt Tom St Denis <[EMAIL PROTECTED]> wrote:
>
> >Mike Kent wrote:
> >>
> >> Tom St Denis wrote:
> >>
> >> > UBCHI2 wrote:
> >> ...
> >> > > Intractable math problem are only in the eye of the beholder. How many of you
> >> > > would have thought that the enigma could be broken?
> >> >
> >> > This is amazingly false.
> >>
> >> Hmmm, it's _very probably_ amazingly false.
> >
> >I would like to think all the math-wizards know what they are doing.
> >Ciphers along the same idea as DES (i.e feistel) have been around for a
> >while.
> >
> >Of course it's entirely possible that all AES ciphers and pre-aes
> >ciphers get broken tommorow. However, that is as likely as monkeys
> >learning speech and taking over the world while we are asleep.
>
> True, the original claims were over the top, but this is way beyond
> what we know in the other direction. We do not know the strength of
> these ciphers. The designers and reviewers do not know the strength
> of these ciphers. None of us *can* know strength with respect to
> opponents we do not know and whose knowledge and resources we also do
> not know.
>
> There exists no basis for asserting that breaking these ciphers is
> "unlikely." We have no testable probability distribution for the
> breaking of ciphers. If the only thing we have to go on is the
> limited published experience, we might well say that every algorithmic
> cipher is likely to be broken eventually. And that is precisely the
> opposite of your unproven assertion that breaking AES is unlikely.
True, but we know (or should I say 'they know') alot about various
metrics to attack ciphers. So we can begin. We can tell for example
that a cipher is weak because we can break it. Given all the talent in
the world if no one comes up with a metric to break a new cipher, then
for that time being it's secure.
Of course of all the ciphers used since the 70's none of them have yet
been broken. So that's a good track record so far....
Tom
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: OAP-L3: Semester 1 / Class #1 All are invited. (cont.)
Date: Fri, 21 Apr 2000 09:40:22 -0700
James Felling wrote:
>
> > <giant snip>
> >
> > I will prove you do not know what you are talking about by you
> > simply answering this question:
> >
> > The OAP-L3 encryption software uses a random number generator.
> > Now which of the following is the most correct and most
> > comprehensive description of this random number generator that
> > it uses: which is the description that results in the random
> > numbers used in the encryption process?
>
> >
> > 1) The process that outputs the random digits from the MixFiles,
or
> >
> > 2) the process that results in the OTP files?
>
> Well the best way to answer that is "neither"( or "both" -- depends
upon how I look at it). I
> agree that the stream data is generated primarially by process #2.
However it still uses
> data from process #1 to produce the mix files which are then used by
process #2. If one
> examines the crypto literature you will find many algorithims that
have comentaries by skilled
> people along the line of "this section of the algorithim is weak --
it does not do X properly
> -- I have found no attack to exploit this property" and this is
enough to withdraw the
> algorithim from serious consideration. Why should your program be
judged upon a different
> standard?
>
> >
> >
> > Now define precisely what your supposed flaws are and what is the
> > exact nature of these "artifacts" you allege?
>
> Ok since you have obviously not done even a textbook analisys of your
mix file generation
> process I will.
> I am using your own names for the subprocesses.(P.S. this is not an
exhaustive list of what I
> have found, but it is simply the result of a half hour of simple
kindergarten cryptoanalisys)
>
> We start with a file F of all possible 1 to 10 sequences.I shall
number them F(1),F(2),
> ....,F(10!)
>
> 1) Scramble -- since all other mixing ops are external( they affect
the order in which the
> F(i)'s are presented) Scramble is effectively orthogonal to all other
MixFile creation
> steps.This means we can effectivly treat all other steps as modifying
the set S=
> Scramble(F(1)), Scramble(F(2)), ....., Scramble(F(10!))
>
> 2) Mix -- The "Mix" operation doesn't do a very good job of it. M(i)=
the ith sequence of
> Mix(S) has the following properties M(j+105*n)= S(j+105*n) with
probability . (n>=0, and j=
> first mix value). Since there are further steps this is less bad than
it seems.
>
> 3) Redistribute -- This creates 14 files I will denote them as T(1)
to T(14), and then T(k,m)
> = themth member of Tfilek.
> This is aparently accomplished as follows T(k,m)= M( (k-1)*259200 + m
).
>
> 4) Shuffle. This Permutes the Tfiles, then data are taken from them
in the permuted order to
> generate the mixfile.call this permutation p(x).
>
> Attack vs mix file generation.
>
> Sincej>=1, T(1,1)= Scramble(F(1)) , and T(8,1)=Scramble(F(1814401))
this meand that within
> the first 14 sequences in the Mix files we have two sequences that
are known, this will occur
> regularly within the mix file where within 14 digits at easily
computable points in the file 2
> sequences (Scrambled) with known chjaracter exist. Because of this we
have very good odds of
> recovering both scramble, and some very good information on P(x) in
addition. Further, if
> j>1 we will easily recover scramble as T(1,2) will occur 14 spots
later in the file and will
> be a single rearangement swap different from T(1,1)
> .
>
> As you can see the Mixfile.otp has a significant amount of
exploitable structure -- enough to
> allow recovery of its generating keys in comparitively short order.
Since this is the case,
> it seems likely to me that at least some of this structure could be
exploited by an analyst
> working the whole key backward.
>
> >
> >
> > Let me end with this:
> >
> > The accepted test of the security of an encryption process is not
> > what Mr. Huuskonen has asked for. The accepted test is that it is
> > assumed that the cracker knows every thing there is to know about
> > the algorithm, and that the cracker has a substantial amount of
> > plain text and the corresponding encrypted text. From this
> > it is demanded that the cracker use this information and knowledge
> > to crack the software. This is hardly what Mr. Huuskonen is asking
> > for: he is essentially asking for the key once removed.
>
> Yes, to a degree he is. But the same structures that allow him to
attack your mix file will
> exist, to a lesser degree in the final output. My guess is that the
Mix files provide about
> 20-30 bits of randomness per each(assuming my attack cannot be
refined). This puts the
> randomness of your code somewhere in the neigborhood of a 90 to 100
bits( tops) when you
> factor it all in. I will be generous and say you are as secure as
3DES(112 bits). Why should
> we use your code in prefrence to 3DES?
This is nothing but BS and I think you know it.
Let's keep it simple then build from there.
Let's say we start with the original encryption data file: the
3,628,800 ten-digit permutations consisting of the digits 0 - 9
with no repeats. In this original encryption file the permutations
are arranged in ascending order.
Let's just run the Shuffle process once. The first 259,200 arrays
are read from the original encryption data file and written to
TFile1. The next 259,200 arrays are read and written to TFile2.
The next 259,200 arrays are read and written to TFile3, etc. until
there are TFile1 - TFile14.
The user then inputs a true random 14 number sequence of the
numbers 1 - 14 with no repeats. For your information there are
14! = over 87 billion possible unique sequences of the numbers
1 - 14.
Then these 14 TFiles are interleaved one array at a time according
to this 14 number sequence.
The resulting output file, we'll call it, MixFile1, is one of over
87 billion possible.
You say it will be easy to guess the order of the permutations in
this MixFile1? How will you do it? There is only one way to do
it: trial and error by using all the 87 billion 14 number
sequences. (Because the input was true random you cannot get around
this by any other means.)
So, after you have produced each of these over 87 billion possible
MixFile1's you store them confident that you have certainly produced
the correct MixFile1 among the over 87 billion you have generated and
stored.
Okay.
Now let us run the Shuffle process again on MixFile1 using another
true random 14 number sequence of the numbers 1 - 14 with no repeats
and call the output again, MixFile1. As above, there are over 87
billion possible sequences.
But there are now over (87E9)^2 possible 28 number sequences of two
sequences of 14 numbers 1 - 14 in a row.
So now you have to produce and store over (87E9)^2 MixFile1's but
you can still be certain that at least one of these (87E9)^2
MixFile1's is the correct one.
Let's say I repeat the process 50 times in total. This means that I
have shuffled the original encryption data file 50 times using one
of over 87 billion 14 number sequences with each shuffle. Thus the
total user input is 50 true random 14 number sequences of the numbers
1 - 14.
This means that there are over (87E9)^50 possible 50 true random 14
number sequence sequences in a row and that the actual input used is
only one of these over (87E9)^50 sequences.
For you to determine the final MixFile array sequence after 50 runs
of the Shuffle process with absolute certainty that at least one of
the MixFiles is the actual one, you will have to produce over
(87E9)^50 MixFiles, and store them.
Let's see, if each MixFile is over 18MB you will need enough storage
for 18E6 * (87E9)^50 = 1.5E459 bytes.
But you can at least be sure you have the right sequence somewhere
among them all.
Your problem now is: which one is it?
Let's say you need three such MixFiles and that the user uses their
last MixFile1 after 50 Shuffle runs to begin 50 more shuffle
processes to produce a MixFile2, then run 50 more processes on this
last MixFile2 to produce a MixFile3.
Similarly as shown in the Theory and Processes Help Files, the odds
of duplicating MixFile1 with certainty is one in (87E9)^50.
But for duplicating MixFile2 it is one in ((87E9)^50)^2 = (87E9)^100.
For duplicating MixFile3 it is one in ((87E9)^50)^3) = (87E9)^150.
And finally, to guess with certainty, all three MixFiles it would be
(87E9)^50 * (87E9)^100 * (87E9)^150 = (87E9)^300.
Tell us how you are going to guess the one chance in (87E9)^300 of
getting the correct three exact MixFiles? (Not to mention store all
of them.)
We really want to know?
Give up?
Give up.
And we haven't even considered subsequent processing of the random
binary number files produced from the MixFiles.
Now, what is it you don't understand about unbreakable?
(I bet you would you like me to sneak you the key right about
now, eh?)
See, how plain it is in layman's terms. This is why I say that the
entire software package is understandable by anyone with average
intelligence.
Now what exactly don't you understand?
(And whatever it is you'd like to say can you say it in laymen's terms
so everyone can understand you?)
Thank you.
(All of this is just as simply explained in the Help Files at
http://www.ciphile.com)
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Problems with NTRU
Date: Fri, 21 Apr 2000 17:19:14 GMT
I don't like the way NTRU presents themselves. Knocking RSA, ECC and
Elgamal as bad, slow and insecure....
Somethings fishy.
Plus they push the idea that you should encrypt data directly with their
algorithm instead of a hybrid-system. Is NTRU really that fast?
Tom
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: Number Theory Book
Date: Fri, 21 Apr 2000 17:34:09 GMT
Antoine Bruguier wrote:
>
> Hi,
> I'm looking for a number theory book, explaining from the beginning. But
> I konw stuff like Zn is a field when n is prime, Fermat's theorem etc.
> Any suggestions ?
>
Try "Fundamentals of Number Theory" (ISBN 0-486-68906-9), or Knuth v1
:)
Tom
------------------------------
From: David Crick <[EMAIL PROTECTED]>
Subject: Re: Requested: update on aes contest
Date: Fri, 21 Apr 2000 18:50:25 +0100
Terry Ritter wrote:
>
> >>I know that you have stated that you are opposed to multiple selections.
> >>Would your position on this issue be influenced by a pair of selections
> >>distinguished by performance? Say Twofish or RC6 as primary, and R++ as
> >>secondary?
> >
> >No. One standard. Only one. Not two. One.
>
> Right. One standard. Consisting, for example, of every cipher not
> yet explicitly broken.
75% of the attendees at AES3 who filled in the anonymous
questionnaire voted for a single algorithm over multiple
ones.
With regards to the original poster quoted above, the full results
of the questionnaire also give the rankings of various combinations
of ciphers, depending on how many there were to be hypothetically.
http://csrc.nist.gov/encryption/aes/round2/conf3/AES3FeedbackForm-summary.pdf
David.
------------------------------
From: Francois Grieu <[EMAIL PROTECTED]>
Subject: Re: Primality Test-how many iterations suffice for n digit number ?
Date: Fri, 21 Apr 2000 19:50:07 +0200
[EMAIL PROTECTED] wrote:
> I know that when I implement MilRab for one base - prob that I
> will fail 0.25, in Lehman(Euler) 0.5; Lucas 5/16, Frobenius 1/7710
>
> R.G.E.Pinch suggests that I should take n bases for n digit number.
>
> Any other suggestions, recomendations ?
According to Robert D. Silverman (*), citing an article by
I. Damgard, P. Landrock et C. Pomerance, for numbers 512 bits
or more, 8 Miller-Rabin tests are enough for an error
probability below 2^-100.
It pays to first test that the GCD with 2*3*5*7*11*13 is 1, then
use 2 as a Miller-Rabin witness (the test can be made faster).
I believe (I have no reference) using the small primes 2,3,5,7,11,
13,17,19 as test values [or random distinct small primes to
guard against someone even attempting to forge a counterexample]
will gives robustness at least equivalent to random values, and
further simplifies the test.
Francois Grieu
(*) Robert D. Silverman: Fast Generation of Random, Strong
RSA Primes, in CrytoBytes Volume 3, No. 1, available online from
<http://www.rsasecurity.com/rsalabs/cryptobytes>
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: SSL and "man in the middle" attack
Date: 21 Apr 2000 17:59:16 GMT
In article <[EMAIL PROTECTED]>,
Francois Grieu <[EMAIL PROTECTED]> wrote:
>I am looking for references on the security of the SSL protocol against
>the "man in the middle" attack (*) in the context of online commerce
>using credit card info keyed-in by the customer.
You could just try reading the spec, RFC 2246.
>I have heard conflicting reports, ranging from
>
>1) SSL offers no protection against the man in the middle attack
False.
>2) a man in the middle attack can be mounted simply with knowledge of
>the secret key and certified public key of any SSL server,
True. But if the attacker knows the secret key, s/he can simply read
the traffic and not bother with MITM.
>which is readily available to hackers;
I hope not! The public key is available, but the secret key is
supposed to be protected. I don't know of many cryptosystems that are
secure against a "known secret key" attack.
>and there is no infrastructure in the
>leading browsers to revoke server public key certificates
False. For example, in MSIE 5, select Tools | Internet Options |
Advanced, and click "Check for certificate revocation" in the security
section.
>[variants: no workable/working infrastructure]
Closer to the truth. Most people don't turn this option on.
It can slow down browsing.
>3) all browsers check the domain name in the server's certificate
>matches the actual domain name reported by the DNS system, so the
>attacker needs to attack the DNS protocol as well;
True.
>this limits the
>attack to a location close (in the network sense) to the end user.
Well, not really. One common attack is to simply hijack the domain
at the NIC. That can be done from anywhere, if the domain owner
chose a bad password or something.
>4) and this will work only if the user does not check the server
>identification info, which the leading browsers display clearly.
Basically true, though there are frame spoofing attacks and stuff like that.
>5) SSL is safe (source: sites using SSL :-)
I use it and would say it's pretty safe :). Even if there was an MITM
attack that worked, you'd need an awful lot of network bandwidth, plus
a large DNS hijack, to mount it against a big SSL site (say amazon.com),
and credit card numbers simply aren't valuable enough.
If you're trying to protect -really- valuable traffic with SSL, the
right way to do it is with certificate-based authentication at both
ends, not just the server end. And the secret keys should be stored in
secure hardware tokens, not disk files.
>Any serious study out there ?
Yes.
>Comments and pointers welcome.
See the other posts, and the RFC.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: SSL and "man in the middle" attack
Date: 21 Apr 2000 18:05:46 GMT
In article <[EMAIL PROTECTED]>,
Francois Grieu <[EMAIL PROTECTED]> wrote:
>Thanks to Lyalc <[EMAIL PROTECTED]> and
>Jonathan Thornburg <[EMAIL PROTECTED]>
>for pointing
>> Web Spoofing: An Internet Con Game
>> Edward W. Felten, Dirk Balfanz, Drew Dean, and Dan S. Wallach
>> Technical Report 540–96 (revised Feb. 1997)
>> at <http://www.cs.princeton.edu/sip/pub/spoofing.html>
>
>The paper however does not discuss how SSL is affected.
>
>I believe in theory it might be possible to guard against spoofing, but
>a lot of assumptions have to be made, including
>- software on the user's PC is trusted
Trusted from what? Yes, insecure browsers can leak info, e.g. Netscape 1.0.
>- user can appropriately decide to disclose credit card info or not on
>the basis on the merchant's identity as displayed by the trusted software
This isn't an SSL issue.
>- user can distinguish between such trusted display from display
>generated by untrusted sources (e.g. GIF, javascript..)
Huh? The browser displays the site content in a window surrounded by
a box with a navigation bar, a lock icon, etc. This generally can't
be spoofed by javascript or gif's.
>Clearly, only a tiny minority of web users are in this situation, but at
>least large-scale attacks could be detected by a few carefull users.
What kind of large-scale attack?
>I wonder if SSL even enables that. For a start, do Netscape or Explorer
>show the certified identity of a server when SSL is used, and how is one
>supposed to know this display is genuine ?
The browser compares the hostname in the navigation bar against the
hostname in the certificate. If they don't match, the browser pops
a warning dialog saying the connection may be insecure, and prompting
the user to choose whether to continue or not.
Why are you asking this stuff?
------------------------------
** 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 (and sci.crypt) via:
Internet: [EMAIL PROTECTED]
End of Cryptography-Digest Digest
******************************
