Cryptography-Digest Digest #769, Volume #10 Sun, 19 Dec 99 20:13:01 EST
Contents:
Re: Attacks on a PKI (Timothy M. Metzinger)
Re: compression & encryption (Jerry Coffin)
Commercial Cryptanalysis. (Glenn Larsson)
Re: dictionary attack (JPeschel)
Re: US Patent Office: How Stupid? Look Here... (Anthony Stephen Szopa)
Re: compression & encryption ("Matt")
Re: DES key safety (Peter Pearson)
S-Box evolution (Glenn Larsson)
Re: dictionary attack ("Michael Velten")
Re: compression & encryption (Guy Macon)
Re: S-Box evolution (Pelle Evensen)
Re: dictionary attack (Guy Macon)
Re: S-Box evolution (lordcow77)
Re: Commercial Cryptanalysis. (Jim Gillogly)
Re: DES key safety (CLSV)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Timothy M. Metzinger)
Subject: Re: Attacks on a PKI
Date: 19 Dec 1999 20:09:46 GMT
In article <83grhk$623$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(Peter Gutmann) writes:
>That is, without e-commerce as an excuse, PKI vendors will have great
>difficulty in selling their wares to users because there's so little
>demonstrable need for them
Huh?
We look forward to PKI for lots of reasons that have nothing to do with
e-commerce. Just the ability to do away with lots of paper (that we had to keep
with wet signatures) is useful.
Of course PKI can be valuable for strong authentication of individuals too.
Timothy Metzinger
Private Pilot - ASEL - IA!!!! AOPA Project Pilot Mentor
DOD # 1854 '82 Virago 750 - "Siobhan"
Cessnas, Tampicos, Tobagos, and Trinidads at FDK
------------------------------
From: [EMAIL PROTECTED] (Jerry Coffin)
Subject: Re: compression & encryption
Date: Sun, 19 Dec 1999 13:44:02 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
[ ... ]
> Curious. The ability to mechanically reject 65535 out of 65536 keys
> based on decrypting only the first two bytes of a file effectively
> knocks sixteen bits off the key. It pretty much reduces (say) a 64-bit
> keyspace to a 48-bit one.
For this to make any sense at all, you have to start by showing a way
to decrypt the first two bytes of the file, independent of the rest of
the first block. If you can't, your argument is nonsense. If you
can, you've shown that the block cipher is SO weak that it makes
absolutely, positively NO difference what sort of compression or
anything else is in use: if you can treat two bytes separately from
the rest, it's _trivial_ to create a 65536 entry dictionary, and do a
simple lookup to break the cipher in a matter of nanoseconds with even
a relatively out of date computer.
Now if, OTOH, we have something vaguely similar to a decent block
cipher where we have to decrypt the entire first block to get anything
at all, what difference is there? Well, if the first two bytes are
fixed, we can (obviously) determine whether we have a good key by
decrypting only one block. For the moment, let's assume that your
version with no header gives _around_ a 50% compression ratio on
normal text, so a 256-bit block holds and average of 64 characters of
text. For our first attempt at saying whether a decryption is good,
we'll use the incredibly simple criteria that it hold only legal ASCII
characters -- I.e. that the high bit not be set in any byte.
The question is how often we'll accidentally decrypt a block with an
output having no high bits set. The chances of it being set in a
particular byte should be roughly 50%. The chances of accidentally
doing that 64 times in a row are .5^64, or about one in 2^64
(18446744073709551616 according to my calculator).
IOW, with a fixed header, we never have to decrypt a second block to
decide whether a key is good. If we don't have a fixed header, we
expect to decrypt a second block for one out of ever 2^64 blocks we
try. To use your example, that means there's about a 50% chance that
we'd decrypt ONE extra block in searching a 64-bit keyspace (of
course, a cipher with a 64-bit key and a 256-bit block doesn't make a
lot of sense, but we've GOT to restrict the keyspace to something
fairly small or your idea of doing a brute-force search at all simply
becomes too ridiculous to contemplate at all).
I won't work through all the math, but to even get CLOSE to your
65536:1 ratio in speed, we'd have to assume that we nearly always have
to decrypt several blocks of the message before we can guess whether
the content looks reasonable. From what I've seen, that's simply not
realistic at all -- quite the contrary, my expectation would be that
in many cases we'll be able to accept or reject a trial decryption
within the first few of bytes in either case. Yes, you're going to
decrypt a few extra blocks without known plaintext, but you need VERY
low criteria for what looks reasonable before you expect it to happen
even one percent of the time.
I won't try to comment on the rest of your message -- it consisted
almost entirely of expounding upon the ramifications of a 16-bit
reduction in keyspace. The ramifications would only be worth
discussing if the keyspace reduction was real to start with.
--
Later,
Jerry.
The universe is a figment of its own imagination.
------------------------------
From: Glenn Larsson <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Commercial Cryptanalysis.
Date: Sun, 19 Dec 1999 22:27:35 +0100
Hi.
One thing i've noticed over a long time is newbies and others asking for
help, and those who can help won't because they want some sort of
compensation; so - to solve that problem: Isn't it about time that
someone would compile a list on companies/persons who offer
cryptanalytical services to commercial entities?
Suggestion
Name of company: x
Years of cryptanalytic experience: x
Analytic experience: (I.e. which ciphers have been analysed)
Price range: from x to y (or) from x and up
Limitation: (As in "Country X only")
And so on..
If there is such a list, please post an URL..
Regards,
Glenn
------------------------------
From: [EMAIL PROTECTED] (JPeschel)
Subject: Re: dictionary attack
Date: 19 Dec 1999 22:02:12 GMT
[EMAIL PROTECTED] writes:
>In article <83is8s$vho$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>(Michael Velten) wrote:
>>
>>Hi,
>>
>>can anybody tell me, where i can find a good (german)
>>dictionary for a Brute Force-Attack?
>
>While you are at it, I could use a good english brute force
>dictionary. I can get a big list of english words, but a
>proper brute force dictionary would have non-words such as
>"born2run", "xxx", "!@#$%^&*()_+", and "asdfghjkl;'".
>
>This, of course, assumes that the info that I am trying to
>guess is something a human choose so as to be easy to
>remember.
>
Guys, a brute-force attack and a dictionary attack aren't
necessarily the same thing.
Joe
__________________________________________
Joe Peschel
D.O.E. SysWorks
http://members.aol.com/jpeschel/index.htm
__________________________________________
------------------------------
From: Anthony Stephen Szopa <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto
Subject: Re: US Patent Office: How Stupid? Look Here...
Date: Sun, 19 Dec 1999 14:01:01 -0800
Reply-To: [EMAIL PROTECTED]
Jerry Coffin wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> says...
>
> Much like your web site, you seem set to make a lot of emotional
> claims, but provide as little real information as possible. Just for
> example, if you want anybody to make intelligent comments instead of
> just listening to you blow off steam, you NEED to tell us the number
> of the patent you're talking about.
>
> After doing some searching, I'm _guessing_ that you're referring to US
> patent number 5,414,771. I'm not sure of that, but it's about the
> <snip>
>
> Your algorithm offers nothing that isn't already done better by freely
> available algorithms, though I suppose a patent might give you a bit
> more grist for the hype mill (aka web page) describing your product.
>
> --
> Later,
> Jerry.
>
> The universe is a figment of its own imagination.
Thank you for your comments.
You are correct: the patent is 5,414,771. I had included the patent
number in a previous post a couple of days ago.
You have helped me put into greater perspective my situation and
freed me from overly speculating, and attempting to logically come
up with the obvious but not so obvious to the inexperienced.
I did intend to ridicule a bit and certainly went over the top. I
intended to start this thread with a strong rhetorical post.
You have furthered my attempt to focus more fully in detail on my
situation.
And just as you said, I had said in the post that I do expect a
patent to be issued.
Your reply post is quite valuable and I am sure there are many people
out here who have benefited greatly from your considered and
thoughtful and obviously experienced reply relating your own real
world experience with the patent office, and your wisdom.
Thank you.
------------------------------
From: "Matt" <[EMAIL PROTECTED]>
Subject: Re: compression & encryption
Date: Sun, 19 Dec 1999 16:15:28 -0600
> Just for example, many compressors leave a signature at the beginning
> of their output. This is typically around 3 bytes or so,
> substantially smaller than a single block with nearly any reasonably
> recent block cipher of which I'm aware.
>
Why not just add a large random number to the beginning of the file, use CBC
and provide a means to recover the random number for removal a few or more
blocks down?
Matt
------------------------------
From: Peter Pearson <[EMAIL PROTECTED]>
Subject: Re: DES key safety
Date: Sun, 19 Dec 1999 14:37:58 -0800
CLSV wrote:
>
> David Wagner wrote:
>
> > Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>
> > > One question that would be nice to resolve is whether a single
> > > 64-bit block of corresponding plain and ciphertext always
> > > determines a *unique* 56-bit DES key. (It's not obvious.)
>
> I am busy with a similar problem for 128-bit key/block
> block-ciphers. If the cipher is random what is the probability that
> using 2 different keys a plaintext block maps to the same
> crypttext block. This is a sort of advanced birthday problem.
>
[snip]
>
> How about this argument:
> Encryption by DES on the plaintext elements
> 0 1 2 3 ... 2^64-2 2^64-1 can be seen as a permutation on
> those elements. Given one such permutation the size of the largest
> set of encryptions with exactly no element on the same place is
> 2^64 - 1 (i.e. all rotations minus the original one). However,
> having a 56-bit key, DES can at most choose 2^56 of these 2^64-1
> permutations.
[snip]
Note that two DES keys define two permutations of 2^64 blocks.
To the extent that these two permutations are randomly drawn
from the universe of possible permutations, the probability
that no element occupies the same position in both permutations
is extremely close to 1/e. So if we pick two DES keys, K1 and K2,
at random, more often than not there will be a plaintext P
such that DES(K1,P) = DES(K2,P).
------------------------------
From: Glenn Larsson <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: S-Box evolution
Date: Sun, 19 Dec 1999 23:47:24 +0100
Hi.
I was playing around with an S-Box i designed earlier and started
thinking about the concept of having an evolving function in it.
1. Generation
- The (key dependent?) SBox is generated in some manner.
- An IV is extracted from the Key or passphrase.
2. "Evolution"
- For each cryptoblock (or round perhaps), there is a function
(Controlled by the IV) that "evolve" the SBox in some way;
Rotations, Addition, Hashing - just some ideas.
3. Flaw detection
- Perhaps another function that checks for "undesirable
things" - if encountered; go back to step 2.
Any direct ideas? Is the "Flaw detection" feasible? Does it
already exist somewhere? if so, where can i find some info
on that?
Note: I'm not asking you to solve the problem, just to share
your opinions on the matter.
Best regards,
Glenn
------------------------------
From: "Michael Velten" <[EMAIL PROTECTED]>
Subject: Re: dictionary attack
Date: Mon, 20 Dec 1999 00:16:25 +0100
Hi JPeschel,
> Guys, a brute-force attack and a dictionary attack aren't
> necessarily the same thing.
First i'd like to say, that i'm a german. So my english isn't so good! I
know that a brute-force attack isn't the same thing as a dictionary-attack,
but it's a kind of that family!
I hope that anybody understand my (bad) english!
Regards,
Michael
___________________________
Michael Velten
eMail: [EMAIL PROTECTED]
JPeschel <[EMAIL PROTECTED]> schrieb in im Newsbeitrag:
[EMAIL PROTECTED]
> [EMAIL PROTECTED] writes:
>
> >In article <83is8s$vho$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
> >(Michael Velten) wrote:
> >>
> >>Hi,
> >>
> >>can anybody tell me, where i can find a good (german)
> >>dictionary for a Brute Force-Attack?
> >
> >While you are at it, I could use a good english brute force
> >dictionary. I can get a big list of english words, but a
> >proper brute force dictionary would have non-words such as
> >"born2run", "xxx", "!@#$%^&*()_+", and "asdfghjkl;'".
> >
> >This, of course, assumes that the info that I am trying to
> >guess is something a human choose so as to be easy to
> >remember.
> >
>
> Guys, a brute-force attack and a dictionary attack aren't
> necessarily the same thing.
>
> Joe
> __________________________________________
>
> Joe Peschel
> D.O.E. SysWorks
> http://members.aol.com/jpeschel/index.htm
> __________________________________________
>
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: compression & encryption
Date: 19 Dec 1999 19:00:13 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Jerry
Coffin) wrote:
>my expectation would be that in many cases we'll be able
>to accept or reject a trial decryption within the first
>few of bytes in either case. Yes, you're going to
>decrypt a few extra blocks without known plaintext,
>but you need VERY low criteria for what looks reasonable
>before you expect it to happen even one percent of the time.
#$^8`L&2c$@(Q&>+ Is there a way one could exploit this by sticking
random characters somewhere in the plaintext prior to encryption?
In other words, does the trial decryption always try to decrypt
the same place in the plaintext? Maybe at one end? V60Jd@_-m#~6^%@!
------------------------------
From: Pelle Evensen <[EMAIL PROTECTED]>
Subject: Re: S-Box evolution
Date: Mon, 20 Dec 1999 00:56:58 +0100
Glenn Larsson wrote:
> I was playing around with an S-Box i designed earlier and started
> thinking about the concept of having an evolving function in it.
>
> 1. Generation
> - The (key dependent?) SBox is generated in some manner.
> - An IV is extracted from the Key or passphrase.
Define "extracted" in step 1.2?
> 2. "Evolution"
> - For each cryptoblock (or round perhaps), there is a function
> (Controlled by the IV) that "evolve" the SBox in some way;
> Rotations, Addition, Hashing - just some ideas.
Don't use the term of "IV" here since it isn't an IV in the traditional
sense, assuming it's generated solely from step 1.2.
> 3. Flaw detection
> - Perhaps another function that checks for "undesirable
> things" - if encountered; go back to step 2.
"Undesirable things" is a quite wide concept. :)
> Any direct ideas? Is the "Flaw detection" feasible? Does it
> already exist somewhere? if so, where can i find some info
> on that?
Being this vague, the "flaw detection" would have to be done by a human.
This sounds remarkably much like a some kind of stream cipher
with a wide block and possibly a feedback loop. Describe the "S-box" of the
first paragraph?
This is vague enough to almost be similar to "Can a combination of a block
cipher and a stream cipher be secure?" :)
/Pell
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: dictionary attack
Date: 19 Dec 1999 19:05:34 EST
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
(JPeschel) wrote:
>
>[EMAIL PROTECTED] writes:
>
>>In article <83is8s$vho$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
>>(Michael Velten) wrote:
>>>
>>>Hi,
>>>
>>>can anybody tell me, where i can find a good (german)
>>>dictionary for a Brute Force-Attack?
>>
>>While you are at it, I could use a good english brute force
>>dictionary. I can get a big list of english words, but a
>>proper brute force dictionary would have non-words such as
>>"born2run", "xxx", "!@#$%^&*()_+", and "asdfghjkl;'".
>>
>>This, of course, assumes that the info that I am trying to
>>guess is something a human choose so as to be easy to
>>remember.
>
>Guys, a brute-force attack and a dictionary attack aren't
>necessarily the same thing.
I thought I just said that. a dictionary attack is a subset
of a brute force attack, of course. It's also a great thing
to try at the start of a lengthy brute force guessing attack.
This, of course, assumes that the info that I am trying to
guess is something a human choose so as to be easy to
remember. Like most passwords and passphrases are.
------------------------------
From: lordcow77 <[EMAIL PROTECTED]>
Subject: Re: S-Box evolution
Date: Sun, 19 Dec 1999 16:16:33 -0800
Flaw detection isn't unfeasible if the S-box is reasonably large. The
AES candidate MARS has a program for generating and testing 8x32
S-boxes, although it does take quite a long time to find one and there
are some bugs in the code.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Commercial Cryptanalysis.
Date: Mon, 20 Dec 1999 00:27:23 +0000
Glenn Larsson wrote:
> One thing i've noticed over a long time is newbies and others asking for
> help, and those who can help won't because they want some sort of
> compensation; so - to solve that problem: Isn't it about time that
> someone would compile a list on companies/persons who offer
> cryptanalytical services to commercial entities?
So... how much will you pay somebody to compile this list for you? :)
In case you wanted to do the research yourself, I'll help you get
started:
www.accessdata.com
www.crak.com
www.counterpane.com
For noncommercial cracks of commercial packages, try Joe Peschel's pages:
members.aol.com/jpeschel/index.htm
To get "free" analysis by the best non-government cryppies, publish
your algorithm in a refereed journal or conference such as Crypto ##,
Eurocrypt, Asiacrypt, Journal of Cryptology, ... and wait.
To get analysis by hungry cryppies, produce a fair challenge (exposed
algorithm preferably with source code, test data, adequate length of
known plaintext, long enough ciphertext and so on) with a reward large
enough to encourage participation. Another useful kind of challenge is
like the Counterpane flavor: offer a reward for the best analysis,
whether or not it results in a complete break.
And read the FAQ.
--
Jim Gillogly
Mersday, 30 Foreyule S.R. 1999, 00:15
12.19.6.14.8, 10 Lamat 16 Mac, Ninth Lord of Night
------------------------------
From: CLSV <[EMAIL PROTECTED]>
Subject: Re: DES key safety
Date: Mon, 20 Dec 1999 00:31:40 +0000
Peter Pearson wrote:
> CLSV wrote:
> > > Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
> > > > One question that would be nice to resolve is whether a single
> > > > 64-bit block of corresponding plain and ciphertext always
> > > > determines a *unique* 56-bit DES key. (It's not obvious.)
> > How about this argument:
> > Encryption by DES on the plaintext elements
> > 0 1 2 3 ... 2^64-2 2^64-1 can be seen as a permutation on
> > those elements. Given one such permutation the size of the largest
> > set of encryptions with exactly no element on the same place is
> > 2^64 - 1 (i.e. all rotations minus the original one). However,
> > having a 56-bit key, DES can at most choose 2^56 of these 2^64-1
> > permutations.
> Note that two DES keys define two permutations of 2^64 blocks.
> To the extent that these two permutations are randomly drawn
> from the universe of possible permutations, the probability
> that no element occupies the same position in both permutations
> is extremely close to 1/e. So if we pick two DES keys, K1 and K2,
> at random, more often than not there will be a plaintext P
> such that DES(K1,P) = DES(K2,P).
Yes, you are absolutely right for the case of (any) two keys.
However, I wanted to make an approximation for the total key
space of DES: the probability that given a random key there is
no other of the 2^56-1 keys that encrypts a plaintext block
to the same crypttext block. That probability should be
much lower than 1/e. Unfortunately, the counting argument I
gave is not correct if the key space is not equal to the
number of plaintext blocks.
Regards,
CLSV
------------------------------
** 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
******************************
