Cryptography-Digest Digest #776, Volume #13 Fri, 2 Mar 01 05:13:00 EST
Contents:
Re: The AES draft FIPS is out!!! (Paul Crowley)
Re: how long can one Arcfour key be used?? (Paul Crowley)
Re: Rijndael S-box inverse (Paul Crowley)
Re: super-stong crypto, straw man phase 2 (wtshaw)
New web site ("Greg Ofiesh")
Re: RC4 like stream cipher ("Scott Fluhrer")
Re: "RSA vs. One-time-pad" or "the perfect enryption" (Steve Meyer)
Re: The AES draft FIPS is out!!! ("Brian Gladman")
Re: "RSA vs. One-time-pad" or "the perfect enryption" (Nicol So)
Re: "RSA vs. One-time-pad" or "the perfect enryption" (Nicol So)
Re: super-stong crypto, straw man phase 2 (Nicol So)
Re: Urgent DES Cipher source code !!!!! (Frank Gerlach)
How good is the KeeLoq algorithm? (Søren A.Møller)
Re: Keystoke recorder (Frank Gerlach)
ARCFOUR and Latin Squares ("r.e.s.")
Re: => FBI easily cracks encryption ...? (Frank Gerlach)
Re: HPRNG (Frank Gerlach)
Re: How good is the KeeLoq algorithm? (Frank Gerlach)
----------------------------------------------------------------------------
Subject: Re: The AES draft FIPS is out!!!
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Fri, 02 Mar 2001 06:32:58 GMT
"Tom St Denis" <[EMAIL PROTECTED]> writes:
> "Volker Hetzer" <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Check http://csrc.nist.gov/encryption/aes/ .
> > Greetings!
> > Volker
>
> A postscript is available at
>
> http://tomstdenis.home.dhs.org/nist_aes.ps.gz
...since the original is available only in Microsoft Word format.
Thanks Tom!
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: how long can one Arcfour key be used??
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Fri, 02 Mar 2001 06:32:57 GMT
"Tom St Denis" <[EMAIL PROTECTED]> writes:
> "Scott Fluhrer" <[EMAIL PROTECTED]> wrote in message
> news:97knf5$66h$[EMAIL PROTECTED]...
> > > Agreed. Of course putting ASCII into RC4 directly is a "dumb" idea. It
> > > severely cripples the key generation process.
> >
> > Do you have a reference to that?
[snip]
> No, I don't have an exact attack but I feel better using a hash on ascii
> passphrases first. It concentrates the entropy better (in theory) and
> avoids the potential weakness.
Interestingly, CipherSaber uses the fact that passphrases are ASCII to
avoid the RC4 weak keys.
I'd say the RC4 key schedule is slightly inadequate no matter how your
key bytes are drawn, but that if you discard 256 bytes of output after
scheduling as is often recommended, you should be OK with ASCII,
binary, or any string with sufficiently high entropy.
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
Subject: Re: Rijndael S-box inverse
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Fri, 02 Mar 2001 06:32:58 GMT
I worked out the shifts needed to do the inverse affine transformation
in Rijndael with a simple exhaustive search. Remember to do this
*before* applying the self-inverse S-box, rather than after as with
the forward direction :-)
This definition is in Python because I've been learning it, but Python
looks so much like pseudocode that you're unlikely to have trouble
decoding it if you're familiar with C-style operators like | for "or",
^ for "xor" and "<<" for "shift left".
def rot1(t):
return ((t << 1) | (t >> 7)) & 0xFF
affine_box = [None] * 256
for i in range(0,256):
ri = rot1(i)
ai = i ^ ri
ri = rot1(ri)
ai = ai ^ ri
ri = rot1(ri)
ai = ai ^ ri
ri = rot1(ri)
affine_box[i] = ai ^ ri ^ 0x63
inv_affine = [None] * 256
for i in range(0,256):
ri = rot1(i)
ai = ri
ri = rot1(ri)
ri = rot1(ri)
ai = ai ^ ri
ri = rot1(ri)
ri = rot1(ri)
ri = rot1(ri)
inv_affine[i] = ai ^ ri ^ 0x5
--
__
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: super-stong crypto, straw man phase 2
Date: Fri, 02 Mar 2001 00:23:29 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
> William Hugh Murray wrote:
> > "Douglas A. Gwyn" wrote:
> > > William Hugh Murray wrote:
> > > > In any case, most of us do not worry about keeping secrets from
> > > > nation states for a long time.
> > > Well, you should!
> > I admit that I do like to confound authority.
>
> Another point is that "super strong crypto" ought to mean that
> *nobody* can come up with a practical attack; if you allow that
> some "nation-state" can successfully attack a given system, then
> that demonstrates that that system was not "super strong".
Ciphers can be separated into groups according to my scale founded on
Shannon's unicity concept. The groups are trivial, weak, marginally
strong, strong, and very strong. Trivial is up to 128 bits, while strong
is at least 92,593 bits of text.
--
Better to pardon hundreds of guilty people than execute one
that is innocent.
------------------------------
From: [EMAIL PROTECTED] ("Greg Ofiesh")
Subject: New web site
Date: 2 Mar 2001 08:00:15 +0100
I am proud to present my new web site, www.hiddenpoint.com, which provides
free source and binaries to my cryptographic products for Win32 platforms.
--
Posted from IDENT:root@[63.217.229.2]
via Mailgate.ORG Server - http://www.Mailgate.ORG
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: RC4 like stream cipher
Date: Fri, 2 Mar 2001 00:09:40 -0800
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:mJBn6.349$[EMAIL PROTECTED]...
>
> "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
That's just as bad. If the attacker sees the digraph (a, b) on the output,
he then knows that, after that digraph has been output, S[a]==b. And, if
the attacker assumes sy at one point (that is, he cycles through all 256
possible sy values), he can track the value of sy at all times, since he
knows sx at all times and sx is the only thing that modifies sy. Ok, it's
slightly better in that the attacker has to try 256 values of sy, rather
than be given it.
So, for every output, a byte of the array is revealed. And, once the
attacker knows it, he can keep track of it forever. So, after a thousand or
so outputs, the attacker knows the vast majority of the array state...
One of the things I've been playing around with is the RC4 variant:
1. i := i + 1
2. j := j + S[i]
3. swap S[i], S[j]
4. output S[i] + S[j]
(all additions mod 256).
This is regular RC4, except the output has one array dereference removed.
One would expect that this should be relatively breakable, but nothing I
tried has worked so far. Henrick, do you have any clues?
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Steve Meyer)
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Reply-To: [EMAIL PROTECTED]
Date: 2 Mar 2001 08:31:35 GMT
Thanks for posting the various summary URLs. It turns out
the British papers are publicly available at
url: "www.cesg.gov.uk/about/nsecret.htm" (given in the OpenSecret.pdf paper).
But I think there may still be an argument that in fact
R. Merkle invented modern concept of public key encryption, i.e.
two way functions. Although he and colleagues at Stanford were
not able to solve the mathematical problem of finding a two way
function such as RSA.
First, I think it possible to read the 1970 paper "The possibility
of Secure Non Secret Digital Encryption" by J. H. Ellis as
an information hiding paper. Then in 1973(?), I believe R. Merkle took a
Cryptography class from UC Berkeley Professor L. Hoffman and wrote a public
key paper as a class project that he then publicly disclosed by submitting
it for publication (to CACM?), but it then was not accepted and sat around
in the refereeing process. He then later went to Stanford to work with
Professor M. Hellman. I think this history was discussed at a Crypto
Conference in the 90s. I remember it because I was a graduate student at
UC Berkeley at the time (as was L. Adelman - the A of RSA). Does anyone
know if the Merkle paper and Stanford part of this story are available on
the net?
In particular, I think it is possible Merkle class project occurred
before the C. C. Cocke paper date November 20, 1973 entitled
"A Note on 'Non-Secret Encryption'" that seems to me to definitely describe
modern public key cryptography, but uses modern language of mathematical
algorithms completely different from the earlier J.H. Ellis paper.
Does anyone know the exact time line?
There is possibly some other relevant information so maybe this
priority of discovery question will be worthy of study by Historians
of Science.
During this period L. Adelman was working on prime factorization at UC Berkeley
as his Ph.d. project. Also, I believe there was frequent communication
between UC Berkeley professors and Bell Labs and I assume (but do not know)
that many of them were consultants for various secret US spy agencies.
All the UCB faculty would have seen any unusual undergraduate papers
such as Merkle's. I think there is possibility that Merkle discovery was
somehow (implicitly?) communicated to Britain.
Also, in 1969 there had been a different priority of discovery problem
involving then assistant professor J.H. Morris' (now at CMU) involving
Morris' discovery of linear string matching algorithm. UC Berkeley
computer science student R. Rivest (coincidentally later involved in
RSA discovery?). Graduate student Rivest transfered from UC Berkeley
to Stanford and published the linear string matching algorithm with D. Knuth
without giving priority of discovery (or even technical report authorship
to J.H. Morris). Morris complained and was added as an author although I
believe at the time D. Knuth and R. Rivest claimed it was their discovery
because they had performed the algorithm analysis.
/Steve
On 2 Mar 2001 04:25:57 GMT, David Wagner <[EMAIL PROTECTED]> wrote:
>Douglas A. Gwyn wrote:
>>I'm pretty sure I read at
>>least one old IDA-CRD paper in this area, and the prior
>>invention is mentioned in a review of the public state of
>>the art in an internal Agency journal.
>
>Interesting. Do you have any idea what the titles or
>authors on those papers might be?
>It might be interesting to try a FOIA on those to see
>what we can get (with stuff damaging to national security
>redacted, of course).
>
>By the way, another nice (and more detailed) summary is at
> http://rodin.cs.uh.edu/~klong/papers/OpenSecret.pdf
--
Steve Meyer Phone: (415) 296-7017
Pragmatic C Software Corp. Fax: (415) 296-0946
220 Montgomery St., Suite 925 email: [EMAIL PROTECTED]
San Francisco, CA 94104
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: The AES draft FIPS is out!!!
Date: Fri, 2 Mar 2001 09:01:24 -0000
"Paul Crowley" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> "Tom St Denis" <[EMAIL PROTECTED]> writes:
> > "Volker Hetzer" <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > Check http://csrc.nist.gov/encryption/aes/ .
> > > Greetings!
> > > Volker
> >
> > A postscript is available at
> >
> > http://tomstdenis.home.dhs.org/nist_aes.ps.gz
>
> ...since the original is available only in Microsoft Word format.
> Thanks Tom!
The original is available in PDF as well as MS Word format on the NIST AES
site.
Brian Gladman
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Fri, 02 Mar 2001 03:56:38 -0500
Reply-To: see.signature
Steve Meyer wrote:
>
> Also, in 1969 there had been a different priority of discovery problem
> involving then assistant professor J.H. Morris' (now at CMU) involving
> Morris' discovery of linear string matching algorithm. UC Berkeley
> computer science student R. Rivest (coincidentally later involved in
> RSA discovery?). Graduate student Rivest transfered from UC Berkeley
> to Stanford and published the linear string matching algorithm with D. Knuth
> without giving priority of discovery (or even technical report authorship
> to J.H. Morris). Morris complained and was added as an author although I
> believe at the time D. Knuth and R. Rivest claimed it was their discovery
> because they had performed the algorithm analysis.
Do you have a reference to the paper? The Knuth-Morris-Pratt string
matching algorithm is well known and linear time, but I couldn't find
any reference to a paper jointly authored by Knuth, Rivest, and Morris.
According to Rivest's publication list at his website, the only paper he
has coauthored with Knuth seems to be one on string matching.
--
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: Nicol So <[EMAIL PROTECTED]>
Subject: Re: "RSA vs. One-time-pad" or "the perfect enryption"
Date: Fri, 02 Mar 2001 04:00:34 -0500
Reply-To: see.signature
Nicol So wrote:
>
> Steve Meyer wrote:
> >
> > Also, in 1969 there had been a different priority of discovery problem
> > involving then assistant professor J.H. Morris' (now at CMU) involving
> > Morris' discovery of linear string matching algorithm. UC Berkeley
> > computer science student R. Rivest (coincidentally later involved in
> > RSA discovery?). Graduate student Rivest transfered from UC Berkeley
> > to Stanford and published the linear string matching algorithm with D. Knuth
> > without giving priority of discovery (or even technical report authorship
> > to J.H. Morris). Morris complained and was added as an author although I
> > believe at the time D. Knuth and R. Rivest claimed it was their discovery
> > because they had performed the algorithm analysis.
>
> Do you have a reference to the paper? The Knuth-Morris-Pratt string
> matching algorithm is well known and linear time, but I couldn't find
> any reference to a paper jointly authored by Knuth, Rivest, and Morris.
> According to Rivest's publication list at his website, the only paper he
> has coauthored with Knuth seems to be one on string matching.
...............................................^^^^^^^^^^^^^^^
Oops. I meant to say "string sorting".
--
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: Nicol So <[EMAIL PROTECTED]>
Subject: Re: super-stong crypto, straw man phase 2
Date: Fri, 02 Mar 2001 04:12:02 -0500
Reply-To: see.signature
wtshaw wrote:
>
> Ciphers can be separated into groups according to my scale founded on
> Shannon's unicity concept. The groups are trivial, weak, marginally
> strong, strong, and very strong. Trivial is up to 128 bits, while strong
> is at least 92,593 bits of text.
Care to explain the significance of the particular value 92593?
--
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: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: Urgent DES Cipher source code !!!!!
Date: Fri, 02 Mar 2001 10:17:22 +0100
Also, buy a decent book on cryptography like Schneier's "Applied
Cryptography". There you will also find lots of good and bad algorithms
and advice.
------------------------------
From: Søren A.Møller <[EMAIL PROTECTED]>
Subject: How good is the KeeLoq algorithm?
Date: Fri, 02 Mar 2001 09:29:01 GMT
Hi,
I am not a crypto specialist, so I hope somebody here can help me.
Does there exist any analysis og the KeeLoq crypto algorithm?
A bit of info about KeeLoq:
Was invented by Nanoteq, implemented in chips by Exel and now owned and used by
Microchip.
It is a 32 bit block cipher with a 64 bit key.
It is mainly used in remote keyless entry systems for cars, where it is used to
encrypt a counter for
each transmission to validate the transmitter.
The algorithm is sort of secret; you need to buy the decryption part from Microchip (a
$10 disk)
and it comes with a 4 page licence agreement. The encryption part can easily be
derived from the
decryption part.
Søren A.Møller
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: Keystoke recorder
Date: Fri, 02 Mar 2001 10:31:01 +0100
> Only if you are a target of choice.
If a lot of people use the checksum mechanism, then attackers will adapt
their techniques to that.
What we have to understand is that there is no way to retrofit security.
To attempt this is like trying to make a building earthquake-proof,
*after* it has been built. Software engineers need to design for
security in every product, which might be challenged. A good example are
Sandboxes, which contain the actions of a program. Obviously, sandboxes
need to be bug-free themselves and present an interesting target; but it
seems to be much more economical to formally verify a sandbox than to
formally verify every single program on your machine. If M$ wanted, they
could provide a very solid sandbox for 'Doze programs.
On Linux and Solaris (and of couse Java) Sandboxes demonstrated that
this concept is feasible. (An OS-level Sandbox should be much simpler
(==more secure) than on Java, as they do not depend on a correct VM)
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: ARCFOUR and Latin Squares
Date: Fri, 2 Mar 2001 01:47:29 -0800
ARCFOUR uses mod-256 addition in several of its steps.
But for 8-bit arguments, (x+y) mod 256 is just one
of a large number of functions whose value-tables are
symmetric order-256 Latin Squares. (Another is XOR.)
So, consider the even-larger number of ARCFOUR-like
ciphers obtainable by replacing some or all of its
mod-256 additions by operations defined by other
symmetric order-256 Latin Squares. (Many of these,
like XOR, are computable via "built-in" functions,
but others would require some sort of table lookup,
I suppose. If table lookup were used, then we might
also consider generating a random symmetric Latin
Square for the purpose. Hmm... would that be hard?)
All this would be apart from ARCFOUR's final-stage
XOR combiner, so invertibility of the Latin Square
is not an issue.
Is it reasonable to explore this idea further for at
least some of the symmetric Latin Squares, e.g. XOR?
Or am I missing some flaw that would make it a waste
of effort?
--r.e.s.
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp,talk.politics.crypto
Subject: Re: => FBI easily cracks encryption ...?
Date: Fri, 02 Mar 2001 10:45:00 +0100
groj wrote:
Or
> perhaps use a palm-type machine to do the encryption and display the
> characters to be typed.
Physically securing a crypto device is always a precondition of good
security.
But don't expect the Palm to be any better than your PC. Someone could
use a flaw in the PalmOS and quietly suck some data from your Palm the
next time you put it into the cradle.
And if the Palm is used like a PC (with lots of third-party programs)
then there are a lot more opportunities...
And if you are absolutely paranoid, even hardware flaws could provide an
opportunity for attack.
Best security is still one-time pads with paper and pencil...
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: HPRNG
Date: Fri, 02 Mar 2001 10:48:50 +0100
> > Sorry to be nit-picky, but it aint a pseudo random number generator, so
> the
> > name should be HRNG :)
That there is randomness AT ALL, is a matter of religious belief, not
science. Ironically, a lot of agnostics would most probably call quantum
effects "truely random", but I can only call this a religious belief.
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: How good is the KeeLoq algorithm?
Date: Fri, 02 Mar 2001 10:54:02 +0100
"S=F8ren A.M=F8ller" wrote:
> =
> Hi,
> =
> I am not a crypto specialist, so I hope somebody here can help me.
> =
> Does there exist any analysis og the KeeLoq crypto algorithm?
Never heard of it.
> =
> A bit of info about KeeLoq:
> Was invented by Nanoteq, implemented in chips by Exel and now owned and=
used by Microchip.
> It is a 32 bit block cipher with a 64 bit key.
> It is mainly used in remote keyless entry systems for cars, where it is=
used to encrypt a counter for
> each transmission to validate the transmitter.
> The algorithm is sort of secret; =
Secret algorithms are always a bad sign in cryptography.
> you need to buy the decryption part from Microchip (a $10 disk)
> and it comes with a 4 page licence agreement. The encryption part can e=
asily be derived from the
> decryption part.
> =
> S=F8ren A.M=F8ller
Why can't they use a standard algorithm such as DES or RC4 ??
Sounds like the russian car mafia should have a look at that :-))
------------------------------
** 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
******************************
