Cryptography-Digest Digest #310, Volume #10 Fri, 24 Sep 99 15:13:03 EDT
Contents:
Re: EAR Relaxed? Really? (Bill Unruh)
Re: frequency of prime numbers? ("Douglas A. Gwyn")
Re: Glossary of undefineable crypto terms (was Re: Ritter's paper) (Mok-Kong Shen)
Re: Second "_NSAKey" (Bruce Barnett)
Re: Glossary of undefineable crypto terms (was Re: Ritter's paper) (Patrick Juola)
Re: Another bug RE: CryptAPI (Christopher Biow)
Re: RSA 640 bits keys factored, French banking smart card system craked! ("Trevor
Jackson, III")
Re: PKCS#7 implementation (Paul Schlyter)
Re: Relating cyrptology to factoring? (Tim Tyler)
Re: RSA 640 bits keys factored, French banking smart card system craked! (Tom St
Denis)
Re: Glossary of undefineable crypto terms (was Re: Ritter's paper) ("Trevor Jackson,
III")
Re: Securing Executables ("Trevor Jackson, III")
Re: RSA 640 bits keys factored, French banking smart card system craked! ("Dmitriy
Morozov")
Re: Relating cyrptology to factoring? (John Savard)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Crossposted-To: talk.politics.crypto
Subject: Re: EAR Relaxed? Really?
Date: 24 Sep 1999 16:47:21 GMT
In <[EMAIL PROTECTED]> Jim Gillogly <[EMAIL PROTECTED]> writes:
>>
>> The interesting question is whether the "technical review"
>> will be allowed to end with the product failing to be approved
>> (presumably because it is too secure, although that might not
>> be the officially stated reason).
>Why else would there be a requirement for a technical review?
>On what other grounds would a product fail to be approved?
That makes it almost funny. You can export arbitrarily strong crypto
with arbitrry key lengths. However, if we cannot break it you cannot
export it. Seems NSA is setting itself up as a crypto vetting
institution. Instead of people posting their latest and greatest crypto
here in sci.crypt, they just send it to NSA for export approval. If NSA
passes it, you know it is weak. At least this will serve some useful
prupose if only to supply a canned reply to people posting their latest
invention here.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: frequency of prime numbers?
Date: Fri, 24 Sep 1999 15:41:02 GMT
Patrick Juola wrote:
> There is. First order logic has been proved consistent (by Goedel).
> There is also a proof, again by Goedel, that the consistency of
> a consistent system cannot be proved using only techniques within that
> system.
So long as that system is powerful enough to express simple arithmetic.
> So we have a proof that first order logic is consistant, but also a
> proof that first order logic can neither find nor express that proof.
> Hence the consistency of FOL is unprovable (within FOL) but true --
> we know it's true because it's provable in a more powerful system.
Yes, assuming that the more powerful system is consistent...
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Glossary of undefineable crypto terms (was Re: Ritter's paper)
Date: Fri, 24 Sep 1999 17:02:50 +0200
Mok-Kong Shen wrote:
>
> Patrick Juola wrote:
>
> > Hell, there's an easier counterexample. O(1) is a provable lower
> > bound to *everything.*
>
> In your vein, why take the trouble to argue with O(1)? Isn't 0
> itself much better?
I like to give a citation from a recent article of Salomaa which
perhaps helps to make his other citation given earlier in this
thread more understandable:
In general, all these [public-key crypto] systems are
dangerously dependent on number-theoretic problems, such as
factoring, whose complexity is not known; there is no proof
that they are intractable.
M. K. Shen
------------------------------
From: Bruce Barnett <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Second "_NSAKey"
Date: 24 Sep 1999 08:59:12 -0400
Greg <[EMAIL PROTECTED]> writes:
> Be my guest. Show me why the conspiracy theory to give
> NSA a key CANNOT be correct. That is what I mean by refute.
> Show that it CANNOT be correct.
This is in the same category as:
"Show that Santa Claus does NOT exist."
It can't be refuted. ever. Let's move on, shall we?
--
Bruce <barnett at crd. ge. com> (speaking as myself, and not a GE employee)
------------------------------
From: [EMAIL PROTECTED] (Patrick Juola)
Subject: Re: Glossary of undefineable crypto terms (was Re: Ritter's paper)
Date: 24 Sep 1999 11:08:29 -0400
In article <[EMAIL PROTECTED]>,
Volker Hetzer <[EMAIL PROTECTED]> wrote:
>Patrick Juola wrote:
>>
>> In article <[EMAIL PROTECTED]>,
>> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>> >Joseph Ashwood wrote:
>> >>
>> >> [snip]
>> >> > How 'hard' are these REALLY? A citation from A. Salomaa says that
>> >> > there are no provable lower bounds for the amount of work of
>> >> > a cryptoanalyst analysing a public-key cryptosystem.
>> >> There can be no lower bounds or upper bounds placed on human cognition,
>> >> simply because we do not understand it. If you are talking about lower
>> >> bounds of the work necessary to break a public key, it is trivial to prove
>> >> that no common method could possibly drop below O(n), where n is the length
>> >> of the key, this is because you obviously must read the key before you can
>> >> break the key, outside of that I am not aware of any progress.
>> >>
>> >
>> >If I understood correctly, you are saying what Salomaa wrote was
>> >nonsense.
>>
>> If he isn't, I am. More accurately, I claim that your presentation of
>> his statement is demonstrably false.
>>
>> Hell, there's an easier counterexample. O(1) is a provable lower
>> bound to *everything.*
>>
>Not meaning to butt in, but why do you have to read the key?
>Couldn't there (in theory) be a cryptosystem, where you read just
>a few bits of message (less than the key) and then are able to produce the key?
Well, producing the key still requires producing each of the key bits.
>Or even just the plaintext which, in turn might be less than the key?
If the plaintext is less than the key, then you're dealing with a
potential OTP, which makes success less than likely.
-kitten
------------------------------
From: Christopher Biow <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: Another bug RE: CryptAPI
Date: Fri, 24 Sep 1999 13:30:42 -0400
Eric Lee Green <[EMAIL PROTECTED]> wrote:
>Christopher Biow wrote:
>> Back to the closed/open source comparison: Note that it was the leaking of
>> source-code symbol information which allowed the identification of the "NSA
>> key" vulnerability. Recovering that information from the object code (to
>> the point of noting the vulnerability) would have been much more expensive.
>> Recovering the semantics provided by "NSA key" from the object code would
>> probably not have been possible.
>Absolutely false. The vulnerability was explained in one of Bruce
>Schneier's newsletters over six months before the "NSA Key" furor. It
>was described as a second key, that could be replaced by your own public
>key in order to insert unauthorized cryptographic components.
You corrected my account by adding the fact that the extensive effort *was*
in fact expended to determine the presence of a second key. Thank you for
the correction--that's what Usenet if here for.
I remain correct that nothing prior to the release of the symbol
communicated the semantics of "NSA key".
>Also see: http://www.cs.berkeley.edu/~daw/papers/
>
>and read the paper about vulnerabilities in an (old) version of the
>Netscape browser. David Wagner succesfully reverse-engineered the SSL
>code in the original Netswcape=-SSL, and found a rather surprising
>vulnerability.
I have claimed only that such decompilation of code is expensive, not
impossible. In the context of cryptographic code, I agree that open-source
should be considered a requirement for use of the adjectives "good" or
"trustworthy."
>Regarding "open source vs. closed source", Unix or Unix-lookalike
>operating systems account for approximately 75% of the operating systems
>on the Internet.
Defined how? By discrete, continuous IP address, they may or may not be. By
IP-addressable-at-times, I very seriously doubt that they are, given the
predominance on Win workstations.
>It is unsurprising that there have thus been more
>network-related attacks directed against them...
That's a valid point. I would also speculate that there is a difference due
to hackers tending to prefer to work within, and even against, their own
preferred OS. Regardless, the closed-source of WinNT has been a
considerable impediment to the discovery of many classes of
vulnerabilities, especially remote buffer overflows. I don't believe that
the equivalent part of WinNT code is much freer of buffer overflow faults
than wu-ftpd--it just seems that the former have not been discovered due to
the closed source.
>I have not seen significant differences
>between the security alerts for closed-source Unix variants and the
>security alerts for open-source Unix variants. If you have, please
>direct me to the source of that information.
Scanning http://ciac.llnl.gov/cgi-bin/index/bulletins?i and
http://ciac.llnl.gov/cgi-bin/index/bulletins?j ISTM that the vast majority
of the Unix remote root exploits that have been discovered and potentially
widely exploited (i.e. not discovered and patched in-house prior to release
of vulnerability info) have been in open-source Unix code.
Relative security can be had through obscurity in OS code, ca. 1999.
------------------------------
Date: Fri, 24 Sep 1999 10:41:23 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: RSA 640 bits keys factored, French banking smart card system craked!
Bruce Barnett wrote:
> Alex <[EMAIL PROTECTED]> writes:
>
> > I was under the impression that it's the other way around, i.e. the
> > number of primes less than x is roughly x/log(x).
>
> Forgive my ignorance, but while the number of primes may be x/log(x),
> does the algorithm try to find primes of a certain minimum size? How
> much does this reduce the search?
By approximately one half.
The lower bound on numbers in the target is X/2, so you lose X/(2*log(X/2)) of
primes that are too small.
You get a larger benefit from knowing at least three bits of each factor. The
top bit is always one. The next-to-top bit is usually one to guarantee that the
product doesn't lose a bit due to lack of a carry. Of course the bottom bit is
one because the factors are odd.
If the specialness of the number includes a formula such as 4x+3, then you know
even more about the bottom bits.
Thus you know at least six bits of the product from simple inspection.
------------------------------
From: [EMAIL PROTECTED] (Paul Schlyter)
Subject: Re: PKCS#7 implementation
Date: 24 Sep 1999 16:37:43 +0200
In article <7sfqh6$6dt$[EMAIL PROTECTED]>,
Roberto Gaudenzi <[EMAIL PROTECTED]> wrote:
> I'm looking for a C or C++ implementation of PKCS#7 standard, possibly
> with source code. Does anybody known where I can find it ?
Check out: http://www.openssl.org
There you'll find free C source code for DES, SHA, MD5, RSA,
PKCS#7,8,12, SSL, ASN/BER/DER/PEM + a lot of other stuff. Be patient
though -- it takes some time to wade through all this. Download
the whole openssl library and build it, then start using it and
you'll get acquaited to it.
--
================================================================
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: [EMAIL PROTECTED] [EMAIL PROTECTED] [EMAIL PROTECTED]
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Relating cyrptology to factoring?
Reply-To: [EMAIL PROTECTED]
Date: Fri, 24 Sep 1999 18:22:41 GMT
jerome <[EMAIL PROTECTED]> wrote:
: NSA claims to have discover the assymetirc cypher in the 60's
: the english intelligence around 70 [...]
I thought the English GCHQ got there approximately three years before the
Americans.
Please correct me if this is not correct.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
I've had fun before. This isn't it.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: RSA 640 bits keys factored, French banking smart card system craked!
Date: Fri, 24 Sep 1999 16:11:12 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Johnny Bravo) wrote:
> The number of primes not exceeding x is asymptotic to x/log x. This has been
> completely proven. A better fitting estimate is just a bit under the proven
> maximum formula x/(log x - 1).
First the prime number theorem is pi(x) = x / ln x, and it has not been
proven, that's why it's a theorem. It just happends to be a very good
estimate.
Second I seriously doubt the primary poster had any idea what he was talking
about. Applied Crypto covers prime numbers in a bit of detail, you should
check there.
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Fri, 24 Sep 1999 14:52:39 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Glossary of undefineable crypto terms (was Re: Ritter's paper)
Volker Hetzer wrote:
> Patrick Juola wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> > >Joseph Ashwood wrote:
> > >>
> > >> [snip]
> > >> > How 'hard' are these REALLY? A citation from A. Salomaa says that
> > >> > there are no provable lower bounds for the amount of work of
> > >> > a cryptoanalyst analysing a public-key cryptosystem.
> > >> There can be no lower bounds or upper bounds placed on human cognition,
> > >> simply because we do not understand it. If you are talking about lower
> > >> bounds of the work necessary to break a public key, it is trivial to prove
> > >> that no common method could possibly drop below O(n), where n is the length
> > >> of the key, this is because you obviously must read the key before you can
> > >> break the key, outside of that I am not aware of any progress.
> > >>
> > >
> > >If I understood correctly, you are saying what Salomaa wrote was
> > >nonsense.
> >
> > If he isn't, I am. More accurately, I claim that your presentation of
> > his statement is demonstrably false.
> >
> > Hell, there's an easier counterexample. O(1) is a provable lower
> > bound to *everything.*
> >
> Not meaning to butt in, but why do you have to read the key?
> Couldn't there (in theory) be a cryptosystem, where you read just
> a few bits of message (less than the key) and then are able to produce the key?
> Or even just the plaintext which, in turn might be less than the key?
This would require the information density of the "few bits of message" to be
greater than one bit per bit. An unreasonable requirement.
It may be that there are very few keys and by inspecting a few bits one could select
from among that very small set. But this mangles the term "key", which usually
refers to the portion of the system that must remain secret. If there's a small
table of large numbers that control the encryption process then the true key is the
index into that table not the value stored in the table. You could publisht the
table of control values as long as you keep secret the index.
------------------------------
Date: Fri, 24 Sep 1999 15:02:51 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Securing Executables
jerome wrote:
> On Fri, 24 Sep 1999 14:41:40 GMT, Tim Tyler wrote:
> >Trevor Jackson, III <[EMAIL PROTECTED]> wrote:
> >: jerome wrote:
> >
> >:> all that looks a lot like the tricks used by game coders a long time ago
> >:> to prevent the crackers to copy or modify their softwares.
> >:> Each time the gamecoders loosed badly because it is easy to modify the
> >:> executable just to avoid to do the test.
> >
> >: Some lost, some won.
> >
> >Indeed. Some of the techniques used to prevent people from decompiling
> >self-decryption were *very* sophisticated fifteen years ago.
> >
> >"Modifying the executable to avoid doing the test" was often made
> >difficult by encrypting in a series of layers, each executing the
> >code of the previous stage.
> >
> >As for people using debuggers - this slows down execution - an effect
> > which can be tested for
>
> with cards who physically freeze the computer (timer included)
> it is much harder.
It is extremely hard to freeze a system totally. Typically the DRAM refresh
cannot be frozen unless the program is running on specialized hardware (e.g.,
SRAM). It's also hard to freeze video sync. And it's extremely hard to freeze
a disk drive, which on older controllers may make the current sector ID
available. If any of these become discontinuous or drift strangely you are
under attack.
Like the arms race between offense and defense, there's no ultimate or permanent
victory. Only ongoing technology and ingenuity.
Note that in a less sophisticated environment, CoreWars, I understand there's an
unkillable program. It doesn't win much because all of its time is spent on
defense. But I think there's a proof that it can't lose. Of course it's
fighting a peer rather than a human. It would be an interesting form of reverse
Turing Test to see if a human could do what a program cannot.
>
>
> > and fake code branched to - etc, etc.
>
> harder but doable.
>
> i remember a game with 17 differents kind of protection, it was hard
> to crack but the side effect is all the crackers tried to just to
> prove they were better than the other crackers.
------------------------------
From: "Dmitriy Morozov" <[EMAIL PROTECTED]>
Crossposted-To: alt.security.pgp
Subject: Re: RSA 640 bits keys factored, French banking smart card system craked!
Date: Fri, 24 Sep 1999 14:29:40 -0400
> First the prime number theorem is pi(x) = x / ln x, and it has not been
> proven, that's why it's a theorem. It just happends to be a very good
> estimate.
That's what I found on the Web.
The Prime Number Theorem: The number of primes not exceeding x is asymptotic
to x/log(x).
Finally, in 1896 Hadamard and independently de la Vallee Poussin completely
proved the prime
number theorem using Riemann's work relating pi(x) to the complex zeta
function.
If it was not proved wouldn't it be called a hypothesis? Though on the same
page it says that the thing that you wrote (pi(x)=x/ln(x)) is just a very
good approximation (exactly what you said).
> Second I seriously doubt the primary poster had any idea what he was
talking
> about. Applied Crypto covers prime numbers in a bit of detail, you should
> check there.
The web site that I found that stuff at is:
http://www.utm.edu/research/primes/
and specifically
http://www.utm.edu/research/primes/howmany.shtml#pnt
--
Dmitriy Morozov
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Relating cyrptology to factoring?
Date: Fri, 24 Sep 1999 19:11:55 GMT
Tom St Denis <[EMAIL PROTECTED]> wrote, in part:
>In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] () wrote:
>> A new type of cryptography, called "public-key cryptography",
>Just to be picky I would seriously argue that symmetric ciphers are
>younger then their asymmetric counterparts.
Do you mean "stronger", instead of "younger"?
Do you mean that the asymmetric ciphers are based on classical
mathematical problems, and are "old" because they're based on old
theory, while block ciphers currently in use are based on recent
ideas?
Symmetric-key encryption, in general, is quite old, while the
public-key systems were invented, at the earliest, around 1968
secretly in Britain.
John Savard ( teneerf<- )
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
** 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
******************************
