Cryptography-Digest Digest #196, Volume #14 Sat, 21 Apr 01 00:13:00 EDT
Contents:
MDS question ("Tom St Denis")
Re: "UNCOBER" = Universal Code Breaker (newbie)
Re: "UNCOBER" = Universal Code Breaker ("Tom St Denis")
Re: Minimal Perfect Hashing (wtshaw)
Re: Will this defeat keyloggers ? (Paul Rubin)
Re: Minimal Perfect Hashing (Paul Rubin)
Re: Note on combining PRNGs with the method of Wichmann and Hill ("Bryan Olson")
Re: First cipher ([EMAIL PROTECTED])
Re: Rabin-Miller prime testing (Bryan Olson)
Re: Minimal Perfect Hashing ("Dann Corbit")
Re: First cipher ([EMAIL PROTECTED])
Re: First cipher ([EMAIL PROTECTED])
Re: what crypt algo is the smallest to code? (Rob Warnock)
----------------------------------------------------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: MDS question
Date: Sat, 21 Apr 2001 02:10:32 GMT
>From empiracle tests a 4x4 MDS must have at least three unique elements.
Does this grow linearly, i.e must a 8x8 have at least 7?
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Fri, 20 Apr 2001 22:13:11 -0300
It's infinite sequence of 1111111111111111111111111111
let r infinitely random
let s= r (-1) inverse of r (random
r Xor x = 1111111111111111111111111111111
infinitely predictable!!!!!!!!!!!!!!!
is it random????????
is the result random??????????
READ WHAT I'M TELLING
Tom St Denis wrote:
>
> "newbie" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > 10100010010 is random string
> > the inverse 01011101101 is random too.
> > but if you Xor the two random string you will find
> > 111111111111111111111111111111
> > random + random does not give you random result.
> > random + non random does not give you 100 % random result.
> > You have to meet some conditions before claiming that those equality are
> > true.
>
> You still don't get it. If the chance of "11111111" of occuring is 1/256
> then it's random!!
>
> Christ 11111111 is equal to 255, so you are saying that no truly random
> number generator can't output 255? Then how can it be random?
>
> You're plain mad.
>
> Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: "UNCOBER" = Universal Code Breaker
Date: Sat, 21 Apr 2001 02:21:45 GMT
"newbie" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> It's infinite sequence of 1111111111111111111111111111
> let r infinitely random
> let s= r (-1) inverse of r (random
>
> r Xor x = 1111111111111111111111111111111
> infinitely predictable!!!!!!!!!!!!!!!
> is it random????????
> is the result random??????????
> READ WHAT I'M TELLING
If your message is ***always*** zero and your pad is ***always*** one then
yes it's not random.
If perchance the pad is equal to the compliment of your message, then it's
random.
READ WHAT I'M TELLING YOU
Tom
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Minimal Perfect Hashing
Date: Fri, 20 Apr 2001 20:17:50 -0600
In article <fNWD6.608070$[EMAIL PROTECTED]>, "Francois
St-Arnaud" <[EMAIL PROTECTED]> wrote:
>
> Yes. I neglected to repeat this important criterion in the requirements. It
> should be "minimal", meaning that n plaintexts will map to 0..n-1 ciphers
> with no collisions at all. For my application, n = 2^48, x and y in
> [0..2^48-1].
>
> Regards,
>
> Francois St-Arnaud
All hashes have collisions. You fill not find what you want for it
violates that truth.
If you have a hash, the output will have less information in it that the input.
--
Ah, so! Chop suey on a bagel. Now...say, "So Sorry."
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Will this defeat keyloggers ?
Date: 20 Apr 2001 20:01:04 -0700
[EMAIL PROTECTED] (Nemo psj) writes:
> You could just make a keypad on the screen and have them clikc in the
> passphrase.... In this way the only keys registerd are the mouse clicks.
The mouse clicks raise windows events just like keystrokes do.
So the logger might also log the mouse clicks.
However, if the letters/digits on the keypad were displayed in a
random order and changed after every click, that also sounds like
a good solution.
------------------------------
From: Paul Rubin <[EMAIL PROTECTED]>
Subject: Re: Minimal Perfect Hashing
Date: 20 Apr 2001 20:01:51 -0700
"Francois St-Arnaud" <[EMAIL PROTECTED]> writes:
> Yes. I neglected to repeat this important criterion in the requirements. It
> should be "minimal", meaning that n plaintexts will map to 0..n-1 ciphers
> with no collisions at all. For my application, n = 2^48, x and y in
> [0..2^48-1].
What you're asking for is not a hash. Type "Hasty Pudding Cipher" into
Google and you'll find what you are looking for.
------------------------------
From: "nospam"@"nonsuch.org" ("Bryan Olson")
Crossposted-To: sci.crypt.random-numbers
Subject: Re: Note on combining PRNGs with the method of Wichmann and Hill
Date: Sat, 21 Apr 2001 03:29:36 GMT
In article <[EMAIL PROTECTED]>, Mok-Kong Shen wrote:
>
>
>Bryan Olson wrote:
>>
>> Mok-Kong Shen wrote:
>> >Bryan Olson wrote:
>> >>
>> >> Mok-Kong Shen wrote:
>> >> > Mok-Kong Shen wrote:
>> >> > > The PRNGs are assumed to be independent (I forgot to
>> >> > > explictly say that) and uniform.
>> [Snip...]
>> >> > Addendum: The scheme of Wichmann and Hill is intended
>> >> > to get a more uniform stream from a number of not well
>> >> > uniform streams.
>> [...]
>>
>> [Bryan]
>> > You now say the
>> > intentions contradict what you just said was assumed.
>>
>> > 'What' I said contradicts 'what' I assumed?
>>
>> Yes. The edits above should make that clear.
>
>You snipped the part that is essential for the point
>you raised here.
Sorry, I didn't mean to snip any point.
> So I reproduce that below:
>
> Addendum: The scheme of Wichmann and Hill is intended
> to get a more uniform stream from a number of not well
> uniform streams. The assumption I made above that
> the PRNGs are uniform is for discussion of the
> theoretical point you raised which I quote below:
>
> The modification destroys an important property of
> the basic combination method: as long as the streams
> are independent, if any of the streams are uniform
> then the sum is uniform.
>
> So in that situation we assume that there are uniform
> streams to start with.
>
>Essential is my last sentence above. The quote from
>you mentioned 'uniform'. Actually the scheme of Wichmann
>and Hill is intended to get more uniform streams from
>not so uniform ones. So we couldn't, strictly speaking,
>argue about your quote (and hence your claimed
>'distruction') at all, since we don't have any 'exactly'
>'uniform' streams.
Nonsense. Your note implies cryptographic use, not the
original intended use.
>(Should I on this ground have said that
>the material of your quote is 'irrelvant' and stopped the
>discussion on that with you?) On the other hand, it is
>obvious that the theorem involved in you quote above is
>'theoretically' interesting, for it forms the base on
>which the scheme of Wichmann and Hill is oriented (just
>like a good pseudo-random bit sequence is oriented
>towards the theoretical ideally random sequence).
The theorem is important. It also has a significant
cryptographic corollary: if there is any one stream the
attacker cannot distinguish from uniform, then he cannot
distinguish the Wichmann-Hill combination from uniform
(again assuming the streams are independent). That is false
for your scheme. We can also show that the attacker cannot
predict the Wichmann-Hill sum any more accurately than he can
predict the least predictable of the streams. Again this is
false for your scheme.
>Therefore, in order to avoid general readers wondering
>why we started to discuss about 'uniform' while there is
>no exact uniformity present, I put out the addendum. Is
>that clear to you now?
It's nonsense still.
>> >> No. You stated a bogus result. What evidence we have
>> >> indicates that your it's false.
>> >
>> >'What' is the bogus result?
>>
>> "thus rendering the analysis more difficult." There is no
>> support for this assertion in the note or in the follow-ups.
>
>The original Wichmann and Hill scheme gives e.g.
>
> R = r1 + r2 + r3 mod 1
>
>The modified one gives
>
> R = c1*r1 + c2*r2 + c3*r3 mod 1
>
>What the opponent has is R. Assuming he had a method
>to get the components r1, r2 and r3 from R, he would
>have more difficulty to do in the second case, since
>the c1, c2 and c3 are unknown to him, isn't it?
Are you joking? What is the justification for that
assumption? Can you in general get the components from the
sum? Can you in realistic cases?
If you are asked to compare schemes A and B, you can't
simply assume scheme A is broken and conclude scheme B looks
better. Cryptosystems don't fall just because you assume
they do.
Still a completely bogus result. No justification.
> (He
>has somehow to determine these unknowns.) One could
>certainly dispute about how much is that 'more'. But
>that there is some 'more' should be evident.
What is evident is that you have not looked seriously at the
properties of the Wichmann and Hill scheme.
>> >'What' is the evidence?
>>
>> As stated in the strand. The modification throws away
>> important properties of the scheme. The resulting stream
>> can come out worse than an individual component stream.
>
>Partly covered above. For the rest: See my follow-up
>to Brian Gladman, who claimed essentially the same as
>you but in a more concrete way. I have asked him to redo
>his chi-square tests and present the results.
You were the advocate of that particular test. Where are
your results?
>As said
>there, I never exclude the possibilty of my making
>blunders, anywhere, anytime. But I want to see concrete
>refutations rather than fuzzy categorical claims of
>my being wrong without any accompanying supporting
>materials.
Utter hypocrisy. Your claims have only nonsense behind
them. There's nothing fuzzy in the theorems we can show
about Wichmann- Hill.
--Bryan
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: First cipher
Date: Fri, 20 Apr 2001 18:47:40 -0800
David Wagner wrote:
>
> >How about something a little more
> >useful, like pointers on how to cryptanalyze my cipher so I don't bug
> >the group with the obvious?
>
> Unfortunately, I don't know of any single good book on cryptanalysis,
> but Biham and Shamir's _Differential cryptanalysis of the Data Encryption
> Standard_ is a pretty darned good starting point. I've heard that this
> book may be out of print; if so, the next-best alternative is to go to
> Biham's web page and read his papers on differential and linear cryptanalysis.
I found that paper. It _is_ a darned good starting point. Let me mull
over
that awhile.
Thanks.
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Rabin-Miller prime testing
Date: Fri, 20 Apr 2001 20:40:26 -0700
"Terry L. Cowart" wrote:
> If you are verifying someone else's numbers, it seems there is a
> certain level of distrust in the first place. If that distrust is not
> misplaced, it is possible the other participant has created a number
> that is the composite of exactly two large primes. In that case, it
> would seem that any nondeterministic test for primeness would be
> unlikely to conclude that the suspect number was indeed a composite,
> since the number has only two factors.
Miller-Rabin isn't fooled by composites with two prime factors.
> Since this is not my primary expertise, what is the current theory on
> primality tests for such (2 prime factors) composite numbers?
I don't know of any efficient method to determine whether a
composite has exactly two prime factors. But we can certainly
distinguish such composites from primes.
--Bryan
------------------------------
From: "Dann Corbit" <[EMAIL PROTECTED]>
Subject: Re: Minimal Perfect Hashing
Date: Fri, 20 Apr 2001 20:54:46 -0700
"wtshaw" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <fNWD6.608070$[EMAIL PROTECTED]>, "Francois
> St-Arnaud" <[EMAIL PROTECTED]> wrote:
> >
> > Yes. I neglected to repeat this important criterion in the requirements.
It
> > should be "minimal", meaning that n plaintexts will map to 0..n-1 ciphers
> > with no collisions at all. For my application, n = 2^48, x and y in
> > [0..2^48-1].
> >
> > Regards,
> >
> > Francois St-Arnaud
>
> All hashes have collisions. You fill not find what you want for it
> violates that truth.
> If you have a hash, the output will have less information in it that the
input.
Unless (of course) it's a perfect hash.
Consider the following hash for 32 bit unsigned integers:
f(u) = u
A perfectly valid hash function.
You could get gperf from GNU and form a perfect hash for any input set. Of
course, if the inputs change, all bets are off.
--
C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html
"The C-FAQ Book" ISBN 0-201-84519-9
C.A.P. FAQ: ftp://cap.connx.com/pub/Chess%20Analysis%20Project%20FAQ.htm
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: First cipher
Date: Fri, 20 Apr 2001 19:04:25 -0800
Scott Fluhrer wrote:
>
> <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> > David Wagner wrote:
> > >
> > > >Supposedly, if the S-box is reversible and the number of bits per table
> > > >entry is large, then the probability of a random S-box having one or
> > > >more bits that are linear functions of the address bits is low.
> > >
> > > (... if the S-box is large enough, and is selected at random.)
> > >
> > > >Ah, but at one time each one of them was a neophyte just like me.
> > >
> > > Yes, but designing new ciphers is unlikely to be the best way to
> > > learn how to design new ciphers. (Sounds counter-intuitive, but
> > > it seems to be true.)
> >
> > I'd be glad to start paying my dues on the cryptanalysis end of things.
> > The problem seems to be finding a consolidated, unified guide in the
> > literature.
>
> Why don't you get started on your own cipher. 16 rounds may be too tough
> for a neophyte, so you may want to reduce it to 4-6. You'll also need to
> fill in the details (eg. exactly what permutation is 'permute'?) I've
> already given you hints about one possible line of attack...
>
> --
> poncho
So, you can't learn how to write good ciphers by writing ciphers but you
can learn good cryptanalysis by doing cryptanalysis ?? ;}
I think I'll read over a differential analysis paper suggested by David
Wagner
before going any further. Then I'll try to analyze a shortened version
of
the cipher I posted after filling in the details. I'm finding that there
are a lot of papers on cryptanalysis out there, just not a good
textbook.
Let me go off and read for awhile...
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: First cipher
Date: Fri, 20 Apr 2001 19:09:58 -0800
Tom St Denis wrote:
>
> <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> > Tom St Denis wrote:
> > >
> > > <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > > > "M.S. Bob" wrote:
> > > > >
> > > > > [EMAIL PROTECTED] wrote:
> > > > > >
> > > > > > "M.S. Bob" wrote:
> > > > > > >
> > > > > > > [EMAIL PROTECTED] wrote:
> > > > >
> > > > > As his says in his self-study course, there is no one good text on
> > > > > cryptanalysis of modern ciphers.
> > > >
> > > > This is somewhat sad, given that there are textbooks out
> > > > there on some extremely complicated scientific/mathematical analysis
> > > > problems.
> > >
> > > Not really. Analysis is just one of those subjects that never ends.
> Find
> > > one good text that answers all questions about god? Or about how the
> human
> > > brain works, or how to factor large integers, or how to remove money
> from
> > > society or how to make good tv programs?
> > >
> > > Answers to these questions will vary over time....
> > >
> > > Tom
> >
> > You can teach an electrical engineering student the basics of circuit
> > analysis
> > by analyzing simpler problems and progressing to more complex problems.
> > Hopefully
> > by the end of the curriculum, the fire will light and the student will
> > be able
> > to approach a wide range of analysis problems and design circuits on
> > his/her own.
> > In spite of the best instruction, some students will never be able to
> > move
> > from analysis to design BUT there is a progressive method of teaching an
> > approach to what are sometimes very complex design or analysis problems.
> > I'd like to think that the crypto field, like any scientic endeavor, has
> > a similar method of passing along its cumulative knowledge to serious
> > students, and not just "go do a hodge-podge
> > self study course and come back when you've taught yourself everything".
>
> Given say an hour I could teach you how to perform differential
> cryptanalysis (which is basically the only attack I really get). But that
> takes time and money. You can learn diff (etc...) cryptanalysis in school,
> just depends on what school.
>
> The bigger problem is that you may resist 100s of attacks but someone may
> find another attack. Saying something is secure means it resists known
> attacks only. Nothing can be provably secure except the OTP.
>
> Tom
If you have the time to show an example of a differential attack (use
the
cipher I posted with a random P-box and S-box with only 4 rounds for
instance)
then that would be helpful.
David Wagner vectored me to a good differential cryptanalysis paper and
I've
found others from that starting point. There seem to be a lot of
cryptanalysis
papers out there, just nothing in textbook form.
I'm going to go read.
Thanks.
------------------------------
From: [EMAIL PROTECTED] (Rob Warnock)
Subject: Re: what crypt algo is the smallest to code?
Date: 21 Apr 2001 04:09:48 GMT
diediedie <[EMAIL PROTECTED]> wrote:
+---------------
| encryption/decryption speed is not of any importance,just the size
| of the actual crypt code, what would be suggested (for a public/secret
| key crypter)? RSA perhaps?
+---------------
RSA is the most well-known of the "tiny code" algorithms. In fact, you can
buy T-shirts with RSA-in-Perl (4 lines) in both text and machine-readable
barcode, along with the obligatory warning: "This shirt is classified as
a munition and may not be exported from the United States of shown to a
foreign national." See:
<URL:http://www.cypherspace.org/~adam/uk-shirt.html>
<URL:http://www.obscura.com/~shirt/> [note: couldn't DNS-resolve this]
<URL:http://www.cypherspace.org/~adam/rsa/> also has a 3-line version:
#!/bin/perl -sp0777i<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<j]dsj
$/=unpack('H*',$_);$_=`echo 16dio\U$k"SK$/SM$n\EsN0p[lN*1
lK[d2%Sa2/d0$^Ixp"|dc`;s/\W//g;$_=pack('H*',/((..)*)$/)
and a 2-line version:
print pack"C*",split/\D+/,`echo "16iII*o\U@{$/=$z;[(pop,pop,unpack"H*",<>
)]}\EsMsKsN0[lN*1lK[d2%Sa2/d0<X+d*lMLa^*lN%0]dsXx++lMlN/dsM0<J]dsJxp"|dc`
-Rob
p.s.
If you're also interested in very small symmetric-key algorithms, consider
TEA <URL:http://www.ftp.cl.cam.ac.uk/ftp/papers/djw-rmn/djw-rmn-tea.html>:
void code(long* v, long* k) {
unsigned long y=v[0],z=v[1], sum=0, /* set up */
delta=0x9e3779b9, n=32 ; /* a key schedule constant */
while (n-->0) { /* basic cycle start */
sum += delta ;
y += (z<<4)+k[0] ^ z+sum ^ (z>>5)+k[1] ;
z += (y<<4)+k[2] ^ y+sum ^ (y>>5)+k[3] ; /* end cycle */
}
v[0]=y ; v[1]=z ; }
(...or XTEA, which significantly strengthens it.)
Or for something stronger, <URL:http://www.cypherspace.org/~adam/rsa/rc4c.html>
(often called ARCFOUR, presumed to be the same as RSA Inc.'s RC4):
#define S,t=s[i],s[i]=s[j],s[j]=t /* rc4 key <file */
unsigned char s[256],i,j,t;main(c,v)char**v;{++v;while
(s[++i]=i);while(j+=s[i]+(*v)[i%strlen(*v)]S,++i);for(
j=0;c=~getchar();putchar(~c^s[t+=s[i]]))j+=s[++i]S;}
=====
Rob Warnock, 31-2-510 [EMAIL PROTECTED]
SGI Network Engineering <URL:http://reality.sgi.com/rpw3/>
1600 Amphitheatre Pkwy. Phone: 650-933-1673
Mountain View, CA 94043 PP-ASEL-IA
------------------------------
** 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
******************************
