Cryptography-Digest Digest #446, Volume #13 Tue, 9 Jan 01 16:13:01 EST
Contents:
Re: Comparison of ECDLP vs. DLP (David Wagner)
Crypto book with mathematical explanations? ("Ingmar Grahn")
Re: Q: Recommended reading about digital watermarking (math-oriented) (Mike Rosing)
Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post) ("Paul Pires")
Re: Linear analysis ("Simon Johnson")
Re: What's better CAST in PGP or Blowfish 128bit? (Darryl Wagoner - WA1GON)
Re: Differential Analysis (Benjamin Goldberg)
Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post) (Benjamin Goldberg)
Linear analysis post 2 (Benjamin Goldberg)
Re: Comparison of ECDLP vs. DLP ("Jakob Jonsson")
Re: What's better CAST in PGP or Blowfish 128bit? (Bill Unruh)
Re: Password security for file transfer w/o speed loss? (Chris Kantarjiev)
Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post) ("Paul Pires")
Re: Comparison of ECDLP vs. DLP (Roger Schlafly)
Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post) ("Matt Timmermans")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Comparison of ECDLP vs. DLP
Date: 9 Jan 2001 18:13:36 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Nicol So wrote:
>If, by "assumptions", you're referring to the common intractability
>assumptions and the likes, the above statement is not true--there's no
>reason why a security proof must always involve unproven assumptions.
>The perfect secrecy of one-time pad against passive adversaries, for
>example, can be demonstrated mathematically without resorting to any
>unproven assumptions.
On the other hand, there are still "assumptions" in the form of
the model of computation used to analyze the one-time pad.
(e.g., that psychics/telepaths don't exist)
------------------------------
From: "Ingmar Grahn" <[EMAIL PROTECTED]>
Subject: Crypto book with mathematical explanations?
Date: Tue, 9 Jan 2001 19:13:47 +0100
Hi!
I'm looking for a book like "Applied Cryptography" by Bruce Schneier -
however I want one that goes into a bit more detail in explaining the
mathematical background, and possibly also one that covers the most modern
algorithms too (since Schneier's book is a couple of years old). Any ideas
of what might be a suitable book for me?
/Ingmar
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Q: Recommended reading about digital watermarking (math-oriented)
Date: Tue, 09 Jan 2001 12:25:23 -0600
Jyrki Lahtonen wrote:
>
> Hi y'all,
>
> I would like to know a little bit about digital watermarking techniques
> and am looking for books/survey articles on the topic. Most of the stuff
> you find with Alta Vista seem to simply advertise their particular point
> and are rather lacking in their description of the mathematical concepts
> being used (guess they dare not describe their algorithm in detail due
> to
> some legal issue).
>
> So more specifically I am looking for texts written to mathematicians
> with
> experience in related fields (crypto, coding theory, you name it). Say,
> if you write a few bits into an image/audio data/whatever, will you seek
> to
> spread the bits by using a bent function sequence, or some other
> pseudorandom
> sequence or what???? Is spreading used at all??
Here's a reference to a way to break water marks:
http://www.cl.cam.ac.uk/~mgk25/stirmark.html
I'm sure the author will be able to point to more definitive information.
Patience, persistence, truth,
Dr. mike
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post)
Date: Tue, 9 Jan 2001 10:43:51 -0800
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Paul Pires wrote:
<snip>
Once again, I thank you. The information you gave is very
helpfull. I keep forgetting to check Terry's site. You'd
think I'd learn by now.
> > What is the state of the art for the good stuff?
>
> 1 clock per byte.
Gulp! That is a humbling number. Any chance that
I am assuming something weird? This is for code,
with no special hardware support,
running under a common OS (like Windoze),
on a common 32bit platform?
Gosh, That just boggles my mind.
Paul
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Re: Linear analysis
Date: Tue, 9 Jan 2001 19:15:35 -0800
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Simon Johnson wrote:
> >
> > In article <[EMAIL PROTECTED]>,
> > Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> > > I've read a bit about linear analysis, and I want to attempt it on
> > > my hypercrypt cipher, which is available at:
> > > http://users.powernet.co.uk/eton/guest/beng/hypercrypt.txt
> > >
> > > However, I'm having trouble seeing how to do so. I want to try and
> > > find a break on reduced round (OROUNDS=1) version of hypercrypt,
> > > using either the currently listed sbox (which is taken from TC5), or
> > > with the AES sbox.
> > >
> > > Both of the sboxen I'm considering are fairly nonlinear. I fail to
> > > see how to even begin doing the linear attack on even the mixing
> > > component (a 4 round 16 bit fiestel), let alone on the entire
> > > cipher.
> > >
> > > The fiestel is 4 rounds since that is the minimum number needed to
> > > be secure against differential analysis.
> >
> > How did i know this was comming ;)
> >
> > I don't have the foggest how to attempt linear cryptanalysis, where
> > did u find out how to do it?
>
> Michael Scott sent me a Microsoft Word document containing a description
> of differential and linear analysis on FEAL-4. The file, difflin.doc,
> is 138KB. Actually, it was an assignment to implement both FEAL-4 and
> the attacks on it, but it contained enough information about the attacks
> to figure this stuff out.
>
> If you want, I can send it to you.
Yes, this would be cool send it to [EMAIL PROTECTED],
DEJA appears to be dead so, i'm using a different news server.
Simon.
> --
> Power interrupts. Uninterruptable power interrupts absolutely.
> [Stolen from Vincent Seifert's web page]
------------------------------
From: [EMAIL PROTECTED] (Darryl Wagoner - WA1GON)
Subject: Re: What's better CAST in PGP or Blowfish 128bit?
Date: Tue, 09 Jan 2001 19:18:21 -0000
[EMAIL PROTECTED] (Tom ST Denis) wrote in
<JTC26.31478$[EMAIL PROTECTED]>:
>
>"Darryl Wagoner - WA1GON" <[EMAIL PROTECTED]> wrote in message
>news:[EMAIL PROTECTED]...
>> [EMAIL PROTECTED] (Tom St Denis) wrote in
><90tp0u$nko$[EMAIL PROTECTED]>:
>>
>> >I would trust a "secure application" written by a real cryptographer.
>> >Just because "heart transplants" exist doesn't mean a IT specialist
>> >can perform them right?
>>
>> So mean if a good software engineer that isn't a cryptographer
>> can't be trusted to create a secure application? This is type
>> of attitudes that creates the mystique that this is a black
>> art.
>
>Often security holes are things people just don't think about. You need
>the right mindset to be a good security application developer. If you
>are careless (i.e work for microsoft) lots of problems will be
>exploited.
Of course security holes are created by people who don't think.
There is all levels of programmers out there. If a tool kit
is well designed with good documention which points out areas
that must be watched for a good eng can write as good or better
secure app than a cryptographer. This is because the cryptographer
may understand the crypto functions but may be clueless about
the OS workings that may have a security weakness in it. Security
is more than crypto.
-darryl
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Differential Analysis
Date: Tue, 09 Jan 2001 19:29:43 GMT
Tom St Denis wrote:
>
> In article <[EMAIL PROTECTED]>,
> Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
[snip]
> > In the AES sbox, there are 23 diferentials which have a probability
> > of 6/256. There are a large number of differentials with
> > probability of 4/256, 2/256, and 0.
>
> Wrong. The highest xor-pair probability is 4/256 not 6/256.
Each of these XOR pair differences occur with probability 6/256.
08->53 09->62 15->3a 26->94 28->5f 2e->52 34->73 3f->16 46->31 4d->80
57->30 5b->5a 68->26 71->c8 7a->b9 80->a6 85->f4 86->27 89->c4 ce->e8
db->d2 de->7e fe->d8
Unless, that is, I've somehow computed the AES sbox wrong. The first
few bytes of what I have are:
63 7c 7f 7b fa 6b 6f cd 30 01 67 2b fe df a3 7e ca 82 c9 7d f2 59 47 f0
Are these wrong?
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post)
Date: Tue, 09 Jan 2001 19:41:12 GMT
Paul Pires wrote:
>
> Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> > Paul Pires wrote:
[snip]
> > > What is the state of the art for the good stuff?
> >
> > 1 clock per byte.
>
> Gulp! That is a humbling number. Any chance that
> I am assuming something weird? This is for code,
> with no special hardware support,
> running under a common OS (like Windoze),
> on a common 32bit platform?
>
> Gosh, That just boggles my mind.
It is perfectly possible to create a stream cipher which works with 32
bit words, not 8 bit bytes. If it takes 4 clocks to generate 32 bits of
keystream, that's 1 clock per byte. Consider the 64-bit word version of
the ISAAC keystream generator -- it takes about 8 instructions per word,
and produces 64 bits at a time.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Linear analysis post 2
Date: Tue, 09 Jan 2001 19:41:55 GMT
Does anyone know of any program which automatically does analysis of an
sbox to find linear relationships?
Also, does anyone have any suggestions for a program to assist me in
doing linear analysis of a cipher (not just of the sbox) -- perhaps a
symbolic math package, (like maple or matlab or mathematica) might help?
I don't have one, and unless I think it'll help, I'm not going to get
one (I'm a bit short on disk space).
Lastly, has anyone already *done* linear analysis of the Rijndael/AES
sbox? It's supposedly well analysed, so I would think that this has
been done. It seems silly to me to do something that's already been
done. And no, I haven't [yet] read the Rijndael paper to see what
analysis they might have done, but they use their sbox as a bytesub, not
a fiestel -- it might not apply.
--
Power interrupts. Uninterruptable power interrupts absolutely.
[Stolen from Vincent Seifert's web page]
------------------------------
From: "Jakob Jonsson" <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Tue, 9 Jan 2001 20:41:19 +0100
"Roger Schlafly" <[EMAIL PROTECTED]> wrote
> Jakob Jonsson wrote:
> > Proofs in the random oracle model ARE proofs of security, but you may
have
> > objections against the strength of the proof.
>
> Stop right there. You contradict yourself. Proofs are proofs.
> There are no objections to the strength of a valid proof.
Actually, I meant that one may have objections against the strength of the
theorems -- if the assumptions are too strong, then the resulting theorems
become "weak", since they may not be applicable in many situations. For
example, in our case the theorem fails as soon as a bias in the hash
function is found, because then the adversary can distinguish it from a
truly random function.
Yet, I don't see why the proofs themselves should not be valid proofs. It is
hard to argue against, e.g., the conclusions in Bellare-Rogaway's RSA-PSS
paper. They derive "theorems" from "assumptions" via sound mathematical
arguments, not via heuristic arguments or hand-waving. Or do you see a basic
flaw in the logical chain leading from the assumptions to the theorems?
Jakob
------------------------------
From: [EMAIL PROTECTED] (Bill Unruh)
Subject: Re: What's better CAST in PGP or Blowfish 128bit?
Date: 9 Jan 2001 19:57:53 GMT
In <[EMAIL PROTECTED]> [EMAIL PROTECTED] (Darryl
Wagoner - WA1GON) writes:
]>> >I would trust a "secure application" written by a real cryptographer.
]>> >Just because "heart transplants" exist doesn't mean a IT specialist
]>> >can perform them right?
]>>
]>> So mean if a good software engineer that isn't a cryptographer
]>> can't be trusted to create a secure application? This is type
No. He just does not have the tools and attitude to do so easily.
Thinking secure is a special attitude which takes time to aquire.
That is all. It is not impossible for a good software engineer to do, it
is just more difficult than it seems.
]>> of attitudes that creates the mystique that this is a black
]>> art.
Is being a gas fitter a black art? No. It is a set of skills you have to
learn. Almost anyone can learn them. Most don't.
------------------------------
From: Chris Kantarjiev <[EMAIL PROTECTED]>
Subject: Re: Password security for file transfer w/o speed loss?
Date: Tue, 09 Jan 2001 12:23:22 -0800
You might take a look at SRP: http://srp.stanford.edu/srp/ which is
designed for authentication only. There are some questions about the
license, but the Stanford licensing office is trying to work them out.
------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post)
Date: Tue, 9 Jan 2001 12:24:59 -0800
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Paul Pires wrote:
> >
> > Douglas A. Gwyn <[EMAIL PROTECTED]> wrote in message
> > news:[EMAIL PROTECTED]...
> > > Paul Pires wrote:
> [snip]
> > > > What is the state of the art for the good stuff?
> > >
> > > 1 clock per byte.
> >
> > Gulp! That is a humbling number. Any chance that
> > I am assuming something weird? This is for code,
> > with no special hardware support,
> > running under a common OS (like Windoze),
> > on a common 32bit platform?
> >
> > Gosh, That just boggles my mind.
>
> It is perfectly possible to create a stream cipher which works with 32
> bit words, not 8 bit bytes. If it takes 4 clocks to generate 32 bits of
> keystream, that's 1 clock per byte. Consider the 64-bit word version of
> the ISAAC keystream generator -- it takes about 8 instructions per word,
> and produces 64 bits at a time.
Okay, I'll consider it but we were talking about "Genuine stream ciphers"
Not siple XOR of plaintext with a keystream generator. The
"cryptographically secure" PRNG is a component of the cipher. 8 instructions for
64 bits is 1 clock per byte if you assume 1 instruction per clock. I guess
I'll have to look at it real close and find out how you transparently do
instructions
on 64 bit units on a 32 bit machine. Now, you process the keystream against
plaintext to make ciphertext, somehow disassociate the
ciphertext from the state and the plaintext and chain this back in. Sounds like
6 - 8 clocks per byte to me. That doesn't boggle my mind. I think I could
even do it in C++, running under Windows and not even in assembly.
I'm still mind-boggled by the above quote in the context of the
previous discussion. There is a minimum number of operations
to do anything. The ideal is not zero clocks per byte. If halving
the distance between "were you are" and "the theoretical ideal"
is 100% imrovement, then there are a lot of those "Massive"
improvements between 8 clocks and 1clock. Not to mention
that there isn't a lot of realistic hope for future performance
improvement.
There! I've blurted out my ignorance. Hopefully, someone will
show me where my assumptions, knowledge or sanity is fubar.
Hopefully, I will survive it.
Paul
>
> --
> Power interrupts. Uninterruptable power interrupts absolutely.
> [Stolen from Vincent Seifert's web page]
====== Posted via Newsfeeds.Com, Uncensored Usenet News ======
http://www.newsfeeds.com - The #1 Newsgroup Service in the World!
======= Over 80,000 Newsgroups = 16 Different Servers! ======
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: Comparison of ECDLP vs. DLP
Date: Tue, 09 Jan 2001 12:37:11 -0800
Jakob Jonsson wrote:
> > > Proofs in the random oracle model ARE proofs of security, but you may
> > > have objections against the strength of the proof.
> > Stop right there. You contradict yourself. Proofs are proofs.
> > There are no objections to the strength of a valid proof.
> Actually, I meant that one may have objections against the strength of the
> theorems -- if the assumptions are too strong, then the resulting theorems
> become "weak", since they may not be applicable in many situations. For
> example, in our case the theorem fails as soon as a bias in the hash
> function is found, because then the adversary can distinguish it from a
> truly random function.
More precisely, it fails as soon as any particular value of a hash
function is found, because it is then no longer a random oracle.
> Yet, I don't see why the proofs themselves should not be valid proofs. It is
> hard to argue against, e.g., the conclusions in Bellare-Rogaway's RSA-PSS
> paper. They derive "theorems" from "assumptions" via sound mathematical
> arguments, not via heuristic arguments or hand-waving. Or do you see a basic
> flaw in the logical chain leading from the assumptions to the theorems?
I see you have to put "theorems" in quotes. They prove something,
but they do not prove that RSA-PSS is secure. The security argument
is a hand-waive.
------------------------------
From: "Matt Timmermans" <[EMAIL PROTECTED]>
Subject: Re: xor'd text file - Cryptanalyis of Simple Aperiodic Substitution Systems
(Warning: LONG post)
Date: Tue, 9 Jan 2001 13:48:18 -0500
Reply-To: "Matt Timmermans" <[EMAIL PROTECTED]>
Benjamin Goldberg <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> [...]
> For a cipher, stream or otherwise, to authenticate, you need one of two
> things: it either must output garbage if an opponent changes some bits
> of the ciphertext, or it must have appended to it some sort of secure
> error checking code.
>
> For a stream cipher, the second can be done by appending a CRC or secure
> hash. [...]
Not a CRC. Since CRCs are linear, your encrypted message is still
susceptible to bit flipping -- flip a bit, then flip the CRC bits that
depend on it. The CRC will still match after decryption -- now that would
be an amusing attack:
"That's not the transaction I sent -- I said 5 dollars, not 262149!"
"Sorry, but it has to be the transaction you sent -- it was encrypted with
your key and the CRC matches."
------------------------------
** 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
******************************
