Cryptography-Digest Digest #553, Volume #9 Sun, 16 May 99 02:13:06 EDT
Contents:
Re: help me crack strong RSA-DNS unicode encryption (Jim Gillogly)
Dont Read This ([EMAIL PROTECTED])
Re: [Q] Are all encryption algorithms based on primes? ("Douglas A. Gwyn")
Re: True Randomness & The Law Of Large Numbers ("Douglas A. Gwyn")
Re: On Contextual Strength ("Douglas A. Gwyn")
Hmm, I wonder if I got this right ([EMAIL PROTECTED])
Re: True Randomness & The Law Of Large Numbers (R. Knauer)
Re: Europe and USA encryption export restrictions ("Douglas A. Gwyn")
Re: Musing on and Factoring of a (special) 782-bit Modulus ("Douglas A. Gwyn")
Re: [Q] Are all encryption algorithms based on primes? ([EMAIL PROTECTED])
Re: Strength of PGP 1.0 conventional block cipher? (Nathan Kennedy)
Security ([EMAIL PROTECTED])
Re: Lemming and Lemur (David Wagner)
Re: Europe and USA encryption export restrictions (Sundial Services)
Re: AES what's up? (Fredrik Olofsson)
--- sci.crypt charter: read before you post (weekly notice) (D. J. Bernstein)
Re: Lemming and Lemur ([EMAIL PROTECTED])
Re: On Contextual Strength (wtshaw)
----------------------------------------------------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: help me crack strong RSA-DNS unicode encryption
Date: Sat, 15 May 1999 13:24:57 -0700
Interesting. Is this some new candidate for an international
language? If so, it would probably be happier in
alt.language.artificial.
Nenad Aliix wrote:
>
> di w��t bra�c,t unikout
The world braucht (needs) unicode.
> in zajdn wou sijm bit aszij di no@m is obwuj $u
seven? bit ASCII?
> saijt aana ewic,kait latin aans , zwa , drai , .....
was? Ewigkeit Latin-1, -2, -3, ...
> unt big fajf , d$isi unt so wajda gejm dujt unt
and Big Five , und so weiter (and so forth)
> as inglesi$e di ima me@ zu@ u@zic, wi@klic,n
English wirklich (actually)
> w��t$brouc, auf$taijgt waj de kfrijsa hajt zu
weltbraucht, aufsteigt...
and so on. Maybe a dialect of German?
> anke mi lasas saluti na xiuj samlingvanoj ,
Woops, that looks like a dialect of Esperanto -- "alsoly
(anke isn't quite a word) I stop (?) to salute (na?) all
who speak the same language (usually meaning Eo)".
Assuming it's a new artificial language, my preference is
always to pick an orthography that maps well to 7-bit
ASCII -- but I suppose that's just Anglocentrism speaking.
--
Jim Gillogly
Hevensday, 24 Thrimidge S.R. 1999, 20:07
12.19.6.3.9, 12 Muluc 17 Uo, Sixth Lord of Night
------------------------------
From: [EMAIL PROTECTED]
Subject: Dont Read This
Date: Mon, 03 May 1999 12:56:41 GMT
l
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: [Q] Are all encryption algorithms based on primes?
Date: Sat, 15 May 1999 22:41:42 GMT
Jessie wrote:
> Are all encryption algorithms based on the fact that it is
> difficult to factor a number which is the product of two LARGE
> primes?
No.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Sat, 15 May 1999 23:04:04 GMT
"R. Knauer" wrote:
> On Wed, 12 May 1999 17:20:40 GMT, "Douglas A. Gwyn" <[EMAIL PROTECTED]>
> wrote:
> >If you dispute that the test accomplishes the above, you should
> >explain where it fails.
> It fails when the TRNG outputs an "abnormal" sequence, which is itself
> perfectly normal.
No, the test works fine, because that "abnormal" circumstance occurs
no more than once per 20,000,000,000 key bits, on average, for a
properly functioning TRNG, just as specified.
If that is your best shot, then you should give up the argument.
> You would condemn a piece of metal because the atoms that comprise it
> do not stay close to their origin when they diffuse.
If I'm trying to measure a diffusion coefficient (which I have
actually done) and leave the experiment unattended overnight, when
I return the next day to find that instead of a nice exponential
penetration, somehow the entire slug of diffusant has formed into a
Dilbert figurine, I would condemn the theory that the statistics of
diffusion properly account for the phenomenon, no matter how much
you assure me that "it could be an anomaly". It is vastly more
likely that some causal factor other than diffusion was involved.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: On Contextual Strength
Date: Sat, 15 May 1999 23:18:56 GMT
Bryan Olson wrote:
> Try and follow: my notion of strength allows valid scientific
> hypothesis that a cipher is strong; the hypothesis is falsifiable.
> If the cipher is not strong then there necessarily exists evidence
> that proves it is not strong.
> If a cipher is strong under the idea I proposed, then _no_
> adversary can break it since a break does not exist.
I missed the start of this thread, but from the tone, it is another
waste of effort.
There is a conceptual problem with any notion of "there exists
evidence". For any practical cryptosystem where the key length
is substantially less than the message length, the "lucky guess"
method of solution "exists" in that sense: if the key is guessed,
then it can be demonstrated to be correct (beyond reasonable doubt).
It seems evident that no such system could be hardened against
such a "break".
A useful criterion has to be phrased in terms of "expected work
factor for some specified threshold success rate against any
deterministic algorithm", or something along those lines.
------------------------------
From: [EMAIL PROTECTED]
Subject: Hmm, I wonder if I got this right
Date: Sat, 15 May 1999 23:13:33 GMT
Am I right (I hope...)
A differential attack is where you find a common delta dX in the input
that satisfies a delta in the output dY with a higher (then equal)
probility. From this subkeys can be suggested. If only a subset of the
keyspace generates this, then one could find a suggested key faster
then brute force.
A linear attack tries to create some linear equation with a probabilty
greater then 1/2, which maps a bit(s) from input->key->output. If this
linear equation holds true, then the output/input can be elimiated from
the linear equation leaving only the key.
Questions
1) Does multiple approximations (linear) or deltas (differential) aid
in the attack, or only the one with the highest probabilty.
2) Can you predict which subset of the keyspace will bare true
(greater then 1/2) for a given approximation or delta? I mean to ask,
do you just try through brute force which keys will work?
3) Can a cipher emit differences, and have the key undectable (or
invalid for the most probable delta)?
4) What is the mathematical method(s) for making linear/diff. attacks
difficult?
Thanks in advance,
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Thu, 13 May 1999 12:24:55 GMT
Reply-To: [EMAIL PROTECTED]
On Wed, 12 May 1999 16:42:00 -0400, [EMAIL PROTECTED] wrote:
>> If you dispute that the test accomplishes the above, you should
>> explain where it fails.
>Now I simply have to take excpetion to that. You are asking him to do
>something that we've have ample evidence (overwhelimg, even inundating
>evidence) that he is not capable of performing.
>How very unfair! But conclusive.
You need to read Feller and Li & Vitanyi.
Bob Knauer
"There is much to be said in favour of modern journalism. By giving us the opinions
of the uneducated, it keeps us in touch with the ignorance of the community."
-- Oscar Wilde
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Europe and USA encryption export restrictions
Date: Sat, 15 May 1999 23:23:50 GMT
Nils Zonneveld wrote:
> I have to admit that I know very little about encryption, but what I do
> know is that today browser software for europe is equipped only with 40
> bits encryption. Due to USA export restrictions the 128 bits encryption
> version is not available. This makes on-line banking[1] impossible and
> cripples e-commerce.
That last sentence is wrong, as you yourself imply when you continue:
> There are in fact European made encryption algorithms that offer more
> protection then 40 bits and even go further then 128 bits.
Indeed, there is no reason why the 128-bit-keyed encryption modules
couldn't be provided by some source not located within the US.
The whole business is sickeningly stupid, made worse by politicians
who don't understand what they're trying to regulate.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Musing on and Factoring of a (special) 782-bit Modulus
Date: Sat, 15 May 1999 23:26:24 GMT
Ted Kaliszewski wrote:
> Now, the interesting question remains why is this example confounding
> the complexity arguments?
It doesn't. The key is to find a method for efficiently factoring
the product of *randomly chosen* large primes.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: [Q] Are all encryption algorithms based on primes?
Date: Sun, 16 May 1999 00:11:38 GMT
In article <[EMAIL PROTECTED]>,
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> Jessie wrote:
> > Are all encryption algorithms based on the fact that it is
> > difficult to factor a number which is the product of two LARGE
> > primes?
>
> No.
>
Also some algorithms use numbers or polynomials which are relatively
prime to another number, polynomial or field. Like Safer, uses 45
which is relatively prime to 257, which allows 45**257 to have 256
equally valid outputs.
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: Nathan Kennedy <[EMAIL PROTECTED]>
Subject: Re: Strength of PGP 1.0 conventional block cipher?
Date: Sat, 15 May 1999 21:36:12 +0800
David Crick wrote:
>
> David Crick wrote:
> >
> > Well I now have possesion of something which calls itself PGP 1.0 :)
> >
> > Public key length options are 286, 510 or 990 bits, hashing is MD4,
> > compression is LZHuf and conventional encryption is an enhancement
> > of "Charles Merritt's algorithm".
> >
> > I just wondered how secure the latter is ~8 years on. Has it held
> > up, or is it an interesting exercise for budding cryptologists?
>
> I hasten to add that I'm interested in attacks other than brute
> force!
I don't know, but I heard that an early PGP block cipher (with something
like "barrel-rolling"??) was weak. MD4 is broken, IIRC (even MD5 has
weaknesses). Obviously, these aren't the state-of-the-art algorithms, and
you don't want less than 1024 bits to your keys with Twinkle in the
making...
Nate
------------------------------
From: [EMAIL PROTECTED]
Subject: Security
Date: Sun, 16 May 1999 01:41:35 GMT
It's funny... I have been reading papers about ciphers, then I see
their attacks, then I see new attacks, and new ones... etc...
My question is... Is the measure of security the effort required to
isolate one valid solution (the key, or plaintext, or both) from any
given ciphertext (and plaintext)? Also given that there is no limit to
the number of algorithms possible, wouldn't there always exist at least
one method faster then brute force for any given algorithm (other then
a proper OTP)? And the given security is the memory/effort required
for any given 'crack'.
Also how many attacks presented are really practical? In theory a lot
of them are good (slide attack, anything with chosen- ) but are they
actually effective (and 2**43 chosen plaintext is not really effective
in my eyes).
Tom
--
PGP public keys. SPARE key is for daily work, WORK key is for
published work. The spare is at
'http://members.tripod.com/~tomstdenis/key_s.pgp'. Work key is at
'http://members.tripod.com/~tomstdenis/key.pgp'. Try SPARE first!
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Lemming and Lemur
Date: 15 May 1999 20:18:21 -0700
In article <7hj2vp$foc$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> >Where does the relation P[0] = C[0] come in?
>
> The F function in Lemming is only weak when P[0]=C[0]. For
> example, pick an arbitrary P and C such that P[0]!=C[0]. Then
> the functions F[P] and F[C] will use different elements of the
> key array. In this case, there are always keys that satisfy both
> F[P]=P' and F[C]=C', so there is no way to tell whether the true
> key satisfies both of those. There is no way to recognize the
> slid pairs, so the F function is not weak. That's why only slid
> pairs with P[0]=C[0] are useful.
Now I got it! Thanks for the explanation.
------------------------------
Date: Sat, 15 May 1999 21:39:40 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Europe and USA encryption export restrictions
Douglas A. Gwyn wrote:
>
> Nils Zonneveld wrote:
>
> Indeed, there is no reason why the 128-bit-keyed encryption modules
> couldn't be provided by some source not located within the US.
>
> The whole business is sickeningly stupid, made worse by politicians
> who don't understand what they're trying to regulate.
Weeellll.... it may sound silly, except that those same politicians will
never forget that they essentially won a number of wars based on their
ability to intercept and decrypt enemy codes. Who knows but that some
of those people -exist- because their fathers survived the war because
some U-boat or I-boat message was decrypted at exactly the right time?
"War, after all, *is* hell."
I still remember a poster I saw at the Cryptologic Museum at Fort Mead.
It showed a WW2 poster "Loose Lips Sink Ships" and added, "The Message
Is Still The Same." Good point. :-/
Anyhow... the good news is that even this export-control law is not
considered sacrosanct within the US Government. It's being debated
rather hotly now. One day it will be changed. How or when, I can't
hazard a guess. It must be tough to reconcile the "Loose Lips" view,
which of course is valid, against the "E-commerce" and European views,
which of course are valid too.
Damn tough problem, actually ... especially when you are setting policy
for an entire nation of however-million people. Very difficult to
debug. I wouldn't want to be, so to speak, the developer of THAT one.
------------------------------
From: [EMAIL PROTECTED] (Fredrik Olofsson)
Subject: Re: AES what's up?
Date: 10 May 1999 11:45:16 GMT
[EMAIL PROTECTED] wrote:
: What's up with AES? Anything new? I dunno...
: I have just finished reading all the papers last week, they are good. I think
: the top two should be RC6/Twofish, since both seemed to have lots of work put
: into them. Twofish is more public, but I think a little harder to implement
: then RC6. Cast-256 looks good too as does Rijndael.
: Tom
What about MARS then? :)
/f0n
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Crossposted-To: talk.politics.crypto
Subject: --- sci.crypt charter: read before you post (weekly notice)
Date: 16 May 1999 05:00:35 GMT
sci.crypt Different methods of data en/decryption.
sci.crypt.research Cryptography, cryptanalysis, and related issues.
talk.politics.crypto The relation between cryptography and government.
The Cryptography FAQ is posted to sci.crypt and talk.politics.crypto
every three weeks. You should read it before posting to either group.
A common myth is that sci.crypt is USENET's catch-all crypto newsgroup.
It is not. It is reserved for discussion of the _science_ of cryptology,
including cryptography, cryptanalysis, and related topics such as
one-way hash functions.
Use talk.politics.crypto for the _politics_ of cryptography, including
Clipper, Digital Telephony, NSA, RSADSI, the distribution of RC4, and
export controls.
What if you want to post an article which is neither pure science nor
pure politics? Go for talk.politics.crypto. Political discussions are
naturally free-ranging, and can easily include scientific articles. But
sci.crypt is much more limited: it has no room for politics.
It's appropriate to post (or at least cross-post) Clipper discussions to
alt.privacy.clipper, which should become talk.politics.crypto.clipper at
some point.
There are now several PGP newsgroups. Try comp.security.pgp.resources if
you want to find PGP, c.s.pgp.tech if you want to set it up and use it,
and c.s.pgp.discuss for other PGP-related questions.
Questions about microfilm and smuggling and other non-cryptographic
``spy stuff'' don't belong in sci.crypt. Try alt.security.
Other relevant newsgroups: misc.legal.computing, comp.org.eff.talk,
comp.org.cpsr.talk, alt.politics.org.nsa, comp.patents, sci.math,
comp.compression, comp.security.misc.
Here's the sci.crypt.research charter: ``The discussion of cryptography,
cryptanalysis, and related issues, in a more civilised environment than
is currently provided by sci.crypt.'' If you want to submit something to
the moderators, try [EMAIL PROTECTED]
---Dan
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Lemming and Lemur
Date: Sun, 16 May 1999 05:34:56 GMT
In article <7hjjpg$s9k$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> > >Slid pairs should be found after about 2^{64.5} known texts
> > That's only true for weak F functions.
> No it's true for any function, it is less useful if your cipher uses
> different round functions.
No. If the F function isn't weak, then you can't recognize slid pairs,
so you'll never find one. If the f function is only sometimes
weak, then you'll only sometimes recognize slid pairs, so it will
take longer to find one.
> > The F function in Lemming is only weak when P[0]=C[0].
> That is not a slid pair. A slid pair would be P'[n] = C[n-1], i
> think.
In Lemming, P[0] is defined to be the first byte of P. Slid pairs
are only recognizable when P[0]=C[0].
> > It looks like the same changes will help both Lemming and Lemur.
> > At this point, I'm leaning toward simply XORing the round number
> > with the index, though that slows it down. An alternative would
> > be to shuffle the words of the block in a round-dependent way.
>
> Xoring a constant is only usefull to prevent degenerative cycles.
The round number isn't constant. It changes each round, by definition.
> Having fixed rotations for example is *only* usefull in gettings bits
> in a position you need them.
Shuffling words differently on each round would stop the slide attack.
> Shuffling in each round may slow the cipher down excessively
> unless you have a faster method.
It depends on the architecture. For a Pentium with 32-bit registers,
shuffling the key in 32-bit chunks can be done in zero time. Think
about writing Lemming in assembly language, unrolling the loop, and
changing the definition of which register holds which part of the
block after each round. If you do it right, you get round-dependent
shuffling for free.
LCB
--== Sent via Deja.com http://www.deja.com/ ==--
---Share what you know. Learn what you don't.---
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: On Contextual Strength
Date: Sun, 16 May 1999 00:09:30 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn"
<[EMAIL PROTECTED]> wrote:
>
> ... For any practical cryptosystem where the key length
> is substantially less than the message length, the "lucky guess"
> method of solution "exists" in that sense: if the key is guessed,
> then it can be demonstrated to be correct (beyond reasonable doubt).
> It seems evident that no such system could be hardened against
> such a "break".
The error in this assumption is obvious to me. That the key should be
practically incapable of being guessed and specifically difficult to be
reverse engineered. In a system where a key might be made to work for one
message, but in effect be the wrong key, a "lucky" guess means finding
yourself in a dead-end passage in a multidimensional maze.
It is traditional to think in terms of linear keys, which might be
supportive of your statement. Non-linear keys may not be.
>
> A useful criterion has to be phrased in terms of "expected work
> factor for some specified threshold success rate against any
> deterministic algorithm", or something along those lines.
Do you mean deterministic as in one key with one plaintext = one
ciphertext, or do you allow for something else?
--
Weathermen prosphesize and insurance companies predict, while both pretend to be doing
the other to get an audience.
------------------------------
** 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
******************************
