Cryptography-Digest Digest #353, Volume #14 Mon, 14 May 01 15:13:01 EDT
Contents:
Re: Is Differential Cryptanalysis practical? (Mark Wooding)
Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm) ("Douglas A.
Gwyn")
Re: Avoiding RSA padding altogether? (Mark Wooding)
Re: Bleaming strock cipher ("Paul Pires")
Re: good x86 coders (help please) ("Douglas A. Gwyn")
Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm) ("Douglas A.
Gwyn")
Re: Is Differential Cryptanalysis practical? ("Douglas A. Gwyn")
Re: DES Crypto Myth?? ("Douglas A. Gwyn")
Re: DES Crypto Myth?? (David Wagner)
Re: JPEG also problematic (Pawel Krawczyk)
Re: which public key algorithm is easy & gd to use? (Paul Crowley)
Re: Avoiding RSA padding altogether? ("Jakob Jonsson")
Re: how to blind a linear transform (Mike Rosing)
sample ebcrypt code in VB ("normangrant")
Re: Bleaming strock cipher (John Myre)
Re: What Is the Quality of Randomness? ("Douglas A. Gwyn")
best algo ("Nils Johansson")
Re: Is Differential Cryptanalysis practical? (Paul Crowley)
Re: Not a realistic thing to do......Why? ("Tom St Denis")
Re: how to blind a linear transform ("Tom St Denis")
Re: best algo ("Tom St Denis")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Is Differential Cryptanalysis practical?
Date: 14 May 2001 16:10:15 GMT
Scott Fluhrer <[EMAIL PROTECTED]> wrote:
> Tom, now be kind to the poor designers of FEAL. Yeah, their designed
> turned out to be somewhat, errr, suboptimal. However, remember how
> many of your designs have been broken in the past.
The really sad thing about FEAL is the number of times everyone went
around the break/tweak cycle before giving up. I'm amazed it wasn't
fairly quickly obvious that the round function was terrible.
Talking of the futility of tweaking broken ciphers, have you made any
more progress on Gift with a 15-bit rotate? ;-)
-- [mdw]
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm)
Date: Mon, 14 May 2001 15:57:28 GMT
"SCOTT19U.ZIP_GUY" wrote:
> ... No wonder violent crime is up in the UK you
> can't shoot the bastards that break into you own house.
Note: You don't have to actually shoot them; it's the fear
of being shot that has deterred many potential home invasions.
Just as the overwhelming majority of instances of self-defense
use of handguns in the US do not involve shots being fired.
It is true that there are newsgroups more appropriate for
extended discussions of this topic. However, the original
short mention was in context for the discussion, which as
David said, was related to an on-topic issue. It is the
nature of free development of ideas that they often stray
far from their origins. But it is important to draw
connections, in order to integrate one's total knowledge.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Avoiding RSA padding altogether?
Date: 14 May 2001 16:27:29 GMT
Paul Crowley <[EMAIL PROTECTED]> wrote:
> But I'd appreciate a brief first glance from those familiar with such
> schemes, to tell me whether this is obvously broken, already proposed
> and shot down, or otherwise not worth pursuing.
It sounds quite plausible to me. I don't suspect that security proofs
in the random oracle model will be particularly hard. (That said, I'm
not entirely sure I've managed to get my brain around the formal
definition of plaintext-awareness...)
-- [mdw]
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: Bleaming strock cipher
Date: Mon, 14 May 2001 09:45:35 -0700
John Myre <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> Paul Pires wrote:
> <snip>
> > ... diddle a few bits in each block according to a coin flip until the
> > parity from block to block spells out, "You Loose".
> <snip>
>
> "and I'm Tight".
Ok. That's a fairly sparse and obscure reply.
Depending on locality, it could mean frugal or
drunk. I imagine both could apply. I just wonder
if I'm missing something profound here.
Paul
>
> JM, the ocunter
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: good x86 coders (help please)
Date: Mon, 14 May 2001 16:11:00 GMT
Tom St Denis wrote:
> The problem is that if I optimize the code specially for the Athlon (which
> is what I am running) I lose out on all other platforms etc..
Indeed. That's why it is better to use highly-optimizing code
generators (usally with switches to select the target architecture)
in compiling a single portable program specification written in a
higher-level language, than to have *every* programmer working to
code by hand a complete set of optimized versions of the program.
This is sometimes a problem when there is too great a mismatch
between the HLL and the target architecture, but even then one
can often devise a single good intermediate-level model for the
relevant special low-level features, along with macros or other
tools to map the model onto the hardware; that approach is in
the long run less expensive than always hand-coding for each
specific target.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: ON-topic - UK crime statistics (was Re: Best, Strongest Algorithm)
Date: Mon, 14 May 2001 16:00:13 GMT
Jim D wrote:
> A little bit of communism would be the best thing that ever
> happened to Yankee-Doodle land.
Perhaps you haven't studied any competent history of the US,
but we did have more than a little bit of communist influence
among our intellectuals, which has had a continuing effect to
this very day.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Is Differential Cryptanalysis practical?
Date: Mon, 14 May 2001 16:29:45 GMT
[EMAIL PROTECTED] wrote:
> I think it's realistic to assume that the algorithm is known by the
> cryptanalyst.
> I think it is realistic to assume that the analyst has SOME chosen
> plaintexts
> with their corresponding ciphertexts (ye old "send it to the embassy"
> trick).
> I think its CRAP to assume that even an embassy is going to encrypt
> 2^(large # here)
> carefully chosen plaintext pairs for the analyst and I think its CRAP to
> assume that
> Joe PC User is going to encrypt 2^(small # here) carefully chosen
> plaintext
> pairs for the analyst (feel free to do whatever differential analysis
> you can
> with the commonly encrypted file headers).
> I'm not even sure that 2^49 chosen ASCII plaintexts is realistic.
It depends on how the cryptoalgorithm is embedded in a system.
For example, if all you need to do to try a probe is send a packet
on a high-speed Internet connection (might as well blast away in
full duplex), a huge number of trials is feasible, although not
quite 2^49 in this instance. Remember, DES is used in automatic
electronic funds transfer and other non-traditional applications.
I do agree that in traditional applications, attacks that require
such enormous numbers of known or controlled texts are not
significant security threats.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: DES Crypto Myth??
Date: Mon, 14 May 2001 16:23:34 GMT
David Wagner wrote:
> >So why do you think the NSA changed the S-boxes, given that the IBM team
> >had already optimized (s-boxes/cipher - take your pick) against
> >differential cryptanalysis?
> It's not clear that it happened this way.
In fact it didn't, but details of the IBM-NSA collaboration
are for some reason still not public. I think a properly-
phrased FOIA request might improve the public record on this.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: DES Crypto Myth??
Date: 14 May 2001 17:00:20 GMT
DJohn37050 wrote:
>I think I remember Don Coppersmith saying that the "T" stood for "twiddle" or
>some such.
"Tickle", I believe?
------------------------------
From: Pawel Krawczyk <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc,talk.politics.crypto
Subject: Re: JPEG also problematic
Date: Sat, 12 May 2001 11:46:08 +0000 (UTC)
In comp.security.misc Frank Gerlach <[EMAIL PROTECTED]> wrote:
> compression. This means that images have quite typical (visible, statistic
> and frequency-domain) characteristics. If bandwith is not a problem, I
> would just use images/sound samples with a very high amplitude resolution
> (24 or 32 bit). Of course, the amount of noise and its characteristics (in
> various domains) would have to be carefully analyzed. The information to
> be embedded would have to be carefully encoded to have similar statistic,
> frequency domain and eyeball-visible characteristics. And here the
> cat-and-mouse game starts: There are an infinite number of transformation
> domains and statistical tests "to be discovered". Whoever has the most and
> best math/signals analysis gurus will win..
I'm not sure if anyone already mentioned OutGuess (www.outguess.org)
by Niels Provos, which is a steganography package for JPEG format, that
tries its best to avoid breaking any characteristics natural for the
format. It also contains an utility to analyze and decode files hidden
with previous versions of the program ;) and some other steganography
tools for JPEG.
--
Pawe� Krawczyk *** home: <http://ceti.pl/~kravietz/>
security: <http://ipsec.pl/> *** fidonet: 2:486/23
------------------------------
Subject: Re: which public key algorithm is easy & gd to use?
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Mon, 14 May 2001 17:18:33 GMT
[EMAIL PROTECTED] (DJohn37050) writes:
> I would say that DSA/DH is the easiest to understand. RSA has lots of
> tricky stuff in key gen and it needs to be all kept secret, while
> DSA/DH simply uses a random number in the correct interval as a
> private key and does the basic arithmetic operation (MODEXP) to
> calculate the public key. It also is MUCH easier to VALIDATE the
> resulting pubic key to ensure that they were no arithmetic boo boo's.
I would vote DHAES for encryption, and Schnorr for signatures. Naive
RSA is insecure, and explaining OAEP is too big a job. Schnorr is
certainly simpler than DSA - when called upon to explain DSA, I've
offered to explain Schnorr instead, since I can hold that in my
head...
--
__ Paul Crowley
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
"Conservation of angular momentum makes the world go around" - John Clark
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: Re: Avoiding RSA padding altogether?
Date: Mon, 14 May 2001 19:21:06 +0200
"Paul Crowley" <[EMAIL PROTECTED]> skrev i meddelandet
news:[EMAIL PROTECTED]...
> Something I wondered while reading the descriptions of OAEP and PSS.
> Is there a simpler way to ensure that the input to RSA is unstructured
> and fairly pseudorandom, by moving away from thinking of it as
> "padding" altogether?
>
> For encryption, it seems like something akin to DHAES would be
> applicable to RSA: choose a random number R fairly between 0 and N-1
> (where N is the RSA modulus), encrypt R using RSA without padding and
> send that as a header, and use Hash(R) as a secret key to encrypt and
> MAC your message.
Indeed, Victor Shoup suggests this method ("simple RSA") in his proposal for
an ISO standard for PKE; see Section 8 in the very first paper at
http://shoup.net/papers/. The construction is provably secure.
> For signing, seed a CPRNG with the hash of your
> message and a nonce, use the CPRNG to choose a pseudorandom number
> fairly between 0 and N-1, then sign that without padding.
Remove the nonce, and you have Full Domain Hashing (FDH) introduced by
Bellare and Rogaway in 1993 ("Random oracles are practical...",
http://www-cse.ucsd.edu/users/mihir/). Coron has given an improved security
proof, which was presented at CRYPTO last year; the proof is very short.
Unfortunately, the security proof for FDH is weaker than the security proof
for PSS. With a random nonce of length say 160 bits, I think the security
proof will be improved (without having checked all details, I guess that the
proof will be just as strong as the PSS proof). Yet, the nonce must be
transmitted together with the message and the signature, which means some
overhead (silly, yes, but standards organizations tend to consider this a
drawback).
The conclusion is that your suggestions are most appropriate -- the
encryption scheme might even be subject to standardization (Shoup is the
editor of the ISO standard).
Jakob
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: how to blind a linear transform
Date: Mon, 14 May 2001 12:43:44 -0500
Tom St Denis wrote:
>
> At my work I have the job of analyzing a blinded linear transform. The idea
> (don't laugh!) is to perform a linear transform in software such that an
> attacker can examine the software but not see the transform.
>
> Our trick is to make an addbox such that it works like this (the linear
> transforms are in F_2 and are square and full rank)
>
> The input is <a,b>
>
> 1. Perform a "unblinding" substitution getting a' = S1[a], b' = S2[b],
> previously a and b were "blinded" via S1^-1 and S2^-1
> 2. Do the linear transform on a' and b' (i.e matrix multiply)
> 3. Add the result in GF(2) i.e c = M1a' + M2b'
> 4. Blind c, i.e c' = S3[c]
>
> The output is c'.
>
> My original analysis considered the inputs a,b to be normal (no blinding).
> My attack then works on finding where c is zero and trying to figure out
> which pairs of M1/M2 were the original matrix. I then simplified the attack
> to say solve for rows of M1/M2 at a time and worry about their order
> later... etc.. pretty demolished.
>
> My question is how to attack this when the blinding is performed. I can't
> for the love of myself figure out how, but I have a hunch it's not at all
> that hard. Plus it would be fun to set this company back some since their
> notion of "whitebox" crypto is kinda silly.
Do the same thing, but now you've got an extra step. If c = 0, then c' = constant.
Are the blindings part of the key? If not, then a' and b' are constants related
to a and b for purposes of plain-text/cipher-text attack. If they are key related,
then you're attacking the key scheduler in effect.
that's the whole point of the blinding - to make the attack more difficult :-)
Patience, persistence, truth,
Dr. mike
------------------------------
From: "normangrant" <[EMAIL PROTECTED]>
Subject: sample ebcrypt code in VB
Date: Mon, 14 May 2001 07:52:00 +0200
Hi all
I have been using ebcrypt for a few projects. Recently I needed to use the
RSA public/private key portion of the code. Obviously could not get it
working!!. Does anyone have sample VB code using Ebcrypt to generate key
sets
thanks in advance
Norman
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: Bleaming strock cipher
Date: Mon, 14 May 2001 11:53:32 -0600
Paul Pires wrote:
>
> John Myre <[EMAIL PROTECTED]> wrote in message news:[EMAIL PROTECTED]...
> > Paul Pires wrote:
> > <snip>
> > > ... diddle a few bits in each block according to a coin flip until the
> > > parity from block to block spells out, "You Loose".
> > <snip>
> >
> > "and I'm Tight".
>
> Ok. That's a fairly sparse and obscure reply.
> Depending on locality, it could mean frugal or
> drunk. I imagine both could apply. I just wonder
> if I'm missing something profound here.
No. I just meant it as the opposite of "Loose"; I imagine
you meant "Lose" (as in "not win"). It could also be seen
as a misspelling of "Right". Besides being obscure, I
suppose it's sophomoric, as well. sigh.
JM
(Ok, for the *really* confused out there, I imagined the
encryption to be intended to spell out
"You Lose, and I'm Right"
but mistakenly came out as
"You Loose, and I'm Tight"
which has two mistakes that result in the words still
being in opposition.)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: What Is the Quality of Randomness?
Date: Mon, 14 May 2001 17:26:23 GMT
Benjamin Goldberg wrote:
> There is no such thing as a random sequence, only a random source. Any
> bitstring, once it's been seen, has zero randomness. ...
The way I usually put this is that all forms of (possibly imperfect)
knowledge are contextual. A particular datum evaluated rationally
is in general consistent with more than one of a set of mutually
contradictory conclusions, especially so when the set is formed by
arbitrary classifications that don't match up well to the way the
world really operates.
Some relevant forms of contextual knowledge are: probability,
classification, information content, and randomness. There is a
theorem somewhere (probably in Good's work) to the effect that
rational decision making (appropriately defined) requires
consideration of all available context (some of which is usually
called "data", some of which is information about applicable
constraints, and some of which is knowledge in a previous,
narrower context).
The notion of "randomness" is inherently tied to the idea of
lack of foreknowledge. Shannon explained how to measure the
information content in the difference between foreknowledge
and postknowledge; as applied to randomness, a maximally
random source is such that this difference (entropy) is as
large as possible.
For a uniform random source, every possible output string of
a given length has the same a priori probability, so the
information gained by observing a string is the same no matter
what specific bit pattern it contains. There is no way to
establish a meaningful distinction between "random" and
"nonrandom" strings. What *can* be done is to perform a
*set* of observations, so that statistical methods can be
applied to test the relative likelihoods of competing
hypotheses (conclusions), the sharpest distinction in this
application being between "comes from a uniform random
source" and "does not come from a uniform random source".
The latter hypothesis is believed by many, as has been
expressed before in this newsgroup, to not be testable;
however, to draw rational conclusions about the relative
likelihoods of the two hypotheses, it is not necessary to
test them in isolation. (Indeed, it is necessary *not* to.)
Techniques for using observed data to test the relative
likelihood of a hypothesis and its converse were developed
by Solomon Kullback and co-workers, and are nicely described
in a Dover reprint, "Information Theory and Statistics",
ISBN 0486696847, in stock at Amazon.com. That's the basis
for my I-hat software that was recently discussed briefly
here.
There is another interpretation of "randomness", largely
associated with the work of Gregory Chaitin, that can be
applied to isolated sample strings, namely: maximal length of
the shortest program (suitably defined) that could generate
the string. This approach has some applications, but it
is not identical to the usual notion, which is purely
probabilistic.
------------------------------
From: "Nils Johansson" <[EMAIL PROTECTED]>
Subject: best algo
Date: Mon, 14 May 2001 20:37:47 +0200
Reply-To: "Nils Johansson" <[EMAIL PROTECTED]>
If I were to implement an encryption into the TCPIP (computer networking)
stack, what algorithm would be suited. RSA would maybe be too slow for
generating numbers. I need to all the time use new keys to make the
connections safe. Are there any algorithms that are particulary suited for
this. deffie hellman maybe.
sincerely, Tore
------------------------------
Subject: Re: Is Differential Cryptanalysis practical?
From: Paul Crowley <[EMAIL PROTECTED]>
Date: Mon, 14 May 2001 18:36:38 GMT
[EMAIL PROTECTED] (Mark Wooding) writes:
> The really sad thing about FEAL is the number of times everyone went
> around the break/tweak cycle before giving up. I'm amazed it wasn't
> fairly quickly obvious that the round function was terrible.
As I understand it, this particular break/tweak cycle was a gift to
cryptanalysis.
Poncho proposed a tweak to Mercy that would prevent the attack on it
he presented to FSE 2001. I'm seriously thinking of trying to get the
tweaked cipher presented somewhere, not because I feel 100% confident
that the tweaked cipher is strong, but because I'm keen to advance the
art of large block cipher cryptanalysis...
--
__ Paul Crowley
\/ o\ [EMAIL PROTECTED]
/\__/ http://www.cluefactory.org.uk/paul/
"Conservation of angular momentum makes the world go around" - John Clark
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Not a realistic thing to do......Why?
Date: Mon, 14 May 2001 19:04:27 GMT
"Keill Randor" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
> >Real ciphers are designed long the lines of fixed keys and fixed cipher
> >design per message. (well typically the cipher design won't change at
all).
> >The security is suppose to lie in the key nothing more.
> >
> >And real cryptographers never compare their ciphers to an OTP since it's
not
> >a realistic thing todo. Sure there is no break against Rijndael faster
than
> >searching the key, that doesn't make it an OTP though....etc.
> >
> >Tom
> >
>
> It looks like the system I have is a lot more powerful than I first
thought, then.....
>
> I AM comparing the system I have to an OTP, and it IS realistic to do so.
If you seriously believe that you need a new line of work.
> If you want security, then ANY system that is crackable, as far as I am
concerned, is not good enough. (Granted, I am not a good enough
mathematician to make much of a dent in PKI, though if I got together with a
decent mathematician and a programmer, we might be able to work something
out). As for symmetrical systems, though, as far as I am concerned if it's
crackable its not very good....
Again if you believe this you will never be a serious cryptographer.
> I need to get the system I have made into a program, and see just how fast
it really is, at it's most basic. (It pretty nmuch is an OTP) - (It'll
still be far more secure than Rijndael).
"pretty much an OTP" is a meaningless bloody term. For <insert some
figureheads name> sake why must sci.crypt go thru this every week.
Either it is an OTP or it's NOTHING LIKE AN OTP. There is no "quasi-otp".
> Hmmm, any one know any decent mathematicians and programmers in England,
who might be interested????
I think Simon Johnson is out that way.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: how to blind a linear transform
Date: Mon, 14 May 2001 19:07:23 GMT
"Mike Rosing" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Tom St Denis wrote:
> >
> > At my work I have the job of analyzing a blinded linear transform. The
idea
> > (don't laugh!) is to perform a linear transform in software such that an
> > attacker can examine the software but not see the transform.
> >
> > Our trick is to make an addbox such that it works like this (the linear
> > transforms are in F_2 and are square and full rank)
> >
> > The input is <a,b>
> >
> > 1. Perform a "unblinding" substitution getting a' = S1[a], b' = S2[b],
> > previously a and b were "blinded" via S1^-1 and S2^-1
> > 2. Do the linear transform on a' and b' (i.e matrix multiply)
> > 3. Add the result in GF(2) i.e c = M1a' + M2b'
> > 4. Blind c, i.e c' = S3[c]
> >
> > The output is c'.
> >
> > My original analysis considered the inputs a,b to be normal (no
blinding).
> > My attack then works on finding where c is zero and trying to figure out
> > which pairs of M1/M2 were the original matrix. I then simplified the
attack
> > to say solve for rows of M1/M2 at a time and worry about their order
> > later... etc.. pretty demolished.
> >
> > My question is how to attack this when the blinding is performed. I
can't
> > for the love of myself figure out how, but I have a hunch it's not at
all
> > that hard. Plus it would be fun to set this company back some since
their
> > notion of "whitebox" crypto is kinda silly.
>
> Do the same thing, but now you've got an extra step. If c = 0, then c' =
constant.
> Are the blindings part of the key? If not, then a' and b' are constants
related
> to a and b for purposes of plain-text/cipher-text attack. If they are key
related,
> then you're attacking the key scheduler in effect.
>
> that's the whole point of the blinding - to make the attack more difficult
:-)
We'll discount the fact that what they want to use this for the input cannot
be blinded...
You cannot use the zero-factor since you will not know what it is. Since
they are 4x4 bijections you will see 16 copies of 0..15 somewhere...
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: best algo
Date: Mon, 14 May 2001 19:09:13 GMT
"Nils Johansson" <[EMAIL PROTECTED]> wrote in message
news:9dp8hb$ja2hd$[EMAIL PROTECTED]...
>
> If I were to implement an encryption into the TCPIP (computer networking)
> stack, what algorithm would be suited. RSA would maybe be too slow for
> generating numbers. I need to all the time use new keys to make the
> connections safe. Are there any algorithms that are particulary suited for
> this. deffie hellman maybe.
Hybrid systems. Try this
1. Once a day you share a random key (say 256-bits) with your friend.
2. you count the message with a binary counter I
3. For each message you encode I as K[I] = encrypt(I) and use K[i] as a key
for a symmetric cipher
This would be very fast but would hinge on having a secure initial transfer
and the master key not being detected or solved for. In practice this could
be secure.
Tom
------------------------------
** 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
******************************
