Cryptography-Digest Digest #987, Volume #13 Sat, 24 Mar 01 09:13:01 EST
Contents:
Re: the classified seminal 1940 work of Alan Turing? (Frank Gerlach)
Re: New PGP Flaw Verified By Phil Zimmerman, Allows Signatures to be Forged
("Tomas Rosa")
Re: New PGP Flaw Verified By Phil Zimmerman, Allows Signatures to be Forged (Pawel
Krawczyk)
Re: the classified seminal 1940 work of Alan Turing? (Mok-Kong Shen)
Re: cryptography using the method of elliptic curve. ("Sam Simpson")
Re: Verisign and Microsoft - oops (Mok-Kong Shen)
Re: on-card key generation for smart card (Daniel James)
Valid condition for multiplicative generator? ("Tom St Denis")
Idiot Question -- Please Help a Crypto Moron ("Og Johnson")
----------------------------------------------------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Re: the classified seminal 1940 work of Alan Turing?
Date: Sat, 24 Mar 2001 13:33:54 +0100
"Douglas A. Gwyn" wrote:
> Frank Gerlach wrote:
> > There is no such thing as "fundamentals of mathematics". Check
> > Goedel,Turing and Chaitin.
> > In a nutshell, they state that most mathematical theories (a theory is a
> > set of axioms) *cannot* be reconciled. If this is true, then there cannot
> > be a "fundament of mathematics".
>
> I have to take issue with that interpretation. At worst, what they
> showed was that no (sufficiently rich) axiomatic system is *complete*,
> i.e. capable of on its own terms resolving all questions that might
> arise. Hofstadter's book "G�del, Escher, Bach: An Eternal Golden
> Braid" (which is worth reading anyway) tries to make this more
> intelligible. All the basic systems with which *most* mathematicians
> work are (thought to be) mutually consistent.
Ok, "*most*" is a very difficult term..
I agree that there might be "fundamentals of contemporary math education", but
that does not mean anything. Maybe the greeks thought they knew the
"foundations of mathematics", but since then a lot of radically new theories
(such as boolean logic or context-free languages) have been invented. These
theories are based on their *own* axiomatic systems and cannot be reduced to
the axioms which were known to the greek.
The real-world consequence is to dump the linear thinking of the
"enlightenment". Mathematics is not a scyscraper, where every new level of
theory is added on top of the existing. In fact, there are skyscrapers (e.g.
linear algebra), but there are also enormous number of one-story houses in
the suburbs (e.g. stack machines, regular expressions, context-free
languages).
Only because most mathematicians tend to work on skyscrapers does not mean the
other fields are less relevant or exciting. In fact, the flaws of complex
contemporary systems are very often quite trivial to describe in mathematic
terms, but they are rapdily becoming much more important in breaking a secure
communications system than everything else. One could argue that this has
nothing to do with crypto, but just were do you draw the line ? Are
key-exchange protocols crypto or not ? As they (eg. SSL) become more and more
complex, formal analysis methods are being used to "prove" their correctness
(whatever is defined as correct).
> The idea of finding a more powerful mathematics through tweaking the
> axioms doesn't get you very far. Most of the interesting systems
> tend to share some similar structures, brought out by tools such as
> Universal Algebra.
*Most* is the key word.
> One of the reasons elliptic curves are
> interesting is because they relate to many fields of mathematics
> that were formerly thought to be less related.
>
> There are also only a finite number of axiomatic systems under a
> specified complexity; this is partly the domain of combinatorial
> logicians, whose work is eerily fascinating.
Under a specified complexity..
------------------------------
From: "Tomas Rosa" <[EMAIL PROTECTED]>
Crossposted-To:
alt.privacy.anon-server,alt.security.pgp,comp.security.pgp.discuss,comp.security.pgp.resources,comp.security.pgp.tech
Subject: Re: New PGP Flaw Verified By Phil Zimmerman, Allows Signatures to be Forged
Date: Thu, 22 Mar 2001 11:07:51 +0100
Despite of some claims from the wired article, we note that the attack is
realistic.
We think that everybody would agree that any kind of information which is
referred to as *encrypted information* shall be able to be stored anywhere
without the risk of its disclosure.
There shall be no reason to store your private key, which is properly
encrypted, in the deposit. We have shown that in the case of the OpenPGP
format the encrypted private key MUST NOT be stored in the place, where the
attacker can access and modify it. From here we conclude that private keys
are NOT PROPERLY ENCRYPTED in the OpenPGP format and derived applications.
So, from the cryptologic point of view, the attack is pretty serious.
Moreover it is also realistic. In the networked systems users usually would
like to store their containers with private keys in some shared place to be
able to have their keys ready to use on any workstation in the network. Note
that this is the default option in the PGP. In such scenario it is clear
that the user has very little or no control on the encrypted private key.
Anybody who can modify this information when it is going through the network
can carry out the attack. Of course your network administrator is the first
person who can be the attacker. We think that users shall not have to care
about such thinks (when their private keys are properly encrypted, of
course). Btw: wasn't it the main idea behind the whole PGP to give its users
"Pretty Good Privacy" in such environments?
So, from the practical point of view, the attack is pretty realistic.
More information will be available in the crypto-paper, which will be
released soon at www.i.cz.
Tomas & Vlastimil
"Bob C." <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> From the article at:
> http://www.wired.com/news/print/0,1294,42553,00.html
>
> Your E-Hancock Can Be Forged
> by Declan McCullagh
> 10:20 a.m. Mar. 21, 2001 PST
> WASHINGTON -- A Czech information security firm has found a flaw in
> Pretty Good Privacy that permits digital signatures to be forged in
> some situations.
>
> Phil Zimmermann, the PGP inventor who's now the director of the
> OpenPGP Consortium, said on Wednesday that he and a Network Associates
> (NETA) engineer verified that the vulnerability exists.
>
> ICZ, a Prague company with 450 employees, said that two of its
> cryptologists unearthed a bug in the OpenPGP format that allows an
> adversary who breaks into your computer to forge your e-mail
> signature.
>
> Both Zimmermann and the Czech engineers, Vlastimil Klima and Tomas
> Rosa, point out that the glitch does not affect messages encrypted
> with PGP. OpenPGP programs -- including GNU Privacy Guard and newer
> versions of PGP -- use different algorithms for signing and
> scrambling, and only the digital signature method is at risk.
>
> PGP and its offspring are by far the most popular e-mail encryption
> programs in the world. Nobody has disclosed a flaw in their
> message-scrambling mechanisms, but PGP owner Network Associates
> suffered an embarrassment last August when a German cryptanalyst
> disclosed a flaw that allows an attacker to hoodwink PGP into not
> encoding secret information properly.
>
> In this case, someone wishing to impersonate you would need to gain
> access to your secret key -- usually stored on a hard drive or a
> floppy disk -- surreptitiously modify it, then obtain a message you
> signed using the altered secret key. Once those steps are complete,
> that person could then digitally sign messages using your name.
>
> "PGP or any program based on the OpenPGP format that does not have any
> extra integrity check will not recognize such modification and it will
> allow you to sign a message with the corrupted key," says Rosa, who
> works at Decros, an ICZ company. Rosa says he demonstrated the
> vulnerability with PGP 7.0.3.
>
> OpenPGP's Zimmermann downplayed the attack, saying that it requires
> someone trying to impersonate you to physically or electronically
> break into your computer.
>
> "It's not an attack that is going to be available to your opponent
> unless you're careless with your private key," Zimmermann said. "We
> specifically warn users to protect their private keys. Users who don't
> protect their private keys have always been at risk -- this is common
> sense."
>
> Even before Klima and Rosa found this glitch, an attacker who managed
> to snatch someone's private key could try to break the passphrase that
> protected it -- and many people appear to rely on weak passphrases
> that can be guessed by a human or a machine.
>
> "It's not a realistic attack," Zimmermann said. "Much worse attacks
> are possible if (an adversary) can get that far."
>
> The exploit works by attacking the Digital Signature Algorithm's
> so-called discrete logarithm problem. DSA keys are typically stored in
> a file called secring.skr, and Klima and Rosa found that they could
> successfuly insert a replacement key in it.
>
> Network Associates did not return phone calls or e-mail messages
> asking if they had any plans to release a fixed version of PGP.
>
> Klima said that on Thursday, he will publish an English-language
> description of their exploit on ICZ's web site. "We promised Network
> Associaties that we will not release these details until tomorrow," he
> said.
>
>
>
>
>
>
------------------------------
From: Pawel Krawczyk <[EMAIL PROTECTED]>
Crossposted-To: alt.privacy.anon-server,alt.security.pgp
Subject: Re: New PGP Flaw Verified By Phil Zimmerman, Allows Signatures to be Forged
Date: Wed, 21 Mar 2001 19:24:05 +0000 (UTC)
In sci.crypt Bob C. <[EMAIL PROTECTED]> wrote:
> The exploit works by attacking the Digital Signature Algorithm's
> so-called discrete logarithm problem. DSA keys are typically stored in
> a file called secring.skr, and Klima and Rosa found that they could
> successfuly insert a replacement key in it.
Every day new details leak painfully slow from the ICZ and it's
still getting closer to another instance of what Bruce Schneier called
`publicity attack'. First comments from ICZ suggested that the PGP has
been broken, then that the secret key can be retrieved without knowing
the passphrase, now we learn that you can substitute private key with
your own, if you have access to the keyring. What an invention! ;-\
--
Pawe� Krawczyk *** home: <http://ceti.pl/~kravietz/>
security: <http://ipsec.pl/> *** fidonet: 2:486/23
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: the classified seminal 1940 work of Alan Turing?
Date: Sat, 24 Mar 2001 13:07:51 +0100
Frank Gerlach wrote:
>
> Mok-Kong Shen wrote:
> >
> > My knowledge of mathematical logic is too meager to argue.
> > But isn't it that Goedel's imcompleteness theorem puts up
> > only a rather (in meaning) 'restricted' statement
> > concerning predicate calculi of higher order and as such
> > probably could not be applied (generalized) to deals with
> > matters like 'efficiency'? (I mean it deals only with
> > 'possibility'/'impossibility'.)
>
> Goedel proves that it is impossible to unify all conceivable mathematic
> theories. This means that an efficiency statement based on one
> theory/approach, which might even be proven, might not be true for a different
> theory.
Could you please post the version of Goedel's imcompleteness
theorem that has anything to do with 'unification' of
mathematics? I like to see the exact text. That one theory
with its axioms can lead to results different from another
theory with different axioms, is trivial. That's why we see
a lot of theories in all sciences, isn't it?
> Very simple example: use a broad-band receiver and look at the signal in the
> time domain. You will see only very complex noise. Look at it in the frequency
> domain, you will see quite some peaks, which represent radio signals. Now you
> only need to filter the frequency you are interested in and transform it back
> into the time domain. That is what you radio or TV does.
> With CDMA mobile phones, it is quite the opposite: They use the same frequency
> band, but do some time-domain correlation.
> Other very interesting domains are used for Wavelet Transformation.
> You can see, depending on the mathematical framework/theory (fourier-,
> wavelet-transform or simple time domain), information can be extracted, which
> seems not to exist in another domain.
> The same is with differential or linear cryptanalysis(although you might not
> consider them "theories"): If you don't know them, you cannot strengthen your
> S-Boxes against them.
I am afraid that doing such 'generalizations'/'analogies'
is vulgarising Goedel's mathematical work, which has
precise statements concerning predicate calculi. One
couldn't connect predicate calculi readily/directly with
lots of stuffs in practical life, if I don't err.
>
> > Are you claiming that
> > people e.g. in NSA are employing a different kind of
> > mathematics than is employed (or understood/known) by the
> > public? Thanks.
>
> Spook agencies heavily depend on the diversity and good skills of university
> graduates (such as Oxford grads). The difference is that their mathematicians
> will not publish anything, regardless how interesting. For example, CESG (the
> the codemaker arm of GCHQ) discovered RSA *first* (calling it "Non Secret
> Encryption"), but published it only in 1997 (87?) (see www.cesg.gov.uk).
> Until that time, they basically put it into the "poison chamber", in order not
> to give competing agencies an advantage.
> Public Key Crypto might not be a "theory", but it is a giant leap forward in
> crypto. Imagine what else they still have in the "poison chamber"....
> Just look at Turing's work - it was ground-breaking in many ways, and a large
> part of it was done at GCCS (the predecessor of GCHQ).
> On the other hand, working for your whole live for the spooks is most probably
> very unsatisfactory to a good mathematician, because you cannot publicize and
> discourse is limited to other spook mathematicians. Different in wartime, of
> course..
> The bottom line seems to be that they employ a large number of excellent
> mathematicians, and all their work remains secret (maybe not to the KGB,
> though). As mathematicians from time to time invent a new theory, it is
> inevitable that they have some "secret mathematics", along with lot of
> analysis tools for symbolic math and lots of other equipment/software
> designed on their own (all secret, of course).
> Just check the job descriptions on www.gchq.gov.uk or www.nsa.gov to see what
> they are doing.
> I found the signals/hardware engineering sections especially enlightening :-)
>
> All that can be "re-invented" by non-spook mathematicians, but as long as it
> isn't, it remains they little secret theory/method.
I don't yet see that you are 'exactly'/'rigorously'
addressing my point. Crypto computations will definitely
remain in the realm of calculus and number theory that
are taught in the universities. In other words, there
will never be anything inherently different between
the mathematics of the users and the opponent, like
that e.g. between Euclidean and non-Euclidean geometries.
There could be a quantititive difference between the
math knowledge of the users and the opponent, of course,
but not in the math employed as such, I believe.
M. K. Shen
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: cryptography using the method of elliptic curve.
Date: Sat, 24 Mar 2001 12:09:56 -0000
With a search engine?
--
Regards,
Sam
http://www.scramdisk.clara.net/
Mauro <[EMAIL PROTECTED]> wrote in message
news:99dk95$ps3$[EMAIL PROTECTED]...
> How can i find information about cryptography using the method of elliptic
> curve.
>
> thanks
> Mauro Pace
> http://web.tiscalinet.it/theflynet/
>
>
>
>
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Verisign and Microsoft - oops
Date: Sat, 24 Mar 2001 13:13:30 +0100
Mathew Hendry wrote:
>
> http://www.microsoft.com/technet/security/bulletin/MS01-017.asp
Merely a tiny example illustrating Murphey's Law, I suppose.
M. K. Shen
------------------------------
From: Daniel James <[EMAIL PROTECTED]>
Subject: Re: on-card key generation for smart card
Date: Sat, 24 Mar 2001 12:46:45 GMT
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, Peter Gutmann wrote:
> If any smart card manages to do a keygen in less than 30s I'd say
> it's faking it on the host rather than using the card.
I've spoken to a few vendors who sell RSA cards and/or PKCS#11
implementations based around RSA cards. I've found the vendors to be
generally pretty honest about what it is they actually do. One vendor of
a PKCS#11 token based around the Schlumberger card was quite adamant that
generating the key in software and loading it into the card was the best
was to operate because one could then be sure that sufficient care had
been taken to generate a strong key (this vendor did not "fake it", they
support C_CreateObject for RSA private keys, but C_GenerateKeyPair).
I have done APDU-level work with some of GemPlus's RSA smartcards. Their
GPK4000 card generates a 1024-bit keyset in 160 seconds 90% of the time -
the remaining 10% of the time you get an "operation not complete" error
code and have to start again. Their newer GPK8000 cards - which are said
to perform the keygen on-card - typically generate a keyset in less than
10 seconds using GemPKCS (I've not had occasion to perform a keygen
operation at APDU level, but I have examined the access control
attributes on the key files and I don't think this is "faked").
Cheers,
Daniel.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Valid condition for multiplicative generator?
Date: Sat, 24 Mar 2001 13:09:55 GMT
I am making a cross platform CryptoLib (really simple, DH + RNG + RC4 +
MiscStuff(tm)= lib :-)) and I am trying to make a function to verify at
runtime that the DH stuff is working (i.e the compiler did it's job).
Basically I verify that the bases are in fact generators w.r.t to their
primes...
All my DH primes are sophie primes (er... 2p + 1 = prime, p = prime). Is it
valid just to test if g^p mod (2p+1) == 1 to reject bases? (i.e it should
only be one with g^(2p) mod (2p+1))?
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: "Og Johnson" <[EMAIL PROTECTED]>
Subject: Idiot Question -- Please Help a Crypto Moron
Date: Sat, 24 Mar 2001 09:03:08 -0500
I'm at work, and was just handed a word puzzle. If I don't answer it by
noon today (it is 8:52 EST right now) I have to buy everyone in my office
lunch. I'm too lazy to think, and I'm not feeling at all generous with my
money, so could the Jim Gilloughys and the Bill Shaws of sci.crypt help a
poor forty-niner out?
Here it is ---
A college student sends a note home to his parents asking for more money.
>From the note, his parents are able to tell exactly how much money he wants.
Here is the note:
SEND
MORE
====================
MONEY
The words SEND and MORE are directly underneath each other; the word MONEY
is displaced one character to the left.
I promise not to waste any more bandwidth, and I beg in advance for the
forgiveness of the young crypto-genius, Tom St. Denis, but this question
determines whether I am a hero or goat here at work today!
Humbly Yours, Og Johnson
------------------------------
** 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
******************************
