Cryptography-Digest Digest #106, Volume #13 Mon, 6 Nov 00 01:13:01 EST
Contents:
Re: Brute force against DES ("John A. Malley")
Re: Client Puzzle Protocol ("rosi")
Re: Brute force against DES (David Wagner)
Re: Brute force against DES (Dan Oetting)
Re: Is RSA provably secure under some conditions? ("rosi")
Re: XOR Software Utility (freeware) available from Ciphile Software (Tom St Denis)
Re: [newbie] Is PGP 7.0 hash extension secure? ([EMAIL PROTECTED])
Re: CHAP security hole question ([EMAIL PROTECTED])
Re: Brute force against DES (Sundial Services)
Re: BENNY AND THE MTB? (SCOTT19U.ZIP_GUY)
Re: BENNY AND THE MTB? (SCOTT19U.ZIP_GUY)
----------------------------------------------------------------------------
From: "John A. Malley" <[EMAIL PROTECTED]>
Subject: Re: Brute force against DES
Date: Sun, 05 Nov 2000 18:36:53 -0800
Sundial Services wrote:
>
[snip]
>
> Basically, you forget that most processors now are at least 32-bit. So
> the computer would test 4 bytes all at once, and any process that tried
> to test them individually would actually force more tests to be made.
Just a thought - if the first byte of 4 different decipherments is
tested in one 32 bit value and none of the four bytes match, then a
single test rules out 4 keys at once. If one matches, then 3 keys are
ruled out at once, and so on.
BUT - maybe it takes more cycles to gather the first byte of 4 results
into one 32 bit value and check it than just checking four 32 bit values
one at a time. If so, then there's no advantage.
>
> Nonetheless, the flaw in any "brute force" strategy will not be
> compensated by any such optimization. If you have to test billions of
> keys, instead of thousands, you are going to be forever doing it -- no
> matter how cleverly you test those billions.
Agreed, every bit of "parallelism" helps, yet the shear enormity of the
task may make measures such as these (trying to speed up testing, or
separating out the testing of "likely" keys from the decipherment of
keys onto different processors) moot.
>
> To be effective, a deciphering algorithm must be able to break-down the
> problem, eliminating entire possibilities for each key-byte (or more) so
> that they do not have to be tested at all. Likewise, the cipher must be
> designed so that this cannot be done... provably, cannot be done.
Agreed.
John A. Malley
[EMAIL PROTECTED]
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Client Puzzle Protocol
Date: Sun, 5 Nov 2000 22:32:45 -0500
(Just poor me again. So if you would please, please...)
With virtually no knowledge of TCP/IP, once wondered as well.
Guess, it depends on what they actually meant by 'layered over'.
--- (My Signature)
[EMAIL PROTECTED] wrote in message <8u4dit$mub$[EMAIL PROTECTED]>...
>Hi,
> It's been quiet a while since RSA announced the client puzzle protocol,
>in the paper they claim the protocol can me layered over TCP/IP as a
>solution to TCP SYN Flooding, but is this really possible without
>modifying TCP itself?
>
>Thanks,
>
>bodie
>
>
>
>Sent via Deja.com http://www.deja.com/
>Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Brute force against DES
Date: 6 Nov 2000 03:01:43 GMT
Reply-To: [EMAIL PROTECTED] (David Wagner)
Sundial Services wrote:
>Basically, you forget that most processors now are at least 32-bit. So
>the computer would test 4 bytes all at once, and any process that tried
>to test them individually would actually force more tests to be made.
The time for a trial decryption is substantially larger than the time
for testing a byte (or 8 bytes), so I would not expect this to affect
trial decryption time by more than a small factor.
------------------------------
From: Dan Oetting <[EMAIL PROTECTED]>
Subject: Re: Brute force against DES
Date: Sun, 05 Nov 2000 20:08:15 -0700
Have we forgeten that DES was brute forced to death in the last few
years. (See http://www.distributed.net and others)
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] wrote:
> John A. Malley wrote:
> >
> > If the plaintext block of eight, 8-bit bytes consists of 8 different
> > values - b1, b2, b3, b4, b5, b6, b7, b8 - then when checking the
> > candidate plaintext resulting from trial decryption with candidate key K
> > - d1, d2, d3, d4, d5, d6, d7, d8 - check first that b1 == d1. If not,
> > throw away this key. There is no need to check the remainder of the
> > decrypted output against the remainder of the known plaintext. This
> > reduces the time spent verifying a key.
> >
> > If b1 == d1 then check if b2 == d2. If not, stop and throw the key away.
Having worked extensivly on the decryption code involved in the DES
chalange I can say this optimization was well known and utilized.
However, even working the block from both ends and comparing in the
middle the savings is around 10%. It's worth doing but not a great
breakthrough.
> Nonetheless, the flaw in any "brute force" strategy will not be
> compensated by any such optimization. If you have to test billions of
> keys, instead of thousands, you are going to be forever doing it -- no
> matter how cleverly you test those billions.
The last DES contest was broken in less than 24 hours.
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: Re: Is RSA provably secure under some conditions?
Date: Sun, 5 Nov 2000 23:14:31 -0500
(Just poor me. So if you would please, please...)
IMHO, the convention has it that it _IS_ intractable; and yours may
not be conventional, I am afraid. But the clarification is good.
--- (My Signature)
Jan Fedak wrote in message ...
>I think searching the key space is not really an option since factoring
>a large integer is much faster than an exhaustive search for a key.
>
>By "secure" I'd mean something like: it's provably as difficult to break
>RSA as to factor $n$.
>
>Jan
>
>In article <[EMAIL PROTECTED]>, Douglas A. Gwyn wrote:
>>Jan Fedak wrote:
>>> I wonder are there any conditions under which RSA is provably secure?
>>
>>You would need to define your term "secure", but certainly
>>RSA can in principle be broken in principle, given sufficient
>>(modest) amount of ciphertext (assuming considerable
>>redundancy exists in the plaintext), by searching the
>>deciphering-key space for a value that converts the ciphertext
>>to a highly redundant (testable) output (putative plaintext).
>
>
>--
> Jan Fedak talk:[EMAIL PROTECTED]
> mailto:[EMAIL PROTECTED] mailto:[EMAIL PROTECTED]
> Linux - the ultimate NT Service Pack.
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,alt.hacker,talk.politics.misc
Subject: Re: XOR Software Utility (freeware) available from Ciphile Software
Date: Mon, 06 Nov 2000 03:36:29 GMT
In article <[EMAIL PROTECTED]>,
Anthony Stephen Szopa <[EMAIL PROTECTED]> wrote:
> XOR Software Utility (freeware) available from Ciphile Software
>
> This software simply performs the universally available logical XOR
> process on two files chosen by the user and outputs the resulting
> file.
>
> http://www.ciphile.com
>
> goto the Downloads Currently Available web page.
> scroll to the bottom of the page.
>
> Click on the blue anchor tag: CiphileXOR_10.zip (155kb)
How on earth did you make such a simple program take 155kb?
Tom
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: [newbie] Is PGP 7.0 hash extension secure?
Date: 05 Nov 2000 20:57:35 -0800
Zero-Knowledge MIME Encapsulated Message
--6OO8AUTBEX9FKQH
Content-Type: text/plain
"Thomas J. Boschloo" <[EMAIL PROTECTED]> writes:
> I had a little e-mail conversation with Micheal Young on the hash extension
> used in PGP (described in RFC 2440). I am not as knowledgeable as him, so I
> can't see if his arguments are true.
>
> My statement was that in order to use Twofish or Rijndael to its full
> potential of 256 bits security, you would need to have a 256 bit hash
> function like they are creating a draft for in
> <http://csrc.nist.gov/cryptval/shs.html>. Micheal Young however, claims that
> the process used in PGP to extend the SHA-1 algorithm to 256 bits is secure
> enough. In PGP you have a large ammount of random data in your entropy pool
> and a 256 bit session key is generated by taking the SHA-1 hash on this
> data. Then the extra missing 96 bits are generating by feeding that same
> pool, with a '/0' character prepended to it, to the SHA-1 function.
This is not correct. You are confusing the method used by PGP to
generate keys from passphrases with the method used to generate random
session keys.
PGP generates session keys in one of two ways. Either the key is
based on a user passphrase, or it is generated from the internal
random number generator.
The mechanism of passing data through a hash twice, prepending a zero
the second time to get more bits out than the hash size, is used for
turning a passphrase into a key. Assuming your passphrase has 256
bits of entropy, this method should produce 256 bits of random output,
within a bit or two.
If you are generating a random session key (as when encrypting to a
public key), the PGP random number generator is used. The code for
this is complicated and involves both hash and encryption transforms.
It does not use the simple structure you are worried about.
Ob
--6OO8AUTBEX9FKQH--
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: CHAP security hole question
Date: Mon, 06 Nov 2000 05:12:09 GMT
In article <8ts26o$19q$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Vernon Schryver)
wrote:
> In article <[EMAIL PROTECTED]>,
> Thomas Wu <[EMAIL PROTECTED]> wrote:
>
> >
> >But as long as humans must authenticate
themselves over networks using
> >secrets stored in their heads, strong password
protocols are useful.
>
> Humans cannot store the many passwords needed to
authenticate themselves
> over networks, because in the real world they
necessily many passwords.
> Strong password protocols are largely
irrelevant.
Humans *can* remember passwords, but the trouble
starts happening
when they're forced to remember passwords that are
difficult to remember.
Strong password protocols are *precisely* relevant
to these cases, because
they protect passwords from offline guessing.
> >And aren't humans really the ultimate endpoints
for all these fancy
> >cryptographic technologies?
>
> When was the last time you participated in the
CHAP PPP authentication
> process? The answer is almost certainly
"never." You might have acted
I don't know if you're deliberately
misunderstanding what I'm saying or if
you really don't understand the point.
Ultimately, a human is what is being
authenticated. Your PC may bringing up a PPP
link, but it's bringing it
up on your behalf.
> Except for the reliability of PC's and the
inevitable need to apply
> Microsoft Repair Technique #1 (re-install
software), there would be
> nothing wrong with an installation scheme in
which a user
> - downloads a program in the usual
InstallShield format
> - the program chats with the user to collect
credit card and
> geographic info (to pick a telephone
number)
> - the program negotiates with the Internet
service provider
> to pick a long, random password and then
jams it into the
> Microsoft PPP configuration stash.
How is this long, random password exchanged
securely? Are you assuming
that on-line communication to your ISP is already
secure?
> In such a scheme, the human user need never know
the CHAP secret.
> Thus, it is wrong to talk about PPP CHAP
authenticating a *human* user.
>
> > ...
but once again the aim of
> >strong password protocols is to improve network
security without further
> >inconveniencing the user. While it is not good
practice to share passwords
> >between sites, for example, some users will do
it, and I don't think there's
> >a easy way to prevent it.
>
> Someone with no sympathy for SRP could twist
those words into "SRP is
> intended to encourage users to pick terrible
passwrords that even SRP
> cannot protect (e.g. human name) and to use the
same terrible password
> evreywhere." The less twisted might say that
protecting poor (instead of
> terrible) passwords is a much worse solution
than almost eliminating the
> problem.
Clearly you don't have much sympathy for strong
password technolgies,
but why not try taking the words at face value
rather than twisting them?
It is better to design an authentication system
that acknowledges
the limitations of human factors and takes them
into account, rather than one
that imposes significant inconvenience upon users
in order to achieve security.
> With smartcards you could have dozens of
unbreakable passwords with the
> same safety and convenience as SRP, EKE, and so
forth would allow with a
> single password. It's not a minor detail that
everyone has enough
> different passwords that SRP cannot help.
You keep talking about how easy and wonderful
smartcards are without
realizing their downsides (expense, availability,
interoperability,
overhead, user acceptance). Maybe people don't
*want* smartcards
everywhere.
> > If zero-knowledge
password protocols are in use,
> >however, it makes it that much harder for, say,
a rogue admin from one site
> >to harvest passwords that he can try elsewhere.
>
> That is true only of really bad authentication
protocols, such as cleartext
> FTP and Telnet, and stupid rogue admins.
Zero-knowledge password protocols
> do not matter to rogue system administrators who
understand what they are
> doing. They do not merely sniff packets to
steal passwords.
You have shown by statements like the above that
you do not fully
understand the concept of strong/ZK password
protocols, and that you
refuse to do the reading and the research before
making false statements.
Are you actually interested in learning through
this discussion, or merely arguing?
> Memorizing dozens of easy passwords is harder
than memorizing a single
> good password, and the assumption behind EKE,
SRP, and so forth is that
> latter is too hard for humans. The human
authentication problem involves
> proving yourself in many situations to many
different others.
> Zero-knowledge systems today are worse than
cleartext telnet was in its
Now you're just being silly.
> day. When telnet was created, the reasons that
make cleartext passwords
> silly did not exist, so that they made sense.
The requirements for dozens
> of separate passwords irrelevant exist today and
make zero-knowledge
> password protocols irrelevant at birth for
anything but fixing obscure,
> archane applications such as rlogin, telnet, and
ftp.
If password-protected network access is "obscure
and arcane" for you,
fine, but I think there are plenty of applications
where this is important.
> In other words, the current reality of dozens of
passwords forces people
Sites that force artificial "good password" rules
on human users do this.
Let's be clear on our assumptions.
> to write them down. If you're writing them
down, you may as well use good
> ones, and in that case you don't need
zero-knowledge password protocols,
> except for things like telnet and ftp, which
hardly anyone uses. (I and
> probably anyone with a Xenon.Stanford.EDU use
them, but we don't count.)
>
> > ...
> >When we get cheap, powerful, universal,
interoperable, secure smartcards
> >into everyone's hands, you might have a point.
But that utopia may
> >never materialize. Why bet on it?
>
> So it's better to bet on people doing what you
know they can't and
> won't do, have sufficient distinct passwords and
use SRP?
No, it's better to bet that humans won't
spontaneously develop better memories and
to design around that.
> People already have non-portable smartcards in
their laptops and even
> desktop PC's, not to mention palmtops. There
are several Windows
> applications for managing passwords. Consider
also how you could use the
> data sync machinery of a palmtop to make it a
fat smartcard.
>
> If PC's did not run such incredibly insecure by
design microstupid
> operating systems, prudent people could use what
might be called a virtual
> smartcard. Take the familiar notion of a
smartcard that applications talk
> to get what's needed for an authentication
dance. Modify it to consist
> of a program, a well encrypted file, and an
intra-host protocol such as
> a dynamically loaded library ABI. You wouldn't
want to use such thing on
> a stranger's computer and perhaps not even on
shared computer where bad
> guys might arrange to watch the insides of a
virtual smartcard. On your
> own trojan-free laptop or desktop, that would be
more secure and more
> convenient than a zero-knowledge protocol system
where the user necessarily
> consults the sticky-note on the monitor for the
right password.
Fine, if you really believe that, go ahead and
design, develop, and
market your fat smartcard. You might get a better
understanding of
the technical and economic difficulties that David
and I have been talking about.
> Note that to use SRP, you must also hope to be
trojan-free. For example,
> you must trust everyone who can affect what runs
on your computers,
> including those who run NFS servers mounted
without NOEXEC or at least
> NOSUID.
I think that's the only real argument for hardware
tokens. But that must be
balanced against their many disadvantages.
> >> In other words, there are good reasons why
zero knowledge schemes have
> >> not taken the Internet by storm, ...
> >
> >Reasons, maybe, but not particularly good
ones. I'd attribute it mostly
> >to a combination of ignorance and inertia. But
even that is changing
> >these days.
>
> Consider the dates conveniently provided by your
>
http://www-cs-students.stanford.edu/~tjw/srp/analysis.html
> EKE dates from 1992. SRP finally may solve the
telnet and rlogin password
> problem, which after all these years is a good
thing, but very faint praise.
> That SRP, EKE, and so forth do not solve the
authentication problems most
> of people is not merely ignorance and inertia.
I think it is exactly ignorance and inertia.
People don't always take the
time to find out all the facts on new technologies
before dismissing them
in their own minds.
> Vernon Schryver [EMAIL PROTECTED]
Tom Wu
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Sun, 05 Nov 2000 22:29:24 -0700
From: Sundial Services <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Brute force against DES
DES -has- been successfully bludgeoned into submission by a
special-purpose computer built to test a massive number of keys per
second. (Somehow, it didn't seem quite "cricket," though. And it was
actually a pretty good demonstration of just how strong the DES
algorithm actually is.)
My point is that, unless you do have a massively-parallel supercomputer
at your disposal with which to brutalize DES, the fact that you must
test billions of keys "at all" is the root cause of your grief. If you
have eliminated 3 keys, then so-what, you've still got "Carl Sagan" keys
to go.
A successful "break" of DES would have to eliminate testing some of the
key -bits-, by somehow concluding "bit #X in the key must be 1" or "must
be 0." That would cut the search-space in half for every bit you could
conclude. The DES algorithm has been designed to make this (as far as
we know) unfeasible. Thus you must resort to brute force. As far as we
know.
>John A. Malley wrote:
> Just a thought - if the first byte of 4 different decipherments is
> tested in one 32 bit value and none of the four bytes match, then a
> single test rules out 4 keys at once. If one matches, then 3 keys are
> ruled out at once, and so on.
>
> BUT - maybe it takes more cycles to gather the first byte of 4 results
> into one 32 bit value and check it than just checking four 32 bit values
> one at a time. If so, then there's no advantage.
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: BENNY AND THE MTB?
Date: 6 Nov 2000 05:31:39 GMT
[EMAIL PROTECTED] (Bryan Olson) wrote in
<8u4jjk$rja$[EMAIL PROTECTED]>:
>Tim Tyler wrote:
>> Bryan Olson <[EMAIL PROTECTED]> wrote:
>> : Tim Tyler wrote:
>> :> What you are now talking about has nothing to do with what
>> :> Joseph Ashwood was talking about.
>>
>> : Not true. [...]
>>
>> I think it's true. How else can you eplain that he stated that the
>> decryption of the cyphertext is one of 2^120 blocks? Joseph was
>> discussing a system that no-one ever proposed - and which would
>> not work.
>
>The way I understand Ashwoods posts, he was showing that
>no system that typically worked as described in David
>Scott's story could exist. He was refuting Scott, not
>Timmermans.
I said the story was MADE UP that means fiction. However
the files where true the Pass key was true. You can take MATTS
CODE and DO the thing your self. I guess you lucky the guy in
the story didn't happen to by chance pick a smaller file. As
you now are currently aware the message could almost just as
easily mapped to the NULL file.
>
>Again, Ashwood was not talking about the specifics of Matt's
>system. He was showing that a system that worked as described
>in the story _had_ to be non-existant.
>
THe systme corrently showed how the files worked using
Matts not so non-existant program.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: BENNY AND THE MTB?
Date: 6 Nov 2000 05:26:52 GMT
[EMAIL PROTECTED] (Tim Tyler) wrote in <[EMAIL PROTECTED]>:
>Matt Timmermans <[EMAIL PROTECTED]> wrote:
>
>: Yes, Bryan's analysis is correct.
>
>: All zeros counts as a finitely odd stream [...]
>
>AFAIK, you are responsible for inventing this terminology - so I hesitate
>to tell you what I think of it.
>
>I liked David's definition of a finitely odd file - where 0 is not
>included.
>
I like it better to :)
However his finitely odd and mine are different. I checked his
with a null file. You can decrypt to null file to get something
that when it compresses you back you go back to a null file.
I don't think Matt had to chose it that way. But he did and there
is more than one way to choose it. My compress h2com also compresses
a null file to a null file. I just checked becasue I was not sure
what it did. I never really intended to use null files as data.
If the IEEE gets interested in bijective compression encryption
this is something they could argue about. I would vote for not having
the null file as a data file. Or if I did I would make it compress
to its self or encrypt to its self. One can actaully do either. Or
maybe several standards could be allowed. A simple change to Matts
is this.
His Way
If file A compress encrypts to NULL with KEY X
if NULL compress encrypts to file B with KEY X
leave it alone you have Matts current.
My alternate way.
get resulte above but then
define file A as compress encrypts to file B with KEY X
define NULL as compress encrypt to NULL
Matt also note you compression currently compress NULL to NULL
this is just a thought. THere are many ways to do it and
maybe most will prefer the current way your doing it if they
ever understand the concept at all.
>Any definition which includes the word "odd" and includes the
>number 0x00000000 is highly counter-inutitive.
>
>"Finitely odd" should refer to streams which terminate in a 1 followed by
>an infinite string of zeros, IMO.
>
>If a term for finitely odd files which /includes/ zero is desirable,
>I believe the emphasis should be on the trailing zeros, rather than the
>last 1. "Zero tailed", perhaps.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE
http://www.jim.com/jamesd/Kong/scott19u.zip
Scott famous encryption website **now all allowed**
http://members.xoom.com/ecil/index.htm
Scott LATEST UPDATED source for scott*u.zip
http://radiusnet.net/crypto/ then look for
sub directory scott after pressing CRYPTO
Scott famous Compression Page
http://members.xoom.com/ecil/compress.htm
**NOTE EMAIL address is for SPAMERS***
I leave you with this final thought from President Bill Clinton:
------------------------------
** 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
******************************
