Cryptography-Digest Digest #898, Volume #12 Wed, 11 Oct 00 16:13:01 EDT
Contents:
re: working with huge numbers ("DeSilva")
Re: Rijndael implementations (David Crick)
Re: Why wasn't MARS chosen as AES? (JCA)
Re: Rijndael implementations ("Paul Pires")
Re: CPU's aimed at cryptography (Michael Torla)
Re: Police want help cracking code to find Enigma machine (Simon Johnson)
Re: Police want help cracking code to find Enigma machine (Simon Johnson)
Re: A5/1 attack implementation? (David A Molnar)
Re: A new paper claiming P=NP (Bill Unruh)
Re: A new paper claiming P=NP (Bill Unruh)
Re: Hardware Implementation of DSA (Mike Rosing)
Re: The science of secrecy: Simple Substition cipher ("KK")
Re: A new paper claiming P=NP (David Eppstein)
Re: The science of secrecy: Simple Substition cipher (David Eppstein)
Re: A new paper claiming P=NP (Jonathan Thornburg)
Re: AES Runner ups (David Schwartz)
Re: The science of secrecy: Simple Substition cipher (David Crick)
Re: pass phrases and key generation (and Kerberos) (Ken Raeburn)
----------------------------------------------------------------------------
From: "DeSilva" <[EMAIL PROTECTED]>
Subject: re: working with huge numbers
Date: Wed, 11 Oct 2000 19:00:10 +0200
Yes thanks.. a free lunch was what i needed :-)
Where do i leave the tip then?
<[EMAIL PROTECTED]> skrev i en
nyhedsmeddelelse:8s1vek$b5c$[EMAIL PROTECTED]
> In article <8s11mi$eo5$[EMAIL PROTECTED]>,
> "DeSilva" <[EMAIL PROTECTED]> wrote:
> > So can anyone direct me to an online source of info on how to do this?
> > Quite frankly right now i dont want to sit and close read sourcecode
> in
> > order to figure out how and why one specific implementation does
> this, i
> > would much rather read some sort of tutorial on the subject... and
> right now
> > i am not really interested in buying books on the subject.
> >
>
> If you want a free lunch, then read this, chapter 14:
> http://cacr.math.uwaterloo.ca/hac/index.html
> They give the algorithms, you just have to implement them in your
> favorite language.
>
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: David Crick <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Date: Wed, 11 Oct 2000 18:18:25 +0100
Paul Pires wrote:
>
> Seems quick to me. Doing my conversion.. (now that I know what it is)
> it looks like about 22.9 clocks per byte (in C++) compared to 16.1 for
> twofish (Highly optimized assembler?) if I remember right from the home > page.
Why compare apples and oranges?
16.1 Twofish assembly compares to 14.5 Rijndael (assembly) with 128-
bit keys (and roughly 17.4 for 192, and 20.3 for 256-bit keys).
--
+-------------------------------------------------------------------+
| David A. Crick <[EMAIL PROTECTED]> PGP: (OCT-2000 KEY) 0xE0F73D98 |
| Damon Hill Tribute Site: http://www.geocities.com/MotorCity/4236/ |
| M. Brundle Quotes: http://members.tripod.com/~vidcad/martin_b.htm |
+-------------------------------------------------------------------+
------------------------------
From: JCA <[EMAIL PROTECTED]>
Subject: Re: Why wasn't MARS chosen as AES?
Date: Wed, 11 Oct 2000 10:03:50 -0700
Greggy wrote:
> In article <[EMAIL PROTECTED]>,
> JCA <[EMAIL PROTECTED]> wrote:
> > UBCHI2 wrote:
> >
> > > Why wasn't MARS chosen as AES?
> >
> > Because it was the worst candidate by a mile?
>
> The expression is, "by a country mile" if you want to add emphasis... :)
I stand corrected :-)
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Rijndael implementations
Date: Wed, 11 Oct 2000 10:22:21 -0700
David Crick <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Paul Pires wrote:
> >
> > Seems quick to me. Doing my conversion.. (now that I know what it is)
> > it looks like about 22.9 clocks per byte (in C++) compared to 16.1 for
> > twofish (Highly optimized assembler?) if I remember right from the home >
page.
>
> Why compare apples and oranges?
That's all I had handy. Sloppy work on my part but
you did supply the other apples :-)
Thanks
>
> 16.1 Twofish assembly compares to 14.5 Rijndael (assembly) with 128-
> bit keys (and roughly 17.4 for 192, and 20.3 for 256-bit keys).
>
> --
> +-------------------------------------------------------------------+
> | David A. Crick <[EMAIL PROTECTED]> PGP: (OCT-2000 KEY) 0xE0F73D98 |
> | Damon Hill Tribute Site: http://www.geocities.com/MotorCity/4236/ |
> | M. Brundle Quotes: http://members.tripod.com/~vidcad/martin_b.htm |
> +-------------------------------------------------------------------+
------------------------------
From: Michael Torla <[EMAIL PROTECTED]>
Subject: Re: CPU's aimed at cryptography
Date: Wed, 11 Oct 2000 10:01:32 -0700
Joe,
MPC180 operating at 66 MHz, will perform modular exponentiation using the
exponent 2^16+1, on 1024 bit moduli, in approximately 1.4 ms (exponentiation
computation time only).
MPC180e, operating at 66 MHz, will perform point multiplication on 160 bit
fields (random 160 bit k) in approximately 13.5 ms in Fp; marginally faster in
F2m polynomial basis.
mt
Joseph Ashwood wrote:
> Does anyone know the kind of signature verification performance these things
> have. I'm particularly interested in the verification of RSA and ECC. And
> also does any one know what format they expect to recieve the public keys
> for the same.
> Joe
>
> "kihdip" <[EMAIL PROTECTED]> wrote in message
> news:8r1ru9$c18$[EMAIL PROTECTED]...
> > CPU especially designed for cryptography are available.
> > This is probably old news, but here are the links:
> >
> > Motorola's CPU, MPC180 at:
> > http://mot-sps.com/news_center/press_releases/PR000926A.html
> > Analog Device's CPU, ADSP-2141 at:
> > http://products.analog.com/products/info.asp?product=ADSP-2141L
> >
> > Kim
--
========================================================================
| Michael J. Torla [EMAIL PROTECTED] |
| Motorola SPS Security Technology Center |
| Tempe, AZ 85282 |
========================================================================
*DigitalDNA(tm) from Motorola: It's who we are. It's what we do.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Police want help cracking code to find Enigma machine
Date: Wed, 11 Oct 2000 17:21:15 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (UBCHI2) wrote:
> How much does the thief want? Maybe this newsgroup can take up a
collection to
> get the Enigma back. Who wouldn't contribute the equivalent of a
Bletchley
> Museum admission to get to see the Enigma again. Is anyone else with
me on
> this? Let's raise a fund to get the enigma back.
>
> Together, we could raise the ransom money. Since you should never
negotiate
> with guys like this, the artifact should be kept in a more secure
environment
> upon return.
>
> Let's set up a central email site to take pledges.
>
>
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: Police want help cracking code to find Enigma machine
Date: Wed, 11 Oct 2000 17:22:11 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (UBCHI2) wrote:
> How much does the thief want? Maybe this newsgroup can take up a
collection to
> get the Enigma back. Who wouldn't contribute the equivalent of a
Bletchley
> Museum admission to get to see the Enigma again. Is anyone else with
me on
> this? Let's raise a fund to get the enigma back.
>
> Together, we could raise the ransom money. Since you should never
negotiate
> with guys like this, the artifact should be kept in a more secure
environment
> upon return.
>
> Let's set up a central email site to take pledges.
>
>
Its a nice idea, i'd be happy to pledge to recover a piece of important
cryptographic history?
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: A5/1 attack implementation?
Date: 11 Oct 2000 17:17:33 GMT
If I remember correctly, the paper notes that the authors implemented it
on a desktop PC for testing purposes. I don't know of any other
implementations which have been announced. (presumably all the
three letter agencies had something like this a while back)
rot26 <[EMAIL PROTECTED]> wrote:
> Does anyone know whether the A5/1 (used in the GSM protocol)
> attacks described in
> http://cryptome.org/a51-bsw.htm
> has ever been implemented?
> Also what's considered of the GSM protocol as a whole in terms of
> security nowadays? I searched the web but no single document seems to
> give the big picture of the state of affairs.
> I need to know because I am thinking of implementing the attacks as a
> final year university project. So does anyone care to give any advice on
> implementing attacks on algorithm and protocols in general? What are the
> pitfalls, caveats, difficulties etc? Obviously I don't want to mess up
> my final year...
> Thanks in advance.
> rot26
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 11 Oct 2000 17:33:21 GMT
In <1PYE5.215$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Kent Paul Dolan) writes:
>David Eppstein <[EMAIL PROTECTED]> wrote:
>><[EMAIL PROTECTED]> wrote:
>>> At the risk of playing clueless straight man here, let me point
>>> out that if validating a proof is P, then finding a proof is
>>> ipso facto NP, since you can guess the proof and then check
>>> if your guess is correct in P time.
>>There's an important technicality you're forgetting: the size of the proof
>>might not be polynomial in the size of the original problem.
Actually this makes no sense. Proofs do not come in sequences of longer
and longer statements of the proof. Also if checking he proof is P, and
since cheching is a linear traversal at least of the parts of the proof,
then if the size is not P then the checking is not P. So, either way, I
do not understand your caveate.
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 11 Oct 2000 17:39:18 GMT
In <8s24l4$lg7$[EMAIL PROTECTED]> [EMAIL PROTECTED] (Jonathan
Thornburg) writes:
>In <[EMAIL PROTECTED]> glenn <[EMAIL PROTECTED]> writes:
>>Irrelevant question, but is there any way of converting a pdf file to
>>ps?
>xpdf ( http://www.foolabs.com/xpdf/ ) is a free (GPL) pdf viewer
>which runs on most Unix flavors. It's about an order of magnitude
>smaller and faster than Acrobat. xpdf includes both the command pdftops
>and a GUI "print" command which produces a postscript file.
xpdf also seems to be more robust. I got a pdf file as a reference
letter. Printing it out using acroread truncated the right side about 20
characters in (making it hard to read) pluss messed up an italics in teh
letter. Perfectly readable on the screen and even by ghostview, but all
the postscript printers I tried the output of acroread on produced a
mess.
xpdf produced postscript the printers had no problems with.
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Hardware Implementation of DSA
Date: Wed, 11 Oct 2000 12:36:05 -0500
Brian Phillips wrote:
>
> I was wondering if anyone had run across any hardware implementation of
> DSA? I am attempting this right now and can't find much on it.
>
> Any and all help is much appreciated.
Check here and ask Prof. Paar who might already have done it as well:
http://www.ece.wpi.edu/People/faculty/cxp.html
Patience, persistence, truth,
Dr. mike
------------------------------
From: "KK" <[EMAIL PROTECTED]>
Subject: Re: The science of secrecy: Simple Substition cipher
Date: Tue, 10 Oct 2000 20:07:23 +0100
Intreasting. Where else can i find such programs or source code.
Id love some (q- / v-)basic code for a program like this
IanM <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> http://www.ics.uci.edu/~eppstein/cryptogram/
>
> this java applet deciphers it with just one letter wrong
>
> (by E.A. Joe)
>
>
------------------------------
From: David Eppstein <[EMAIL PROTECTED]>
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: Wed, 11 Oct 2000 10:52:41 -0700
In article <8s2891$4ad$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Bill Unruh) wrote:
> >>There's an important technicality you're forgetting: the size of the
> >>proof might not be polynomial in the size of the original problem.
>
> Actually this makes no sense. Proofs do not come in sequences of longer
> and longer statements of the proof. Also if checking he proof is P, and
> since cheching is a linear traversal at least of the parts of the proof,
> then if the size is not P then the checking is not P. So, either way, I
> do not understand your caveate.
The definition of a problem being in NP is that every yes-instance has a
witness *of polynomial size* which can be checked in polynomial time.
Lots of problems in harder complexity classes have witnesses which can be
checked in P, but the witnesses are too big.
For example, think about your favorite exp-time hard game, such as Chess or
Go. One possible way to prove you have a winning position would be to
write down a complete strategy tree -- if he moves there I move there etc
-- all the way out to checkmate. If someone hands you a strategy tree,
it's easy to check that the leaves really are checkmate, that each interior
position lists all legal moves for the opponent, and that each of your own
moves is legal -- so checking a tree is polynomial time. But the size of
the tree is exponential in the size of the original game position.
--
David Eppstein UC Irvine Dept. of Information & Computer Science
[EMAIL PROTECTED] http://www.ics.uci.edu/~eppstein/
------------------------------
From: David Eppstein <[EMAIL PROTECTED]>
Subject: Re: The science of secrecy: Simple Substition cipher
Date: Wed, 11 Oct 2000 10:59:10 -0700
In article <8s29a6$f4v$[EMAIL PROTECTED]>, "KK" <[EMAIL PROTECTED]>
wrote:
> Intreasting. Where else can i find such programs or source code.
> Id love some (q- / v-)basic code for a program like this
Did you follow the links on that page? Some of them lead to
http://www.gtoal.com/wordgames/cryptograms.html
--
David Eppstein UC Irvine Dept. of Information & Computer Science
[EMAIL PROTECTED] http://www.ics.uci.edu/~eppstein/
------------------------------
From: [EMAIL PROTECTED] (Jonathan Thornburg)
Crossposted-To: comp.theory,sci.math,sci.op-research
Subject: Re: A new paper claiming P=NP
Date: 11 Oct 2000 20:02:31 +0200
In <8s24l4$lg7$[EMAIL PROTECTED]> I wrote
| xpdf ( http://www.foolabs.com/xpdf/ ) is a free (GPL) pdf viewer
| which runs on most Unix flavors. It's about an order of magnitude
| smaller and faster than Acrobat. xpdf includes both the command pdftops
| and a GUI "print" command which produces a postscript file.
In article <8s28k6$4i5$[EMAIL PROTECTED]>,
Bill Unruh <[EMAIL PROTECTED]> wrote:
>xpdf also seems to be more robust. [[...]]
And last but not least, in place of acrobat's ##$@!@#$%^&* annoying spash
screen, xpdf just prints an annoying copyright message to stdout... so
a 3-line shell script can filter it out to achive "silent" operation.
--
-- Jonathan Thornburg <[EMAIL PROTECTED]>
http://www.thp.univie.ac.at/~jthorn/home.html
Universitaet Wien (Vienna, Austria) / Institut fuer Theoretische Physik
"There can be no doubt, I think, that the possession of money causes
people to take a more favorable view of this world in comparison to
the next." -- John Kenneth Galbraith
------------------------------
From: David Schwartz <[EMAIL PROTECTED]>
Subject: Re: AES Runner ups
Date: Wed, 11 Oct 2000 11:27:16 -0700
Greggy wrote:
> Let me rephrase - has the government stated any one of the other five
> finalists would be their backup deployment strategy if a problem was
> uncovered with Rijndael on some type of official level?
The rationale was that if a backup was picked, it either had to be
required or optional. If it was optional, interoperability problems
might be created between implementations that used the optional
algorithm and implementations that didn't. Plus it would mean a
negotiation layer would have to be implemented, which adds whole new
sets of security risks. If it was required that the backup algorithm be
implemented, the 'cost' of implementing the AES would equal the sum of
the 'costs' of the two algorithms. This would probably more than double
the hardware and software resources required.
DS
------------------------------
From: David Crick <[EMAIL PROTECTED]>
Subject: Re: The science of secrecy: Simple Substition cipher
Date: Wed, 11 Oct 2000 19:41:02 +0100
KK wrote:
>
> Channel 4 (UK) are running a series of 'The science of secrecy'
What I thought was amusing was the presented naive solution of work
needed to break a monoalphabetic substitution cipher: 26! (approx.
2**88). This was cited as taking longer than the age of the
universe to work. Yet instead of using brute force, the problem
can trivially be solved using letter frequencies, as was presented.
But we have seen the same thing with Enigma, and even in NIST's
Q&A on AES:
"Assuming that one could build a machine that could [brute
force] a DES key in a second, then it would take that machine
approximately 149 thousand-billion (149 trillion) years to
crack a 128-bit AES key. To put that into perspective, the
universe is believed to be less than 20 billion years old."
The truth is, of course, that there are far easier ways of
obtaining keys and/or plaintext besides brute force and (even)
cryptographic attacks.
--
+-------------------------------------------------------------------+
| David A. Crick <[EMAIL PROTECTED]> PGP: (OCT-2000 KEY) 0xE0F73D98 |
| Damon Hill Tribute Site: http://www.geocities.com/MotorCity/4236/ |
| M. Brundle Quotes: http://members.tripod.com/~vidcad/martin_b.htm |
+-------------------------------------------------------------------+
------------------------------
Subject: Re: pass phrases and key generation (and Kerberos)
From: Ken Raeburn <[EMAIL PROTECTED]>
Date: 11 Oct 2000 15:54:15 -0400
Paul Rubin <[EMAIL PROTECTED]> writes:
> CBC-MAC with a fixed IV has the disadvantage that with a one-block
> passphrase (anything <= 16 bytes because AES has 128-bit blocks), the
> passphrase can be decrypted.
Ow, good point. We do include a salt usually on the order of ten or
more bytes, but not always, and even when we do that may not be enough
if a really short password is chosen. The difference between a
principal's key and passphrase probably isn't all that crucial in the
Kerberos framework, since the only way we use the passphrase is in the
generation of the key, but it'd still be better to not have it be
reversible, IMHO.
> 1) Compute 128-bit AES CBC MAC of passphrase, with a fixed key and IV,
> preferably secret. Call the result K1.
> 2) Initialize K1 as a 128-bit AES key and use it to encrypt itself,
> i.e. find E(K1, K1).
> 3) Use the ciphertext from 2) as the final key.
Is encrypting a key with itself -- feeding it in as two different
inputs to step 2 -- not going to weaken anything? For that matter, is
it any better than encrypting a known constant with K1?
So, in general, using a CBC-MAC as a mixer to get a relatively good
key to use in a later step of generating the final key is okay then?
> > Should I give up on encryption-based schemes and just go with SHA1 (or
> > SHA2 eventually)?
>
> I don't think it matters much. Passphrases aren't a good way
> represent keys in the first place. They should only be used for low
For generic UNIX login and authentication, passphrases are what we've
got. The protocol allows for hardware authenticators as well (instead
of or in addition to passphrases), but most of the environments we're
dealing with don't have them.
> security applications. Nobody will break even a reasonably good
> password-to-key crunching scheme, if they can instead guess the
> passphrase by brute force, or sneak software onto the user's computer
> to capture the keystrokes and get the passphrase that way, etc.
Depends on what they're after. If, for example, certain classes of
passwords drastically cut down the key space, perhaps through
excessive collisions in some part of the algorithm, it may be fairly
easy and non-intrusive to bash just those keys against the traffic
that goes by, instead of targeting individual users with means that
may be more detectable.
> >[moved from top of message]:
> > I'm looking at putting together a spec for using Rijndael and/or
> > Twofish in Kerberos. ...
>
> It gets slightly off-topic, but can you say if there's any point in
> using Kerberos these days, other than to interoperate with existing
> Kerberized networks? It was a neat piece of software but needed a lot
> of complexity and careful design to do its work using only secret-key
> algorithms. Now that the important public-key patents have expired,
> isn't it simpler to use SSH, SSL, IPSEC, and so forth?
That's certainly a question we should probably think about and write
up an answer to some time, but two things occur to me offhand:
First, you're comparing apples and oranges to some degree. You can
use SSH with Kerberos authentication instead of public key, I do it
daily. There's a working group for IPSEC key management using
Kerberos. I think Kerberos or GSSAPI can be used with SSL too. There
are also proposals for having Kerberos make use of PK in certain ways
(e.g., initial ticket acquisition given a certificate; inter-realm
authentication). While the authentication and key negotiation schemes
are part of the protocols and applications, they're not the entirety.
Second, there are things Kerberos offers, or would let you do without
changing zillions of applications, such as more centralized management
(a plus to some, a minus to others), time-limiting damage from stolen
credentials, revocation of certain kinds of stolen credentials,
requiring good random-number sources only in a centralized place (the
KDC, not the applications), hardware authenticator support at login
time. More, I'm sure, that's been done elsewhere, using features MIT
doesn't use much or at all, and I'm not as familiar as I could be with
PK apps and their limitations.
There are certainly things Kerberos isn't and never has been good for
as well, like signing documents.
I've got too much else on my plate to spend much time going into the
relative merits right now. In short, though, I think the answer is
"yes". :-)
Ken
------------------------------
** 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
******************************
