Cryptography-Digest Digest #425, Volume #9 Mon, 19 Apr 99 21:13:04 EDT
Contents:
Magenta and DFC descriptions added to web site (John Savard)
Re: FSE-6 Report: Slide Attack ("Douglas A. Gwyn")
Re: Comments on Boomerang Attack Sought (John Savard)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(John Savard)
Re: PGP=NSA (what is it about crypto?) ([EMAIL PROTECTED])
Re: Question on confidence derived from cryptanalysis. ("Trevor Jackson, III")
Re: Extreme lossy text compression (D. J. Bernstein)
Re: Question on confidence derived from cryptanalysis. ("Douglas A. Gwyn")
NSA not so bad after all? (was Re: RC6 new key standard from AES conference?)
([EMAIL PROTECTED])
Re: RC6 new key standard from AES conference? ([EMAIL PROTECTED])
Re: Charles Booher is a complete IDIOT! (Chem-R-Us)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Magenta and DFC descriptions added to web site
Date: Mon, 19 Apr 1999 21:51:46 GMT
After a very long hiatus, I have added descriptions of two more of the AES
candidates to my web site.
The description of Magenta will need to be improved by adding some more
diagrams; as it is, there is one diagram, added to a page largely derived
from some of my recent posts.
The description of DFC is very short, and does not discuss the key
schedule. I have read in a recent post that DFC includes a key-dependent
bit transpose, which I did not encounter in the paper describing it, so it
is possible my description is wrong (or perhaps there was confusion, and
this is a feature of HPC, whose algorithm I have been unable to examine in
detail).
John Savard ( teenerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: FSE-6 Report: Slide Attack
Date: Mon, 19 Apr 1999 21:30:04 GMT
[EMAIL PROTECTED] wrote:
> BTW, are chosen-plaintext attacks really pratical? I mean they make
> good theory but are they actually used 'in the field'?
It depends on the cryptosystem. For example, in a public-key system,
you can encrypt as many plaintexts as you like, and they are all under
your control.
For secret-key systems, you don't generally have such control over
what is encrypted, but often you have *some* influence. For example,
the meaning of a Japanese code word, a place name, was in doubt
during WWII, and to determine which of two alternatives it was, a
bombing run was ordered against one of the places, and Lo! the
intercepted damage report used that code word to denote where the
bombs had just fallen. While there had not been *total* control
over the plaintext, there had been enough influence for the purpose.
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Comments on Boomerang Attack Sought
Date: Mon, 19 Apr 1999 22:07:40 GMT
[EMAIL PROTECTED] (John Savard) wrote, in part:
>James Frey <[EMAIL PROTECTED]> wrote, in part:
>>I looked at you diagram, but it is labeled "butterfly attack"
>>instead of boomerang attack. Is that an error
>Yes, it certainly is.
And I finally got around to correcting that Freudian slip.
John Savard ( teenerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Mon, 19 Apr 1999 22:05:58 GMT
[EMAIL PROTECTED] wrote, in part:
> DES, the mother of all ciphers, uses only XORs, substitutions, and
> bit transpositions. When I designed Frog, I decided to use only
> XORs and substitutions (and continue the tradition), even though I
> knew that ADD has better diffusion properties than XOR. In all
> synchronous processors ADD takes the same time as XOR and I think
> now that I made a bad decision then.
While at first the poster does appear to be making the important mistake of
forgetting that most block ciphers do include one complex operation - the
S-box - reading the post further, and noting the examples he used, such as
SIGABA, led me to the conclusion that he wasn't really asking about why not
many block ciphers use, say, multiply instructions, but instead was asking
why they don't use more involved structures with a little creativity.
In other words, I think he was asking why block ciphers weren't more like
FROG! (My original reply to his post goes into this at greater length.)
John Savard ( teenerf<- )
http://members.xoom.com/quadibloc/index.html
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: PGP=NSA (what is it about crypto?)
Date: 19 Apr 1999 19:31:10 GMT
Reply-To: [EMAIL PROTECTED]
Who let this flake in here?
And what is the deal with cryptography attracting these ranting lunatics?
"Charles Booher" <[EMAIL PROTECTED]> writes:
>Zimmerman can fill you in on the details.
>
>PGP is now owned by Network Associates.
>
>Network Associates does $$$$ buisness with the NSA.
>
>Mostly they sell Sniffers to the NSA.
>
>The NSA also buys Ultra SPARCS by the truck load.
>
>THE NSA CAN READ MOST PGP MESSAGES!!
>
>There are only 1,000,000,000 possible PGP key pairs with DF implemenation in
>PGP 6.0
>
>Every PGP key pair has been calculated, stored, and sorted.
>
>
>
--
Lamont Granquist ([EMAIL PROTECTED])
ICBM: 47 39'23"N 122 18'19"W
------------------------------
Date: Tue, 20 Apr 1999 06:37:03 -0400
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Question on confidence derived from cryptanalysis.
Geoff Thorpe wrote:
>
> Hello,
>
> "Douglas A. Gwyn" wrote:
> > (I'm not suggesting that academics haven't made useful
> > contributions to the state of the art, just that their
> > work does not define the total state of the art.)
>
> Oh I agree completely - I was just taking issue with what I perceived to
> be the following idea: Until we actually break it, or *prove* it secure,
> we have no more measure of strength for it than for another (less
> "investigated") one. I feel that quite the opposite is true - it IS a
> very appropriate statistical measure of strength, and moreover the only
> realistic one we have to work with. If the total state of the art stays
> roughly in sync with the academics, albeit "they" may have a couple of
> things up their sleeves and they may often get the jump on us by a few
> months/years with various developments, then we can make reasoned
> guestimations on the strength of a cipher against them based on the
> strength of a cipher against us.
This usage of the term strength may be inappropriate. As a substitute I
offer the term confidence. The difference is partly connotative, but an
example may illustrate a real distinction worth preserving. In a
restricted set of cases one might use a weak cipher, knowing that it is
theoretically breakable, but also knowing that the adversaries (threat
model) cannot break it in practice. The reasons for their inability
might be lack of resources, cruptographic sophistication, or as simple
as one message sent one time. In this situation we have confidence that
the cipher will protect the secret, but the cipher is not strong.
The practical test of ciphers is valid in the sense that it can give us
confidence, but it cannot give us strength. In a sense the practical
test of exposure to many and varied attacks gives us a kind of lower
bound on the types of attacks a cipher might not resist. Once a cipher
has survived a gauntlet, we know that any successful attack must be
fairly sophisticated, optomized agains the particular cipher, or simple
but based on a radical insight or advance in the field (linear,
differential, boomerang, or sliding attacks appear to be advances ).
But this lower bound does not tell us *anything* about the "strength" of
the cipher (the units for which are completely undefined), but tells us
a lot about the confidence we might repose in the cipher.
Ritter appears to be after strength. Thorpe appears to be after
confidence.
>
> > > Mathematical problems - that is what I was referring to ...
> >
> > Yes, cryptology is largely applied mathematics, but
> > practical cryptanalysis has evolved in the context of
> > operational experience that is largely unavailable to
> > outsiders, and that has caused a substantial difference
> > between insiders and outsiders in their aims and methods.
>
> Well yes and no ... applied mathematics has a handy of way of pushing
> things along nicely particularly in the area of computation (complexity)
> problems. "Their" ideals may be different to ours but I doubt their aims
> or methods are ... everybody would love to break an established cipher
> (with the possible exception of the patent holder), everybody would love
> to *prove* a cipher secure (with the possible exception of the patent
> holder's competition). I dare say the NSA et al have less motivation to
> chase down some of the more daunting theoretical possibilities for
> weaknesses in algorithms, especially when in reality, so many of them
> lead nowhere or to advances that are at best - theoretical.
>
> "They" have budgets (albeit big ones) and they probably have things
> they'd rather spend it on (satelites, lobbying, hardware, breaking
> implementations, breaking installations, etc). OTOH, having been
> post-grad in a mathematics department before I know very well that this
> obsession for looking in every nook and cranny of all things theoretical
> is exactly the sort of thing academics get off on. Cracking ciphers (ie.
> the actual algorithm itself, not the practical implementation details
> that may be vulnerable) is much more the meat and veg of academics who
> like to play and write papers. "They" just want information, and I'm
> guessing just do whatever they got to do to get it - and searching
> endlessly for little theoretical weaknesses is probably not their top
> priority. That's not to say they don't do it and do it very well, but I
> doubt their considerable advantages in resources are put so much to this
> task as to make our abilities so incomparable or unrelated as some might
> believe.
A good point. However, we canot deal with their (secret) intentions,
but must anticipate their possible (even more secret) capabilities.
Thus amplifying the threat model is a sensible thing to do. It
eliminates some of the risk of catastrophically underestimating them by
enhancing the risk of expensively overestimating them.
An appropriate paranoia dictates that we accept the costs of
overestimation.
>
> > Some problems, like efficient factoring, are obviously
> > relevant, and unlikely to be achieved in secret without
> > happening in the outside around the same time. Other
>
> I agree but I doubt very much Mr Ritter does.
>
> > breakthroughs have been kept secret for decades, in some
> > cases. So there really is reason to fear that the most
> > advanced "enemies" might know how to easily crack some
> > system you use that appears uncrackable to all outsiders.
>
> I know - and there's a lot of targets out there so the odds are on that
> at least one of them has fallen completely to an "unpublished" source
> without our knowing it. However, I just think it's more likely to be
> something less well analysed in the "open" than something well analysed
> in the "open" for the reasons I've mentioned, and that Mr Ritter doesn't
> agree with.
It appears to me that he *does* agree (tho he can certainly speak for
himself), which is why he has repeatedly proposed the use of multiple
ciphers both to spread eggs across baskets, and to provide layered
security where warranted.
>
> On a related note (and all IMHO), bit-twiddling little ciphers are no
> less "mathematical" than effecient factoring. Discrete maths actually
> finds that cute little "permutation stuff" quite fashionable from my
> limited contact with it (and them). Factoring tends to interest (again
> from my limited contact) more the applied heads - meaning I'd give
> better odds to developments in faster optimizations on 64-bit platforms
> with super-dooper cache, than to fundamental breaks in the factoring
> algorithms [;-)
>
> > There is a significant difference between what is "well
> > established" in long-existing, well-funded cryptologic
> > organizations and what is "well established" in the
> > dispersed, high-turnover-rate academic community.
>
> True - and to agree with Mr Ritter for a moment, I think perhaps another
> risk is that the academics tend to show interest in things that interest
> them - where as the well-funded organisations you speak of more likely
> show interest in things that give them the best chance of accomplishing
> some objective. However, this pragmatic mind-set, albeit fearsome in
> many ways, might give us some hope that in the ethereal hights of trying
> (and hoping) to break an already well-studied algorithm, they probably
> are less hopeful, less obsessed, and more practical and realistic. After
> all, RSA, IDEA may be perfect but if Win95's TCP allows a
> password-sniffer to leak into your PC "they" have accomplished their
> objective and "broken" PGP as far as "they" are concerned.
>
> > There is a big problem in working in *applied* fields
> > academically, since it is harder to get academic
> > respect from publication of application or tutorial
> > papers instead of research papers. There are many
> > technologies that are well-known *in general* in the
> > research community, but their specific application to
> > cryptology is *not* well known.
>
> Probably quite true.
>
> > > We all know that risk - it's the probabilities that are open to
> > > debate. ...
> >
> > More precisely, the likelihoods.
> > The nice thing is that *relative* likelihoods can be estimated
> > and used to make decisions; e.g. "I need a cipher that <meets
> > certain requirements> -- pick one."
> > If the consequences of not making a decision are sufficiently
> > severe, then even an uncertain decision can be better than
> > letting the uncertainty stop you from making a decision.
>
> Exactly, and well said.
>
> > > Me, I'm going to stick with RSA and triple-DES for a while.
> >
> > In a well-designed cryptosystem, these do seem sufficiently
> > secure against realistic threats for the near future. Any
> > vulnerabilities would most likely occur elsewhere in the
> > system/protocols, not in these encryption algorithms as such
> > (assuming of course a long RSA key, and 168-bit 3DES key).
>
> I think that too, but as Mr Ritter might say - you are already in the
> abyss and are naive if you think that. If that is so, I am comfortable
> in my naivety.
>
> > That seems to be part of Ritter's aim, but others seem to
> > think that during cryptanalysis the stages have to be peeled
> > like an onion, and they assume that there is not enough
> > pattern available at the next-to-outermost layer for there
> > to be any chance of peeling the outer layer off.
>
> Well hopefully someone will look at this, and demonstrate some success
> from it. Results speak for themselves, even to ivory tower academics
> [;-)
>
> > > And this can't be achieved within ONE cipher? When you start talking
> > > multiple algorithms, you instantly start talking interoperability
> > > and standardisation headaches.
> >
> > That's a significant concern, because breakdowns in operational
> > procedure often provide the enemy analyst the entering wedge he
> > needs to crack a system.
>
> Exactly, and if I resort to using a different cipher every week ... the
> cryptanalysts will not keep up with them satisfactorily and I have a lot
> more confidence that "they" WILL be breaking my traffic on a
> semi-regular basis.
Layered algorithms do not dictate expensive or complex operational
requirements. The implementation of a layered cipher needs some care,
but no more than any other secure system. This issue appears to be a
red herring.
------------------------------
From: [EMAIL PROTECTED] (D. J. Bernstein)
Subject: Re: Extreme lossy text compression
Date: 19 Apr 1999 20:48:18 GMT
Here's an analogy in base 10. Suppose you want to compute
2718281828 r^4 + 4590452353 r^3 + 6028747135 r^2 + 2662497757 r
modulo p, where p = 10^30-1 and r = 314159265358979323846264338327. You
do some precomputations with r:
r^1 mod p = 3141592653 10^20 + 5897932384 10^10 + 6264338327
r^2 mod p = 2631235735 10^20 + 1304915222 10^10 + 3466068927
r^3 mod p = 7883992070 10^20 + 5909899612 10^10 + 2554294263
r^4 mod p = 9595247344 10^20 + 1716075106 10^10 + 5252936926
Now you can compute the (approximately 40-digit) number
2718281828 (r^4 mod p) + 4590452353 (r^3 mod p)
+ 6028747135 (r^2 mod p) + 2662497757 (r mod p)
with 3 dot products of ten-digit numbers, totalling 12 multiplications;
and then you can easily reduce the result modulo p.
Terry Ritter <[EMAIL PROTECTED]> wrote:
> How do you avoid multi-precision operations, multiply and divide, when
> dealing with a 128-bit integer hash?
I don't know what distinction you're trying to draw. These _are_
multiprecision operations. The same techniques can be used in many other
multiprecision arithmetic problems.
> Indeed, *any* linear system is normally a bad idea for authentication
On the contrary. See the hash127 man pages, or my previous postings, for
several safe authentication methods.
> When a linear system is acceptable, I see no serious theoretical
> consequences from splitting it into smaller subsystems with about the
> same total state.
Again: The maximum collision probability for four independent CRC-32s on
a b-bit message is roughly b^4/2^128. That grows disastrously with b.
With today's networking technology an attacker can break that system in
a matter of minutes.
In contrast, CRC-128 has maximum collision probability around b/2^128,
and hash127 has maximum collision probability around 3b/2^133.
---Dan
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Question on confidence derived from cryptanalysis.
Date: Mon, 19 Apr 1999 21:49:34 GMT
Geoff Thorpe wrote:
> ... I dare say the NSA et al have less motivation to
> chase down some of the more daunting theoretical possibilities for
> weaknesses in algorithms, especially when in reality, so many of them
> lead nowhere or to advances that are at best - theoretical.
For example, several "significant" results in academic papers say
that certain systems can be broken with an inordinate amount of
resources, if 2^24 chosen plaintexts are used. It's hard to justify
such work when your job performance is measured by practical results
"in the field".
Generally speaking, Terry is right to be concerned over the unknown,
but some risks are greater than others. The specific algorithms you
mentioned previously are among the better risks. If the stakes are
really high, thoroughly studied systems are better bets than untested
ones. That's not to say that we don't need new, better systems, but
it takes *time* to subject them to enough testing and analysis to
develop confidence in them. Maybe some day we'll all understand that
Terry's approach (or David's) is a better way to go -- or maybe not.
------------------------------
From: [EMAIL PROTECTED]
Subject: NSA not so bad after all? (was Re: RC6 new key standard from AES conference?)
Date: 19 Apr 1999 22:35:54 GMT
Reply-To: [EMAIL PROTECTED]
[EMAIL PROTECTED] writes:
>after the smartcard
>debacle NIST declared that how well a competitor performs on smartcards will
>not have high priority in the competition.
You know, the Smartcard Debacle really has made me wonder about government
crypto vs. public crypto. Okay, this is all just based on what I've read
in sci.crypt on the AES conference, but my understanding is that Skipjack
performs much better in smartcard applications than all the AES candidates.
That's just adding to my impression that overall the government/NSA really
does seem to know what they're doing when it comes to crypto. With the
exception of its 56-bit key DES is really pretty damn good, SHA1 seems to
be a better choice than MD5, and Skipjack seems to be better (barring the
politically motivated and openly-known key escrow problem) than the AES
candidates. It also makes sense that the NSA wouldn't want to include some
kind of "hidden backdoor" as has been rumored about DES for ages. Figure
it out: from the NSAs perspective they have to assume that they could never
keep such a backdoor secret forever, and once it leaked out into the public
then the corporations and government agencies which use NSA-approved
crypto would never trust them again and NSA would lose its control.
Conclusion: NSA crypto can generally be trusted? (barring obvious design
choices like the DES 56-bit key or key escrow)
--
Lamont Granquist ([EMAIL PROTECTED])
ICBM: 47 39'23"N 122 18'19"W
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RC6 new key standard from AES conference?
Date: Mon, 19 Apr 1999 23:42:57 GMT
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Paul Rubin) wrote:
> In article <7ffi37$e77$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> >A completely new key scheduler will probably not be considered as a "tweak"
by
> >NIST, which means that Rivest will not be able to have this variant
considered
> >as the AES competitor. Probably this will not matter much: after the
smartcard
> >debacle NIST declared that how well a competitor performs on smartcards will
> >not have high priority in the competition.
>
> What debacle was that? I missed something.
>
> I think it is important that the AES perform reasonably well on smartcardts.
>
See the "Live from the Second AES conference" thread. In general the idea is
this: you only need AES on a smartcard if you need high levels of security;
but then the recently discovered practical attacks against smartcard
implementation of ciphers (particularly PDA) make today's smartcard
technology of little use for high security applications.
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Chem-R-Us <[EMAIL PROTECTED]>
Subject: Re: Charles Booher is a complete IDIOT!
Date: Mon, 19 Apr 1999 17:45:10 -0700
"Gurripato (x=nospam)" wrote:
>
> >0695964556368027177090443413373454477475448244069409410027461521549561837479
> >42618930038144511578375279779164644494978894252889762924768717093;
> >
> >
> >
> And this proves what, please?
Ye Gods, man! Don't quote the whole thing just to add a single line.
Haven't you ever seen:
<snip>
--
Chem
------------------------------
** 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
******************************
