Cryptography-Digest Digest #351, Volume #12 Thu, 3 Aug 00 15:13:01 EDT
Contents:
Re: New William Friedman Crypto Patent (filed in 1933) ("Paul Pires")
Re: Elliptic Curves encryption (Terry Ritter)
Re: Plausible Word Generation via Trigram Statistics (Tom Anderson)
Re: Cracking RC4-40 in FPGA hardware ("CMan")
Re: Kill my Cipher ("Joseph Ashwood")
Re: Stream Ciphers (Tom Anderson)
Re: I did do it PROTOCOL: (Tom Anderson)
Re: Elliptic Curves encryption (Doug Kuhlman)
Re: OTP using BBS generator? ("Joseph Ashwood")
Re: New William Friedman Crypto Patent (filed in 1933) (Tom Anderson)
Re: What is the word on TC5? (tomstd)
Re: Cracking RC4-40 in FPGA hardware (Paul Rubin)
Re: OTP using BBS generator? (Terry Ritter)
----------------------------------------------------------------------------
From: "Paul Pires" <[EMAIL PROTECTED]>
Subject: Re: New William Friedman Crypto Patent (filed in 1933)
Date: Thu, 3 Aug 2000 11:09:10 -0700
Mok-Kong Shen <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Bruce Schneier wrote:
>
> > William Friedman filed a patent application for an Enigma-like
> > encryption device in 1933. The Patent Office awarded the patent this
> > month:
> >
> > http://www.patents.ibm.com/details?&pn=US06097812__&s_all=1
> >
>
> This lets one speculate that patents that quickly go through the
> patent offices are probably of inferior quality (cf. Hitachi's rotation).
>
> Isn't it usually the case that some fees have to be paid upon award
> of the patents? I wonder who is going to do that.
>
> M. K. Shen
>
You might be missing something here that explains the lag, like a security
order. The patent office, time to grant and USPTO regs are not a factor in
the quality or lack thereof in patents. That is the sole responsibility of
the author. GIGO.
Paul
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Elliptic Curves encryption
Date: Thu, 03 Aug 2000 18:20:41 GMT
On 3 Aug 2000 14:21:16 GMT, in <[EMAIL PROTECTED]>,
in sci.crypt [EMAIL PROTECTED] (Mark Wooding) wrote:
>Terry Ritter <[EMAIL PROTECTED]> wrote:
>>
>> On Tue, 01 Aug 2000 13:26:12 -0500, in
>> <[EMAIL PROTECTED]>, in sci.crypt Doug Kuhlman
>> <[EMAIL PROTECTED]> wrote:
>>
>> >But knowing that "breaking" BBS (for example) is equivalent to
>> >factoring is SOMEthing.
>>
>> No, it is not, and we just went through that a month ago.
>
>Yes, we did, and you're still wrong now.
On the contrary, you seem to have difficulty understanding written
English. Or perhaps you are simply too arrogant to take the effort to
understand someone else's ideas.
>> When the supposed "BB&S" construction is used, there is a possibility
>> -- admittedly very remote -- of having selected a short cycle. When
>> that happens, the system can be broken due to repetition of the cycle,
>> and that of course also allows the composite to be factored. Now,
>> exactly *how* has it helped us to know that the failure allowed
>> factoring?
>
>Well, we know that finding cycles is at least as hard as factoring.
|--------------------------^
(That would be "finding *short* cycles." *Every* starting value finds
a cycle.)
Whether finding short cycles is hard or not is hardly the point. If
we design the system, it is our choice whether or not we allow the use
a short cycle or not. If we do, we have allowed a weakness to be
present in use. On those rare occasions when we expose that weakness,
factoring is no longer hard on that system.
Let me say that again: A guarantee to be as hard as factoring is
useless when we arrange to make factoring easy. All the arguments
about factoring being hard do not apply when we make factoring easy.
This is a way in which "proven" strength need not really apply.
>While we don't actually know how hard factoring is, it seems pretty
>difficult, and has seemed difficult for hundreds of years.
Nope. Factoring is not at all difficult if we have a two-prime
composite and then expose one of the factors.
>There are
>two possibilities at this point:
>
> * Finding cycles is harder than our best algorithm for factoring
> integers. Then we don't need to care about cycles at all, because
> factoring is a better attack anyway.
>
> * Finding cycles *is* our best algorithm for factoring integers.
> Well, we probably ought to care, but we still care just as much
> about factoring, because it's (equivalent to) the best attack.
>
>So either way, the thing to worry about is advances in factoring.
>Cycles are really a bit of a red herring.
Short cycles are a weakness we can prevent. We can choose not to.
But then, when we do use a short cycle, we have only as much strength
as it takes to identify a cycle repeat. Then our composite N can be
factored. Then the guarantee does not apply.
The math doesn't guarantee that factoring is easy if we deliberately
make it easy because we are too lazy to do things right.
>> So "breaking" BB&S means that we have found it to be weak to the given
>> attack, and that -- my goodness! -- might not even overturn
>> mathematics as we know it.
>
>It would certainly be an interesting new factoring method.
>
>> >I still would like you to present something to me as a fact.
>>
>> How about this: That's a stupid request.
>
>Now prove that this is a fact. ;-)
Self evident.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: Tom Anderson <[EMAIL PROTECTED]>
Subject: Re: Plausible Word Generation via Trigram Statistics
Date: Thu, 3 Aug 2000 19:33:28 +0100
On Wed, 2 Aug 2000, Mok-Kong Shen wrote:
> I just saw in a post in a mailing list something that is
> related in some measure to what you are doing. The author
> call it mnemonic encoder. The following is taken from
> his web page http://www.tothink.com/mnemonic
>
> The mnemonic encoding presented here is a method for
> converting binary data into a sequence of words suitable for
> transmission or storage by voice, handwriting, memorization
> or other non-computerized means. The encoding converts 32
> bits of data into 3 words from a vocabulary of 1626 words.
> The words have been chosen to be easy to understand over the
> phone and recognizable internationally as much as possible.
it's not the same thing as Kurt's suggestion, as has been pointed out.
however, it is similar to the PGP fingerprint-in-words scheme; i remember
reading about this, but can't find it on the web. basically, there's a
wordlist (actually, there's two ...), and bytes of data are used as
indices into the list (or something). the words are chosen to minimise the
probability of confusion (a bit like maximising Hamming distance).
tom
------------------------------
From: "CMan" <[EMAIL PROTECTED]>
Subject: Re: Cracking RC4-40 in FPGA hardware
Date: Thu, 3 Aug 2000 11:34:49 -0700
It is possible break a single Word document using a Beowulf array of four
450 Mhz Celeron processors with optimized software in 7 to 30 days because
of certain weaknesses in the MS Word implementation of RC4. If RC4
encrypted Ascii text is being attacked, one can exploit a weakness in RC4 to
do a brute force key search without having any known plain text.
A faster hardware solution would be nice to have if it could be done at a
reasonable price.
The problem is that RC4 is not really amenable to parallel hardware
solutions because of the swapping that is a fundamental part of the cipher.
Perhaps if one could configure enough dual port RAMs on an ASIC the problem
could be solved using massively parallel operations. The problem is bus
contention - all of these swaps demand separate buses in a parallel
solution. The shear number of interconnections becomes a problem very
quickly. Of course a really clever devil may see a way around this
difficulty...
We at CRAK Software would certainly be interested in purchasing such a
design if the price were right :--) Any ASIC designers out there willing to
try??
JK
--
CRAK Software
http://www.crak.com
Password Recovery Software
QuickBooks, Quicken, Access...More
Spam bait (credit E. Needham):
root@localhost
postmaster@localhost
admin@localhost
abuse@localhost
webmaster@localhost
[EMAIL PROTECTED]
[EMAIL PROTECTED]
[EMAIL PROTECTED]
+
Paul Morris <[EMAIL PROTECTED]> wrote in message
news:8mcbbp$[EMAIL PROTECTED]...
> Having recently posted an article called 'Hardware based PK device' I was
> amazed by the very positive response I received - thank you for your time.
>
> Anyway, I received a mail from Paul Rubin who suggested building a device
> capable of cracking RC4-40. Since I think cracking a code has more 'wow
> factor' for project markers (and a more tangible goal) I thought I would
> investigate this a little further especially since being in the UK I think
> 40 bits is all we can legally import from the US.
>
> Paul mentioned that RC4-40 is used in exportable web browsers (presumably
as
> part of the SSLv3) and for password protected files in Microsoft Word.
> Although RSA's site states that RC4 is considered strong, Paul mentioned
> that it could be broken in 'a few months' with a PIII. Given that RSA
> consider it strong are there any other high profile uses for RC4-40? I'm
> very much looking for some 'wow factor' here!
>
> Fundamentally, Paul suggested that multiple (cheap) FPGAs, running
multiple
> threads each, could potentially brute-force break an RC4-40 in, say, 200
> hours or less. Paul coined the name 'Shallow Crack' in reference to the
EFF
> Deep Crack machine. Does anybody have any comments on the feasibility of
> this? Given my limited (but burgeoning) understanding of crypto I would
> assume that a brute-force attack like this would require the attacker to
> have both ciphertext and plaintext. If this is the case it makes a
> transaction using RC4-40, where the key used is a session key, impossible
to
> break since even if one message is compromised the next transmission will
> use a different key. Or am I on the wrong track?
>
> I would be very grateful if I could get (yet more) generous help from
those
> in the know.
>
> a, Is the idea outlined above a feasible concept for a 9 month project?
> b, Is there a similar yet much easier counterpart algorithm that could
prove
> the feasability of the idea (and give me some progress mile stone) along
the
> way?
> c, If I don't have both ciphertext and plaintext how can a brute-force
crack
> work?
> d, Anything else you can think of???
>
> When I finish reading the RSA faq I should be a bit further along
> understanding modern crypto but there is no substitute for experience so I
> would love to here your comments. Anything you can contribute will be
> gratefully received.
>
> Cheers
> Paul Morris
> [EMAIL PROTECTED]
>
>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: Kill my Cipher
Date: Thu, 3 Aug 2000 11:15:46 -0700
I don't have the time to perform a full analysis (I know it seems like I
never do) but, I glanced at the key schedule, and it's apparent that given
knowledge of 2 consequetive round keys you can determine the initial key,
like this:
given r
given ky[r]
given ky[r]
kyr = ky[n] ^ ky[n-1]
for(;r>=0; r--)
kyr = rot(kyr,-r)
kyr is the initial 32-bit key. It would be best to make your round keys in
such a way that given n-1 of them you cannot compute the unknown one. I'll
try and take a look at the rest later.
Joe
"Martin 'SirDystic' Wolters" <[EMAIL PROTECTED]> wrote in message
news:8mbv1k$rv7$[EMAIL PROTECTED]...
> Hi
>
> I wrote another Cipher, and I'd like
> to hear, what you think about it.
>
> It's a 16 round Feistel Cipher, which
> uses 16 subkeys, generated like this:
>
> int ky[0] = 0x00000000;
> int kp[0] = 0x8F1BBCDC; (5^0.5)*(2^30)
>
> for(i=1;i<17;i++) {
> r=kp[i-1]&((1<<32)-1);
> kp[i]=rot(ky[i-1],r);
> ky[i]=kp[i]^kp[i-1];
> }
>
> where ky[0] is a 32 Bit User key and
> rot(x,y) means a Left rotation of x by y
> bits.
>
> this is the f-function it uses:
>
> int f(int in,int k)
> {
> int r,r2,o,o2;
> in=~in;
> r=k&31;
> o=rot(in,r)^k;
> r2=o&31;
> o2=rot(o,r2)^k;
> o2=~o2;
> return o2;
> }
>
> the encryption routine is this:
>
> for(i=0;i<16;i++) {
> x1[i+1]=x2[i];
> x2[i+1]=x1[i]^f(x2[i],ky[i+1]);
> }
>
> where x1[0] are the left 32 bits of
> the 64bit Plaintext and x2[0] are the
> rightmost 32bits of the Plaintext.
>
> The decryption the same, the subkeys
> are just used in reverse order.
>
>
------------------------------
From: Tom Anderson <[EMAIL PROTECTED]>
Subject: Re: Stream Ciphers
Date: Thu, 3 Aug 2000 19:35:27 +0100
On Wed, 2 Aug 2000, Douglas A. Gwyn wrote:
> Tom Anderson wrote:
>
> > classical stream ciphers (which are CPRNGs whose output stream is
> > xored/added into the plaintext stream to give ciphertext stream, with no
> > input into the CPRNG save the key) suffer badly from ...
>
> Stream ciphers don't have to be structured that way.
oh, i am aware of this ...
> That you seldom see them described otherwise in the
> open literature is simply due to a failure of
> imagination and lack of experience with them.
hence all my ciphers are stream ciphers! yes, one day i will unleash one
onto an unsuspecting sci.crypt, and then you'll all be sorry ... MUAHAHAH!
tom
------------------------------
From: Tom Anderson <[EMAIL PROTECTED]>
Subject: Re: I did do it PROTOCOL:
Date: Thu, 3 Aug 2000 19:37:54 +0100
On Wed, 2 Aug 2000, R Fabian wrote:
> Is there any way (protocol) that can be used to prove that a person
> (in this case game player) has got the ping he says he has.
you can prove an upper bound, but not a lower bound, as has been
mentioned, and i think you want a lower bound.
now, if you assume that the client's protocol stack (or at least the IP
and ICMP layers) are unmolested, there is a way to find the ping time -
you simply ping the client from the server.
tom
------------------------------
From: Doug Kuhlman <[EMAIL PROTECTED]>
Subject: Re: Elliptic Curves encryption
Date: Thu, 03 Aug 2000 13:28:27 -0500
Mike Rosing wrote:
>
> Roger Schlafly wrote:
> >
> > Doug Kuhlman wrote:
> > > Have you seen a proof that breaking ECDH is equivalent to the
> > > ECDLP? I haven't.
> >
> > No. It is an open question.
>
> Well, I guess I need to see what's open about it. ECDH is just
> Alice sends aP to Bob
> Bob sends bP to Alice
> they both compute the secret abP.
> ECDLP is finding a (or b) from aP (or bP) and P. Once you have a or b,
> you have the secret.
>
> If you mean whether f(aP, bP) = abP is a possible function without
> solving ECDLP is simpler than ECDLP, then I suppose it's an open
> question. But I don't see how. Every point can be constructed in
> multiple ways from P. Finding f() seems harder to me than ECDLP,
> but I've got a lot of math to learn yet :-)
>
That is exactly the problem. Maybe (somehow) one can find abP with aP
and bP without ever calculating a or b. It doesn't seem possible to me,
either, but that's a far cry from a mathematical proof.
As for your last statement, I concur, but I've learned through hard
experience that expectations in mathematics only occasionally have a
relationship to what can be proven. Maybe no such f exists ... or maybe
it does, but the question, I believe, remains open.
Doug
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: OTP using BBS generator?
Date: Thu, 3 Aug 2000 11:39:04 -0700
The difference lies in the requirements for a OTP. For a OTP the
requirements are very strict, and generally unachievable. The most important
one for this discussion is that each bit of the key stream must have an
entropy content of 1 bit.
Take your favorite keyed pRNG, with a key of size k. Now let's startg the
examination under the best assumptions for the generator. Obviously for the
first bit the generator is good, after all there are k bits of entropy and
only 1 bit of pad generated. For each bit n generated, it also must consume
1 bit of entropy from the pool, so the total entropy used by getting to that
bit is n. When n=k, we have reached the limit of the key, and by encrypting
just 1 more bit we violate the rule for OTP that I gave above. That is why a
pRNG can't be used for a OTP, it's entropy pool is not infinite, so n > k is
unavoidable. Now the requirements for a stream cipher are different, and BBS
may be usable for that.
Joe
"Grant Anderson" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> I know there has been much discussion about (supposed) OTP ciphers and
> how
> most of them generally don't fulfil the OTP requirements. What I don't
> understand is why the use of the blum-blum-shub generator as the pad
> isn't acceptable? I have read a great deal about the characteristics of
> the BBS generator and it *seems* secure as "random-number" generators
> go.
>
> Assuming that each individual has a private key pair (two large primes)
> p
> and q and a public key n such that p x q = n, then the BBS generator
> creates bits by:
>
> x(i)=x^2 mod n for each i
>
> Now obviously you can't use the same pad twice, so you would need to do
> something like having a central repository (the keyserver for example)
> which remembers the last "i" value for each user. So when you want to
> encrypt for user A, you contact the keyserver and obtain their public
> key
> (n) and the initialisation value i and start generating from i+1....
>
> What is wrong with this solution?
>
> Cheers,
> Grant Anderson.
>
>
------------------------------
From: Tom Anderson <[EMAIL PROTECTED]>
Subject: Re: New William Friedman Crypto Patent (filed in 1933)
Date: Thu, 3 Aug 2000 20:03:14 +0100
On Thu, 3 Aug 2000, jungle wrote:
> are we going to expect now that patent on HYPERLINK awarded to BT in
> 1976, that is making SPIN now everywhere in the world, will be
> invalidated because NSA will / could be awarded patent FILED in, say
> 1933 & LOCKED IN CONSPIRACY until now ?
could be. except that the NSA have been beaten to the post by Ted Nelson,
who first used the term 'hypertext' in a publication in 1965, and whose
Xanadu project inspired the web. see:
http://www.xanadu.net/HISTORY/
i think you can trace the lineage of the idea back to Vannevar Bush's
'memex' of 1945:
http://www.theatlantic.com/unbound/flashbks/computer/bushf.htm
i think Nelson even traces it back to the quasi-hypertextual commentary in
the Torah [1].
tom
[1] i think it's the Torah; one of the jewish holy books. i apologise for
my lack of erudition in this field [2].
[2] and for the off-topicness of this post.
------------------------------
Subject: Re: What is the word on TC5?
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 03 Aug 2000 11:49:08 -0700
[EMAIL PROTECTED] (Mark Wooding) wrote:
>tomstd <[EMAIL PROTECTED]> wrote:
>
>> How does the generic attack work?
>
>I described the impossible differentials in Feistel networks
with
>bijective F-functions in
<[EMAIL PROTECTED]>. The
>summary is that there are important structural differential
properties
>of Feistel networks with small numbers of rounds (3 for general
Feistel
>networks, 5 for networks with bijective F-functions).
>
>Since the outer Feistel has only four rounds and a bijective F-
function,
>it exhibits such impossible differentials.
>
>The impossible differential is (0, d) -/-> (?, d). Here's how
it
>evolves:
>
> 1. (0, d) ---> (d, 0)
> 2. (d, 0) ---> (d', d), with d' != 0
> 3. (d', d) ---> (d'', d'), with d'' != d
> 4. (d'', d') ---> (?, d'')
>
>There's another, which is (d, 0) -/-> (d, 0), which is just the
>five-round impossible differential without the first round.
Find specific values of 'd' and I will deem your attack valid.
Tom
===========================================================
Got questions? Get answers over the phone at Keen.com.
Up to 100 minutes free!
http://www.keen.com
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Cracking RC4-40 in FPGA hardware
Date: 3 Aug 2000 19:03:11 GMT
CMan <[EMAIL PROTECTED]> wrote:
>The problem is that RC4 is not really amenable to parallel hardware
>solutions because of the swapping that is a fundamental part of the cipher.
>Perhaps if one could configure enough dual port RAMs on an ASIC the problem
>could be solved using massively parallel operations. The problem is bus
>contention - all of these swaps demand separate buses in a parallel
>solution. The shear number of interconnections becomes a problem very
>quickly. Of course a really clever devil may see a way around this
>difficulty...
I don't see why you need dual port ram. Just use a several separate
sections of the chip with either separate banks of ordinary single
port ram, or synthesize the ram out of logic blocks. The single port
ram means an extra cycle is needed per swap, but that's ok.
The FPGA that I had in mind when I suggested RC4-40 was the Xilinx
Spartan II (www.xilinx.com). The lowest model has four banks of 4k
bytes synchronous ram that can all be operated in parallel, plus
enough CLB's to (it looks to me) provide all the memory needed even
without any ram arrays. The highest model has about 3x as much stuff.
They can run at up to 200 mhz, though the logic delays for something
like this might limit the clock speed to somewhat lower. That's the
basis for my belief that one of these fpga's can crack rc4 at least as
fast as a 1 GHz Celeron/PIII, and maybe a lot faster.
The high-end Spartan II costs $10 in large quantity, so the hope is
that the low-end chip is also around $10 but in small quantity. If
that's the case, it should be possible to build something comparable
in cost to your 4-box Beowulf cluster (why Beowulf? The fast
networking really isn't needed...) but at least 10x faster, using say
20 chips.
I'm certainly no hardware guru though. Maybe someone here who is can
look at the Xilinx page and provide some wisdom on the matter.
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: OTP using BBS generator?
Date: Thu, 03 Aug 2000 19:06:19 GMT
On Thu, 03 Aug 2000 07:01:49 -0700, in
<[EMAIL PROTECTED]>, in sci.crypt lordcow77
<[EMAIL PROTECTED]> wrote:
>Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>>BBS has been a recurring topic in this group. I have little
>>knowledge in that but I have the impression that discussions
>>about it never led to unanimously accepted results. You
>>may try to look into old postings of this group.
>>
>
>Wrong. Practically everyone accepts that choosing the factors of
>the modulus to be congruent to 3 mod 4 and picking a random
>starting point are enough to ensure that the resulting BBS
>sequence will be secure, based on the computational equivalence
>of predicting BBS and deciding quadratic residuosity (and
>therefore factoring).
That is false on its face. You can accept if you want, however.
It is true that using a short cycle would be extremely unlikely. But
*when* that event occurs, all the math proofs you have will not save
you, since the resulting system is insecure.
Using a short cycle is unarguably insecure. And, unless we
specifically prevent it, using a short cycle is an unarguable
possibility.
The only valid argument here is that using a short cycle would be
extremely unlikely, and that is no conflict, because I agree.
>Terry Ritter is the only proponent of the
>position that one must take elaborate steps to ensure that one
>falls into a guaranteed long cycle on the basis of a
>misunderstanding of the security proof given by Blum, Blum, and
>Shub and a desire to assert that no cipher can be proven to be
>secure under reasonable assumptions, such that he can promote
>his own products that "stack" multiple patented algorithms
>together.
Alas for the attempt at a personal attack, I have no current
"products" in that sense. I do hold current patents which represent
fundamentally new cryptographic technology. You can like that or you
can hate it, but I own the technology anyway.
Does the fact that I might make money out of improving technology
somehow make me suspect for pointing out the problems in other
approaches? Finding the problems is why I have better approaches.
But I may be one of the few authors and designers who actively seeks
negative comments and then publishes those on my pages, as readers can
attest.
My stuff is not intended to replace BB&S or PK, but if they have
problems that I see, I'm going to say so, independent of whether I can
profit from that or not.
I have been doing this for the better part of a decade, and I don't
need to have my motives questioned. By pointing out problems, others
can make their own informed choices about how to solve those problems
or perhaps use something else. My patented technology provides
alternatives which others may weigh against the price of its use.
For free, I offer a 400K Crypto Glossary, plus a free Introduction to
Cryptography, Literature Surveys also free, plus lots of other stuff.
You don't have to buy a book to read my stuff, but if you want to read
it in a library, you can do that too, on any Web terminal.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
** 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
******************************
