Cryptography-Digest Digest #475, Volume #9 Wed, 28 Apr 99 02:13:03 EDT
Contents:
Re: Quantum Computing and Cryptography added to web site...
([EMAIL PROTECTED])
Re: Quantum Computing and Cryptography added to web site... (David A Molnar)
Re: Quantum Computing and Cryptography added to web site... (David A Molnar)
Re: Quantum Computing and Cryptography added to web site... (David A Molnar)
Re: Easy identity-proof (NOT Fiat-Shamir) (Helger Lipmaa)
Re: break this code ("Dan")
Re: Algorithms where encryption=decryption? ([EMAIL PROTECTED])
Re: xtea paper (was PGP=NSA) (Steve Rush)
Re: Papers on RC4 key size (Paul Rubin)
Re: xtea paper (was PGP=NSA) (Paul Rubin)
Re: True Randomness & The Law Of Large Numbers ("Douglas A. Gwyn")
Re: True Randomness & The Law Of Large Numbers ("Douglas A. Gwyn")
Re: break this code ("Douglas A. Gwyn")
Re: Double Encryption is Patented! (from talk.politics.crypto) (Jerry Coffin)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Jerry Coffin)
Re: FSE-6 Report: Slide Attack (Jerry Coffin)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Quantum Computing and Cryptography added to web site...
Date: 28 Apr 1999 00:33:56 GMT
Reply-To: [EMAIL PROTECTED]
I decided to write this up in a slightly clearer way. If you find it
useful, feel free to use/plagarize any of it. To do this right I should
reference the quantum search algorithm...
Quantum Computation and Brute-Force Attack
Lets say we are given a problem where we know that a given 128-bit block
of plaintext is encrypted to a given 128-bit block of ciphertext using
a known algorithm and we would like to recover the key.
On a classical computer, with a good algorithm, you have to resort to
brute-forcing the key. This means that you feed a trial key and the
plaintext into the cipher, turn the crank and compare the output ciphertext
to the ciphertext that you want and repeat if they don't match. When they
do match then you ring the bell and you've found the key. The search
time is O(N) where N is the number of different keys (and N=2^b where b is
the number of bits in the cipher).
On a quantum computer you would do exactly the same thing, only instead of
picking a particular key you would feed 128 q-bits into the algorithm and
you would output a state containing all possible ciphertexts. The trick
comes in picking the ciphertext out of these which matches the ciphertext
which you are looking for. If you could reach into the quantum state and
pick this ciphertext out, then you would be done. A common misconception
about quantum computers is that it is possible to do this and that brute
forcing an algorithm would be trivial.
This is actually not the case. Without doing anything special we can only
measure the output state of the quantum computer and we get only a single
one of the states picked entirely at random. This would be equivalent to
a classical computer picking random trial keys and we would do no better
than the O(N) classical case.
However, on a quantum computer it is actually possible to increase the
chances of picking the correct key. It is not possible to increase the
probability sufficiently so that one can reach in a pull the key out in
one trial. However, it is possible to reduce the search time from O(N) to
O(sqrt(N)). And it can, in fact, be proven that given a cipher that
lets you know nothing about what the probable keys are (a flat distribution)
that this is the best speedup which you can get.
The result of this is that on a quantum computer the security of a
block symmetric cipher against these kinds of brute-force attacks is reduced
to half the number of bits. So that a 128-bit cipher being brute-forced by
a quantum computer only has the security of a 64-bit cipher being brute-forced
by a classical computer (assuming that the "clock speeds" of the quantum
and classical computers are the same, which is admittedly unlikely).
(okay, end of the simpler explanation)
You can also probably tackle the problem of being given a ciphertext and
recovering the key and the plaintext out of it. In this case you run the
ciphertext (as bits) and the key material (as q-bits) through the decryption
algorithm and then feed the output plaintext through an algorithm that
measures the entropy of the plaintext and returns a 0 if its random garbage
and a 1 if its a candidate. The analysis might be more complicated since
you might have to account for the fact that more than one key might give
you a '1' result.
In general you can get this quantum speedup for any algorithm where you
take n-bits which are equally likely and you run them through some black
box and the result is a single bit which is a 0 for all the wrong results
and a 1 for the right result.
Anyway, hopefully someone out there will find this explanation useful...
I actually almost understand this quantum algorithm. I don't quite
understand the part where the probability of finding the correct answer is
increased and it seems a bit like magic, but i can accept it. I can now go
"ahh, yes, quantum parallellism, i know what you mean.." and nod my head like
i know what the fuck i'm talking about. On the other hand i still haven't
tackled the complexities of Shor's factorization algorithm...
--
Lamont Granquist ([EMAIL PROTECTED])
ICBM: 47 39'23"N 122 18'19"W
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Quantum Computing and Cryptography added to web site...
Date: 28 Apr 1999 00:12:58 GMT
[EMAIL PROTECTED] wrote:
> You could also include a blurb on brute-force searching, quantum computers
> and the quantum search algorithm (it is named after someone, but i forget
> it).
Lov K. Grover. There's a press release type page at
http://www.bell-labs.com/user/feature/archives/lkgrover/
and a paper on the algorithm at
http://www.imada.ou.dk/Research/Preprints/Abstracts/1996/11.html
-David
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Quantum Computing and Cryptography added to web site...
Date: 28 Apr 1999 00:22:25 GMT
[EMAIL PROTECTED] wrote:
> Dunno, I think that's some "useful info" -- good to show to people who claim
> that quantum computation means the death of cryptography, and people who
> don't understand the way that quantum paralellism works.
(sorry, I forgot this last time)
You may also note that Shor's algorithm does not work for all, or even most
problems in NP. Unfortunately, the ones it happens to work for are exactly
the problems which have been most popular in public-key cryptography. Still,
it is not known that a quantum computer can solve every problem in NP in
polynomial time. i.e. BQP (bounded prob of error, quantum computer, polytime) ?= NP.
So if a quantum computer is built and can handle arbitrary length numbers, with
today's state of the art, it seems that
* confidential-key distribution crypto ("secret key" crypto) is still possible, but
survives, but with longer keylengths because of Grover's algorithm. Maybe that kills
smartcards?
* RSA, ElGamal, and all the Integer Factoring and Discrete Log public key algorithms
die.
(do elliptic curves follow?)
* It may be possible to find some problem in NP which admits of trapdoors but is not
efficient on a quantum computer. Maybe lattice cryptosystems take off.
-David
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Quantum Computing and Cryptography added to web site...
Date: 28 Apr 1999 00:29:23 GMT
[EMAIL PROTECTED] wrote:
> "ahh, yes, quantum parallellism, i know what you mean.." and nod my head like
> i know what the fuck i'm talking about. On the other hand i still haven't
> tackled the complexities of Shor's factorization algorithm...
Has something to do with the fact that you can find the period of a function
by applying a fourier transform to it. Then he has a way to do a quantum fourier
transform. It turns out that the order of the subgroup to which a particular
element belongs in Z/nZ happens to give you one of the factors of n (which, if you
handwave about order as "the number of elements in the group", makes sense).
Finding the period of g^x mod n as values of x vary gives you the order.
now the tough part is figuring out just how the QFT and modular multiplication work,
and
I'm not much help there just yet.
------------------------------
From: [EMAIL PROTECTED] (Helger Lipmaa)
Subject: Re: Easy identity-proof (NOT Fiat-Shamir)
Date: 27 Apr 1999 22:28:50 GMT
[EMAIL PROTECTED] wrote:
: Christian Geuer-Pollmann:
: > I need a system used for authentication. Systems like Fiat-Shamir have a
: > balance in the computation power: The proof is a little bit hard, the
: > verification is easier. For my project, I need a system with an easy
: > proof and a harder verification. The proof must be done on a very lousy
: > hardware (less computing power than a smartcard and much faster like 1/2
: > second).
: >
: > Do there exist such systems / protocols?
: Well, sort of.
: First, if you can assume prover and verifier share a secret,
: then you can use fast symmetric crypographic primatives.
Schnorr's identification scheme?
Alice's public key is $(p,q,g,h)$, where $p$ is a (say) $>600$ bit prime,
$q|p-1$ is a $\approx 160$ bit prime, $g\neq 1$ and $h$ are two elements
$\mod p$. Alice's private key is $w$ ($mod q$), such that $g^w=h$.
Protocol itself:
Alice Bob
r:=rand(2^q)
a:=g^r a
------------->
c c:=rand(2^80)
<-------------
z:=cw+r z
------------->
Bob accepts if g^z=a*h^c
Alice has only perform one on-line 160*80 multiplication (and addition)! On
the other hand, her off-line computations include a random number generation
and a modular exponent.
Schnorr's scheme is probably the most efficient public key identification
scheme at all, although some of its security is still heuristic. Okamoto's
modification of this scheme is ``provable secure'' (see his paper at Crypto
92), but requires _two_ multiplications instead of one.
Helger
PS Schnorr's original paper is available on the web.
Cf http://home.cyber.ee/helger/crypto/link/protocols/ident.html
------------------------------
From: "Dan" <[EMAIL PROTECTED]>
Subject: Re: break this code
Date: Tue, 27 Apr 1999 20:53:48 -0400
=====BEGIN PGP SIGNED MESSAGE=====
Hash: SHA1
Thanks for the replies.
Unfortunately, although my initial question was answered I now have
many more.
I am hesitant to ask too many (amature) questions as most of the
postings are about some pretty heavyweight stuff. So I just sit back
and try to understand as best I can.
Believe it or not, one of my favorite things is to take an encrypted
(cypher) and try to decrypt it. Most of the time it is from a program
that I use or have came across on the net. While the data may or may
not be of interest to me, the method of encryption is.
For example I recently took a database that was encrypted and
converted each of the encrypted characters into a number (In VB5 using
the asc() function) then I compared the numbers in various ways,
looking for obvious patterns, adding & subtracting, even multiplying
the character equilivant codes and much to my surprise a particular
number kept coming up so I took this number (key) and using a little
trial and error was able to decrypt the text to its original state. I
have done this on several occasions using different methods and even a
little luck. Correct me if I am wrong, but I believe you call this
differential comparison.
Most recently I have ran across a cypher that has me baffeled as it is
encrypted in 8 character (byte ?) blocks, and if a character within a
particular block of the cypher is changed that block is "garbled" in
the output. There is more but I will save it for later.
If there are no objections I would like to ask questions as they come
to mind. Hopefully I will have learned the correct terminology so I
can better phrase my questions so that they make sense. Just remember
that I am an amature and I may ask what to many might be "dumb"
questions, though I am very skilled in many things, unfortunately
cryptography is not one of them (hopefully that will change).
Thanks,
Dan [EMAIL PROTECTED]
P.S. If one or many of you would like to coach an amature like me
through what looks to be a rough road ahead, please feel free to
e-mail me any time. I will appreciate it VERY much.
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 6.0 for non-commercial use <http://www.pgp.com>
iQA/AwUBNyZcGXczPNMGhkSQEQKO+ACg2U6D3ruo0G4/RRZIPfbfZ8bt5f4An36T
ld7qSAACjK9scuYFlponwqxZ
=iMXY
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Algorithms where encryption=decryption?
Date: Wed, 28 Apr 1999 00:54:57 GMT
In article <[EMAIL PROTECTED]>,
Anne Veling <[EMAIL PROTECTED]> wrote:
> Hi everyone,
>
> I am looking for any algorithms that can be used in encryption in which
> the encryption algorithm is the same as the decryption algorithm.
>
> For instance:
>
> the well-known ROT-13 (a unary encryption algorithm (uses only one
> parameter))
>
> Or f(x)=-x
> Or f(x)=1/x (not so useful for encryption)
>
> Or binary:
>
> f(x,y)=x XOR y
>
> Do you know of any other?
>
> Thanks, bye,
>
> Anne.
> --
>
> Anne Veling
> [EMAIL PROTECTED]
> http://www.medialab.nl/crew/anne/
>
> A man with a watch knows what time it is. A man with two watches is
> never sure.
>
You might want to consider the fact that ANY block chpher is reversible
when used in the CFB block chaining mode.
--
Robert G. Durnal
Web pages at www.afn.org/~afn21533
and members.tripod.com/~afn21533
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Steve Rush)
Subject: Re: xtea paper (was PGP=NSA)
Date: 28 Apr 1999 01:37:56 GMT
>[EMAIL PROTECTED] (Paul Rubin) wrote:
>...
>First of all, pdf sucks for reading with a web browser.
>It's for exercising total control over formatting a document,
>usually for printing it. Unless you have a good reason to need
>that kind of control, please use html.
I agree about PDF, but HTML really sucks for posting to newsgroups, which are
about plain old text (or text-encoded binaries). Using HTML in Usenet more
than doubles the length of the message.
Are you using one of those big integrated browsers that try to make the whole
world look like the World Wide Wait?
**********************************************************************
If it's spam, it's a scam. Don't do business with Net abusers.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Papers on RC4 key size
Date: Wed, 28 Apr 1999 03:35:57 GMT
<[EMAIL PROTECTED]> wrote:
>> Therefore, ALL cryptosystems with 40 bits keys are useless.
>
>Not really, what if a key is generated at random, and the secret is valid for
>say the next 5 minutes. Can you search 2^40 keys in 5 minutes?
1) With enough hardware, yes, certainly. Something on the scale of
Deep Crack could do it in seconds.
2) But even if you can't, it often won't matter. If the info that
you're encryting now will still be valuable next week, it doesn't matter
if you change the key in 5 minutes. The attacker can spend the rest
of the week crunching the current key.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: xtea paper (was PGP=NSA)
Date: Wed, 28 Apr 1999 03:37:10 GMT
In article <[EMAIL PROTECTED]>,
Steve Rush <[EMAIL PROTECTED]> wrote:
>>First of all, pdf sucks for reading with a web browser.
>>It's for exercising total control over formatting a document,
>>usually for printing it. Unless you have a good reason to need
>>that kind of control, please use html.
>
>I agree about PDF, but HTML really sucks for posting to newsgroups, which are
>about plain old text (or text-encoded binaries). Using HTML in Usenet more
>than doubles the length of the message.
I'm saying use HTML instead of PDF to format the paper on a web page,
not a newsgroup post. HTML doesn't belong in news posts. Neither does PDF.
>Are you using one of those big integrated browsers that try to make the whole
>world look like the World Wide Wait?
Absolutely not. See above.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Wed, 28 Apr 1999 04:06:19 GMT
Medical Electronics Lab wrote:
> Douglas A. Gwyn wrote:
> > *******************************************************************
> > * Okay, here is a nice cryptomathematical problem for everyone: *
> > * Given that you have to make a decision whether or not a *
> > * sequential flat-random bit stream generator is malfunctioning *
> > * within 20,000 bits of the point at which it first malfunctions, *
> > * what tests would you perform? The generator must be treated *
> > * as a "black box"; no knowledge of its inner workings is *
> > * available; consequently, the tests must be performed on its *
> > * output stream. The upper limit for the likelihood of *
> > * malfunction being reported when it isn't present shall be *
> > * 10^-6. The goal is to maximize the likelihood of reporting a *
> > * malfunction when one in fact is present. *
> > *******************************************************************
> Autocorrelation and frequency distribution as well as uniformity.
That general idea works, with suitable refinement and quantification
of the thresholds.
> 20,000 bits ain't a whole lot to work with to get 10^-6. I'd
> prefer 10^6 bits :-)
Feel free to adjust the trade-off between Type I and Type II error.
I think the above specification is approximately what was used in
creating the FIPS-140 test specs.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: True Randomness & The Law Of Large Numbers
Date: Wed, 28 Apr 1999 04:11:49 GMT
"R. Knauer" wrote:
> An error is generated if any of the FIPS-140 tests is failed. So
> exactly what failure mode is being tested by the Monobit Test?
Since FIPS-140 does not specify details of the implementation
(algorithm, hardware architecture, etc.), it cannot tie tests
to specific failure modes. Instead, it specifies generic tests
that *any* sufficiently random generator should pass 999,999
times out of 1,000,000 (or thereabouts). This is known as
"black box" testing in the engineering professions. ("White box"
testing, which should more properly be called "clear box" testing,
can take into account the internal construction of the system.)
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: break this code
Date: Wed, 28 Apr 1999 04:17:48 GMT
Dan wrote:
> Why do you need the entire system, isn't that kind of like cheating?
Two reasons: (1) In practice, the structure of a cryptosystem that
is heavily used has a substantial chance of being discovered by the
opponent, so for conservative testing, you need to assume that the
opponent knows the system; (2) It takes a lot of work, sometimes,
and often a *large* amount of traffic, to determine the probable
system being used, and for a "challenge" cryptogram, why would we
invest so much effort?
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Double Encryption is Patented! (from talk.politics.crypto)
Date: Tue, 27 Apr 1999 22:15:21 -0600
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
> It is the claims that matter. In this case, they are able to show that every
> bit of ciphertext depends on every bit of plaintext. This is not true of
> normal CBC and is novel.
Yes and no -- claims 18 and 19 are (or at least might be) "means plus
function" claims, and as I understand things, a means plus function
claim is tied quite closely to the disclosure of the patent. This
means that if the disclosure suggests the variation he talked about,
it might be considered equivalent to one of those two claims, even if
they don't specifically talk about it. At the same time, if the
disclosure doesn't suggest such a thing, they probably would NOT cover
it, even if it might otherwise fall within the scope of their
description.
If it's close enough that this is a question, you probably want to get
a patent attorney involved rather than taking my word for things
though.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Tue, 27 Apr 1999 22:15:30 -0600
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> You've made some strong claims here, and demolished a trivial example.
> Can you show a real example? Are there _any_ known weaknesses in
> combining any pair of the following: Blowfish, IDEA, 3DES?
> An easier
> question would be to ask whther there are any weaknesses known in
> combining one of the previously mentioned list with any other cipher.
> Are there real facts behind your claims or are you expressing a
> subjective judgement?
Of course there are real facts. I've demonstrated how one trivial
example shows up poorly -- I'd thought that would show the fundamental
problem, but apparently it didn't, so I'll try to point out the
most fundamental problem more explicitly.
The most fundamental problem with the idea as-presented is that all
the forms of encryption use the same key. That means that if any
_one_ of the forms of encryption used is broken, the enemy can recover
the key and decrypt the message.
Just for the sake of demonstration, assume that you've got a message
that you want to ensure against being decrypted within 10 years. For
the sake of argument, let's say you use Blowfish, IDEA and triple-DES.
Again, purely for the sake of having some numbers, let's assign a 20%
chance to each of these three forms of encryption being broken within
the ten year time-frame.
In this case, encrypting with one of the three means you have a 20%
chance of your message being decrypted. Encrypting with all three
means you have a 60% chance of the message being decrypted.
IOW, by using the same key for all forms of encryption, the best you
can hope for is to get the overall strength of the single _weakest_
form of encryption used. If any _one_ form of encryption is broken,
the message can be decrypted.
To be at all useful, you need to start by using an independent key for
each form of encryption. This means breaking one has no effect on the
others.
Then you hope that applying the forms of encryption together doesn't
lead to some previously unknown/unexpected weakness. Without fairly
extensive study of a specific combination, it's impossible to make
specific comments, but I'll point out a basic concept to consider: the
forms of encryption we're talking about are all symmetric. If you
apply essentially the same form of encryption twice, the second can
end up decrypting the first. When you combine the two, you're
basically hoping for a sum of their individual strengths, but if one
ends up partially decrypting the other, you can end up with the
difference instead of the sum, with results you'd rather not know
about.
Of course, using independent keys for the different forms of
encryption CAN help a great deal in this regard as well -- as long as
the two forms of encryption don't form a co-group (so to speak) you
can end up with a stronger result even if both using the same key
would partly or completely cancel each other out. OTOH, if the two
form a co-group, using a separate key for each might not help at all.
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: FSE-6 Report: Slide Attack
Date: Tue, 27 Apr 1999 22:15:26 -0600
In article <7g319p$gg8$[EMAIL PROTECTED]>, tomstdenis@my-
dejanews.com says...
[ ... ]
> Cool, no offence, but heres an interesting question. How does this apply to
> normal file, or communication links of today? I really would like to know.
Assuming you're talking about chosen-plaintext in general, the usual
application is if a networked computer routinely encrypts data to be
transmitted over a particular link, in many cases you can arrange to
send data over that link and intercept the encrypted version. Once
you break the encryption, you can read all the other messages sent
over the link as well...
------------------------------
** 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
******************************
