Cryptography-Digest Digest #497, Volume #9 Tue, 4 May 99 02:13:04 EDT
Contents:
small modular exponentiation routine wanted (Paul Rubin)
Re: Factoring breakthrough? (lcs Mixmaster Remailer)
Re: A challenge for you ! (root)
Re: Deadly threats (root)
Re: Obvious flaws in cipher design (root)
Cool stuff too see ([EMAIL PROTECTED])
Re: Encrypted Phones (Frank Costantini)
Shamir's Discover: to those in the know (Jeff Hamblin)
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
([EMAIL PROTECTED])
Re: Deadly threats ("hapticz")
Re: Thought question: why do public ciphers use only simple ops like shift and XOR?
(Terry Ritter)
Re: Factoring breakthrough? ("Michel Bouissou")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: small modular exponentiation routine wanted
Date: Mon, 3 May 1999 23:31:40 GMT
I'm looking for a small subroutine for modular exponentiation on the
x86. It can be in C or x86 assembler (32 bit). Ideally the code size
should be 4k or smaller, though that's not a hard limit. I'm not too
worried about speed, within reason. I know about MIRACL and BNLIB,
but these are tuned for speed and include a lot of optimizations which
make the libraries faster but increase the code size. Any suggestions?
PS, a small SHA-1 routine (smaller than the one I'm using) would also
be nice, though I have a fairly small one (in C) already. The application
is a DSA signature verification module.
------------------------------
From: lcs Mixmaster Remailer <[EMAIL PROTECTED]>
Subject: Re: Factoring breakthrough?
Date: 4 May 1999 00:00:04 -0000
Paul Rubin <[EMAIL PROTECTED]> wrote:
> Oh what the heck. I've heard it is based on work that Prof. Shamir
> presented at the Crypto 97 rump session, where you'd stack up 1000's
> of sheets of photographic film and see where the dots lined up. Kind
> of reminiscent of Zygalski's perforated sheets used for breaking
> Enigma ;-). I don't remember details from the Crypto talk though.
Here are my notes from that talk:
The idea is to break 40 bit DES using film as an analog computer.
Photographic film can hold 2^30 pixels per square inch, so 10 yards
of 70 mm movie film could hold 2^40 pixels.
Treating pieces of such film as long, 2^40 bit "registers", certain
logical operations can be performed on them using photographic techniques.
Negating a register can be done by taking the photographic negative of
the film. NOR is done by stacking multiple strips of film and exposing
through them. NAND is a double exposure (first expose through one,
then expose through the other). XOR is a combination of these.
For DES key search, treat each pixel position as corresponding to a
trial key. The keys themselves must then span 40 strips of film, with
the first strip of film holding the MSB of all keys, the last holding
the LSB of all keys, and the other strips holding the intermediate bits.
Then the 40 bits of a trial key can be read by reading the pixel values
at corresponding locations on the 40 pieces of film, and the films are
big enough to hold 2^40 keys.
The films can be initialized just by exposing them to random noise.
This will initialize each of the 2^40 keys to a random value, and there
will therefore be approximately 2^40 distinct keys.
It is then a matter of using the logical operations on these films to
implement the DES algorithm with a known plaintext/ciphertext pair.
The logical operations of NOT, NAND and NOR are enough to implement DES.
DES has 66 gates per S-box; Shamir worked out from this how many logical
operations you'd have to do, but my notes don't include the result.
At the end, if a key was correct you'd have a single dot at that point
in the final film. You could then go back and read the initial key
which corresponded to that pixel position and you'd have your answer.
Of course, in the time since Shamir's talk there has been considerable
progress in computer technology, and breaking 40 bit DES keys is no
longer especially difficult. The EFF's Deep Crack machine can break them
in just a few seconds, while Shamir's technique would surely take many
hours or days of work. Shamir's films would probably cost considerably
less, though.
------------------------------
From: root <[EMAIL PROTECTED]>
Subject: Re: A challenge for you !
Date: Mon, 3 May 1999 19:48:16 +0200
i realy would have to agree with John Savard here...
if your not going to give the algorithm up then i can tell you right now
that its not secure...
--Hawkhaven
"Win if you can, lose if you must, but always, always cheat!"
------------------------------
From: root <[EMAIL PROTECTED]>
Subject: Re: Deadly threats
Date: Mon, 3 May 1999 20:21:38 +0200
On Sun, 2 May 1999, Anonymous wrote:
> hapticz wrote:
> > if I continue to send deadly physical threats to high government officials
> > in encrypted form without the keys, am i liable to be prosecuted?
only if you admit that its a threat...ooops too late...seriously though
the secret servise doesnt have a very good sense of hummer when it comes
to that sort of thing...(although the chances of them coming after you is
still slim)
--Hawkhaven
"Win if you can, lose if you must, but always, always cheat!"
------------------------------
From: root <[EMAIL PROTECTED]>
Subject: Re: Obvious flaws in cipher design
Date: Mon, 3 May 1999 20:25:38 +0200
On Sun, 2 May 1999, SCOTT19U.ZIP_GUY wrote:
> If the user password is only a few characters in lenght then one
> needs only to search a small character space to test for a break in
> the code. Also if the string of characters is much longer than 128 bits
> such that it has an entropy of larger than that if a random 128 bit
> string even perfect hashing would allow for more than one ascii string
> to map to the same key. If the ascii string is exactly 128 bits. All
> hashing could do is increase the chance of a common mapping to a certain
> key and hashing should not be done at all. One needs to hash only if
> the password is longer than the key.
>
> David A. Scott
this of course assumes that the tiny-brains of the planet will choose
desent passwords...it has been my experience that they dont...
--Hawkhaven
"Win if you can, lose if you must, but always, always cheat!"
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.econ,sci.environment,sci.geo
Subject: Cool stuff too see
Date: Tue, 04 May 1999 01:51:13 GMT
Goto http://www.geocities.com/Hollywood/Agency/8089/ for it
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: [EMAIL PROTECTED] (Frank Costantini)
Subject: Re: Encrypted Phones
Date: 4 May 1999 02:50:38 GMT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
>Greetings,
>
> The only encrypted phones I can find are being produced by the
>federal systems division of motorola (like we should trust them?).
>
> Does anyone know of any digitally encrypted (super secure) phones
>that can be plugged in and used over standard phone lines? PGP
>phone is the closest thing I can find, but I need boxes that are
>"plug and play" (don't require a MS O.S.).
>
> thanks in advance,
>
>Bill Bishop
>
You may want to check out a product at
http://www.l-3com.com/privatel/
It connects between the handset and base of your existing phone, so it
works over standards POTS phones, ISDN phones, and digital PBX phones.
This may provide what you are looking for.
Frank Costantini
------------------------------
From: Jeff Hamblin <[EMAIL PROTECTED]>
Subject: Shamir's Discover: to those in the know
Date: 4 May 1999 03:02:06 GMT
if you are fortunate enough to hear shamir speak about his new toy, please put
some technical info up here for the rest of us clamoring for info. even if you
don't hear him speak, but you already know about it, feel free to spout off
after he talks. it's open season after he presents, as i understand. and i'm
so very curious.
thanks
--
jeff
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Tue, 04 May 1999 01:40:01 GMT
Terry Ritter wrote:
> [EMAIL PROTECTED] wrote:
> >Terry Ritter wrote:
> >[...]
>
> >[...]
> >Use of a different cipher for each compartment would make
> >some sense. The intelligence value of messages would be
> >somewhat partitioned among the ciphers. That is not the
> >scheme you proposed.
>
> I note that if your interest was in getting a good design, you would
> be promoting your scheme as "better." You are not.
My interest here is in correct results. I believe the best
response to a design with terrible flaws is to clearly identify
and explain those flaws.
> I proposed using a different cipher for each message. That is
> *superior* to having a different cipher for each intelligence
> compartment. But no sort of compartmentalization will by itself solve
> all security problems.
>
> >Your opener "as far as I know" is kind of a giveaway.
>
> The only "giveaway" here is that I am not inside the security
> community. That is no surprise. But I doubt anyone questions that
> compartmentalization is in fact used in practice.
Of course it is. Did someone suggest it isn't?
> >If
> >you knew in detail how classified systems work, you would
> >not be allowed to post it here. Since you don't, I suggest
> >you not try to serve a market you know little about.
>
> What kind of argument is that?
It's an argument against accepting premises that are merely
speculation on how classified systems work. We have actual
customers with actual projects and they provide the environment
in which our systems need to work.
> If I knew current development from the inside, how could I develop
> improvements for the outside? My stuff is not for "classified
> systems," it is for ordinary cipher users.
Exactly.
> The use of randomly-selected ciphers on a per-message basis closes a
> fundamental security hole in ciphering. That hole is the fact that
> some attacks expose not just the current message, but almost any
> message ever sent. And we cannot know when such an attack exists, or
> is being applied. The absolute *best* we can do is to terminate any
> such attack by moving on to other ciphers.
It closes no such hole. Suppose an attacker has a 5% chance
of breaking any of our ciphers (which may be multi-ciphers).
If we choose one and only one cipher, then we have a 5% chance
of exposing all our traffic. If we encrypt each message with a
random choice from 1000 ciphers, then we will almost certainly
loose 5% of our traffic. The problem is that a random 5% of
the traffic probably contains most of the useful intelligence.
We don't know that the number is 5%, but of course I only offered
that number to make the example concrete. The argument holds for
any reasonable value, whether we know what it is or not.
[...]
> However, it may be that projects of highest security should transmit
> only changes to any plan. These would be "updates" instead of
> "replacements," the way software is sometimes changed.
Is that how your customers do it?
> >Where the
> >information any pair of users shares is disjoint from what
> >any other pair shares?
>
> Sure. It is called working independently. As far as I know, this is
> in fact used in the highest security projects.
I suppose one could work independently then burn the results
of the work, but I don't think that's indicative of real-world
projects.
> >No such argument appeared.
>
> It is perfectly reasonable to demonstrate false logic by showing that
> a similar construction implies false results.
No similar argument appeared.
> >You also have the flaw backwards;
> >the real problem is not one message carrying a great deal of
> >intelligence, but that many messages carry the same intelligence.
> >That intelligence is available to an attacker that can read just
> >one of the messages carrying it.
>
> The flaw is what it is; the only "backwards" thing about it is your
> view of it.
Be careful not to confuse failure to recognize the problem
with not having the problem. The flaw I pointed out is that
real-world messages have a great deal of inter-message
redundancy. If the same information is available from several
messages, each encrypted with a different cipher, then a break
to any of several ciphers exposes the information. You are
welcome to consider other flaws of course, but please don't
package those comments as I response to what I wrote.
> It seems clear enough that losing the data in a single message is far
> better than losing all data over all of time.
No one said otherwise.
> Certainly users will
> change projects: Even exposing the entire current project is far
> different than exposing all past and future projects.
So one cipher per project might make sense.
> >[...]
> >> >I think dynamically
> >> >choosing ciphers from a large pool is simply naive.
> >>
> >> But the question is whether you have a factual basis for this opinion,
> >> and whether you draw your conclusions from a reasoned argument. None
> >> of that is given here.
> >
> >Wrong. The premise was clearly stated: that in real world projects
> >and in real world enterprises, the same intelligence is carried in
> >many messages. No one has disagreed, with the possible exception
> >of your conjectures about compartmentalization above.
>
> Compartmentalization is a fact. That real security organizations do
> use compartmentalization is a fact. The only "conjecture" here is
> that I cannot personally testify to that from current experience.
The possible exception was your (false) conjecture that each
compartment holds one basic secret.
In any case, compartmentalization by subject area makes sense,
while random compartmentalization does not.
> But
> "no one has disagreed" with me about that, with the possible exception
> of your handwaving which is apparently based on no facts at all.
Your hiding your head in the sand. The purpose of
compartmentalization is to partition the intelligence in the
data. Random compartmentalization does no such thing.
What facts have I relied on that are not in evidence? The
factual basis of my argument is that in real world enterprises
and real world projects, the same information is carried in
many messages. I certainly have a great deal of personal
experience to back that up. Do other people have major
customers that don't send document revision around to the
team? Where every meetings minutes contain disjoint
information from the last? Look at ISO 9000; how many parties
will look at the same on-line document?
The facts are clear. If you'd stop guessing about secret
systems and look at how your own customers work you'd see
them first-hand.
> >I showed how
> >the conclusion follows from the premise, and if you doubt the
> >premise you have only to look at real world projects, read texts on
> >project management, or look at how the information systems that
> >support team projects work.
>
> The compartmentalized system can be attacked and exposed message by
> message. But a break only exposes the information in one message.
True.
> And if that message does not in fact contain "all" information
> protected by the system over time, then that break does not expose
> "all" information.
The real problem is that we expect the number of breakable ciphers
in use to be roughly proportional to the number of ciphers. It may
be worse, since we can't validate each of 1000 ciphers nearly as
well as each of a few.
[...]
> When we have only one cipher, we need no protocol for changing
> ciphers.
To avoid needless repetition, I suggest we focus on the
points where we disagree. For years I've been a proponent
of protocols that are independent of cipher choice. See my
criticism of "The Design of Penknife" for example.
> >The subject here is the per-message random choice of ciphers.
>
> With "PMRC" a break exposes the content of one message. If we assume
> that some of the ciphers are weaker than one we would have chosen, we
> may lose the contents of several messages. That is unfortunate, but
> we can continue our work.
As shown above, PMRC moves us from a small chance of exposing
all the traffic to almost assuredly exposing a small portion of
the traffic. Combined with the inter-message redundancy of real
traffic, PMRC moves us from a system in which catastrophic failure
is possible, to one in which it is inevitable.
--Bryan
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: "hapticz" <[EMAIL PROTECTED]>
Subject: Re: Deadly threats
Date: Mon, 3 May 1999 23:21:16 -0400
i always was suspicious of govenment branch with initials "SS"
it just kinda' smacked of another group of "heavies"!
then again, there's many more secrets the peoples in this democracy never
know about until it's too late to do anything about.
("all for our own good" or something like that!)
--
best regards
[EMAIL PROTECTED]
remove first "email" from address, sorry i had to do this!
root wrote in message ...
|On Sun, 2 May 1999, Anonymous wrote:
|> hapticz wrote:
|> > if I continue to send deadly physical threats to high government
officials
|> > in encrypted form without the keys, am i liable to be prosecuted?
|
|only if you admit that its a threat...ooops too late...seriously though
|the secret servise doesnt have a very good sense of hummer when it comes
|to that sort of thing...(although the chances of them coming after you is
|still slim)
|
|
|--Hawkhaven
|
|"Win if you can, lose if you must, but always, always cheat!"
|
|
|
------------------------------
From: [EMAIL PROTECTED] (Terry Ritter)
Subject: Re: Thought question: why do public ciphers use only simple ops like shift
and XOR?
Date: Tue, 04 May 1999 05:31:27 GMT
On Tue, 04 May 1999 01:40:01 GMT, in
<7glj5g$3ap$[EMAIL PROTECTED]>, in sci.crypt
[EMAIL PROTECTED] wrote:
>Terry Ritter wrote:
>>[...]
>> The use of randomly-selected ciphers on a per-message basis closes a
>> fundamental security hole in ciphering. That hole is the fact that
>> some attacks expose not just the current message, but almost any
>> message ever sent. And we cannot know when such an attack exists, or
>> is being applied. The absolute *best* we can do is to terminate any
>> such attack by moving on to other ciphers.
>
>It closes no such hole. Suppose an attacker has a 5% chance
>of breaking any of our ciphers (which may be multi-ciphers).
>If we choose one and only one cipher, then we have a 5% chance
>of exposing all our traffic. If we encrypt each message with a
>random choice from 1000 ciphers, then we will almost certainly
>loose 5% of our traffic. The problem is that a random 5% of
>the traffic probably contains most of the useful intelligence.
But that is not a good model of the real situation.
In reality, an attacker has some chance of breaking a cipher *given*
*some* *amount* *of* *time,* *effort* *and* *resources*.
With only one cipher, an attacker continues to pour effort and
resources into that one problem.
With a growing body of ciphers, there is less effort and fewer
resources for attacking any one cipher. Ciphers might even be retired
after a few years of service, thus limiting the effort spent attacking
them, and also limiting the value of information they protect.
With only have a single cipher, that cipher stays in place and
continues to be a target. In fact, it gets to be an increasingly
choice target, as the cumulative value of information protected by
that cipher increases. This may justify even more attack effort.
>[...]
>Be careful not to confuse failure to recognize the problem
>with not having the problem. The flaw I pointed out is that
>real-world messages have a great deal of inter-message
>redundancy. If the same information is available from several
>messages, each encrypted with a different cipher, then a break
>to any of several ciphers exposes the information. You are
>welcome to consider other flaws of course, but please don't
>package those comments as I response to what I wrote.
You address a supposed "flaw" in the many-cipher system, then fail to
address the analogous flaw in the one-cipher system you prefer.
The "flaw" here is that information flow contains redundancy which
allows significant intelligence to be extrapolated from a small
proportion of exposed messages. But *that* is fact; the "flaw" part
of this is the exposure of some amount of the hidden information as a
consequence of that fact.
Broken ciphers expose information in both systems: In the
multi-cipher case, we can assume that having more ciphers means more
ciphers could be broken. Fine. But if a cipher is broken, the user
proceeds on and the next cipher will be secure again. A past exposed
message simply does not reveal a future creative activity.
In the single cipher case, a break exposes *all* of the hidden
information. And since the break is not known by the user, the
information continues to flow, and the exposure continues until the
cipher system is replaced.
It would be nice to have a system with no flaws at all. But in real
systems we are concerned with tradeoffs. In my view, the risk of
catastrophic permanent failure is vastly more significant than an
occasional transient exposure.
>[...]
>In any case, compartmentalization by subject area makes sense,
>while random compartmentalization does not.
On the contrary, automatic random compartmentalization makes at least
as much sense, and requires far less management.
With normal compartmentalization, a single individual within the
compartment can reveal most of that compartment *plus* what can be
extrapolated from *that* vast quantity of divergent information.
With automatic random compartmentalization, a single message reveals
only what it carries and what can be extrapolated from it and a few
other messages.
Extrapolation occurs in both cases, but there is more to go on when
more primary information is revealed.
>[...]
>Your hiding your head in the sand. The purpose of
>compartmentalization is to partition the intelligence in the
>data. Random compartmentalization does no such thing.
Sure it does.
>[...]
>The facts are clear. If you'd stop guessing about secret
>systems and look at how your own customers work you'd see
>them first-hand.
Oddly, I see the issue of the unknown break which continues to be
exploited for the foreseeable future as a breathtaking flaw in
conventional cryptography. Given that the ordinary references do not
discuss this little detail, I suspect it will take some time for users
to understand what this issue means to them.
>[...]
>The real problem is that we expect the number of breakable ciphers
>in use to be roughly proportional to the number of ciphers.
I agree.
>It may
>be worse, since we can't validate each of 1000 ciphers nearly as
>well as each of a few.
I agree.
But the rest of the story is that attack effort is either apportioned
among many ciphers, or focused on one. Which is better for the user?
>[...]
>As shown above, PMRC moves us from a small chance of exposing
>all the traffic to almost assuredly exposing a small portion of
>the traffic.
This false conclusion is a consequence of using an inappropriate model
for cipher weakness. When we realize that limited resources require
attackers to apportion effort among used ciphers, we see that
increasing the number of ciphers decreases the effort available for
any one. The alternative, of course, is for all effort to be aimed at
one cipher.
---
Terry Ritter [EMAIL PROTECTED] http://www.io.com/~ritter/
Crypto Glossary http://www.io.com/~ritter/GLOSSARY.HTM
------------------------------
From: "Michel Bouissou" <[EMAIL PROTECTED]>
Subject: Re: Factoring breakthrough?
Date: Sun, 2 May 1999 13:41:24 +0200
lcs Mixmaster Remailer a �crit dans le message
<[EMAIL PROTECTED]>...
>Rumor has it Adi Shamir will announce factoring breakthrough soon.
>Increasing efficiency by orders of magnitude and breaking keys 100-200
>bits longer than current state of the art.
>
>Anybody confirm/deny?
A first article in the N.Y. times. Take a look at
http://www.nytimes.com/library/tech/99/05/biztech/articles/02encr.html
--
Michel Bouissou <[EMAIL PROTECTED]> DH/DSS ID: 0x80DBBD8F
Prot�gez votre correspondance avec PGP: http://www.pgpi.com
Informations: Nouvelle URL: http://come.to/pgpenfrancais
Prot�gez votre disque dur: http://www.scramdisk.clara.net
------------------------------
** 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
******************************
