Cryptography-Digest Digest #770, Volume #10 Sun, 19 Dec 99 23:13:01 EST
Contents:
Re: question (Johnny Bravo)
Re: dictionary attack (Riky Oleman)
Re: dictionary attack (Matthew Montchalin)
Code Puzzle ([EMAIL PROTECTED])
Re: S-Box evolution (David Wagner)
Re: random numbers straight out of MS BASIC (Raddatz Peter)
Re: S-Box evolution (Tim Tyler)
Re: compression & encryption (Tim Tyler)
Re: Code Puzzle (Arthur Dardia)
Re: compression & encryption (Tim Tyler)
Re: Code Puzzle (Arthur Dardia)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Johnny Bravo)
Subject: Re: question
Date: Sun, 19 Dec 1999 20:16:38 GMT
On Sat, 18 Dec 1999 19:21:25 GMT, amadeus @DELETE_THIS.netcomuk.co.uk
(Jim) wrote:
>On Sat, 18 Dec 1999 17:01:50 -0000, "Gary" <[EMAIL PROTECTED]> wrote:
>
>>Chaff and winnowing proposed by Rivest is one example.
>>In fact there are also alot of relatively new public key systems that have
>>expansion.
>
>By a factor of 2 or 3 ?
By as much as you want. It works like this: both parties share a
secret key. The sender takes the secret information he wants to send
and chops it up into small pieces, then computes a checksum on each
piece plus the secret key. So the checksum only computes correctly
when you include the secret key in the computation.
Then, the sender sends these chunks (with checksums) along with a
lot of bogus randomly-generated chunks with bogus randomly-generated
checksums, which are referred to as "chaff". The receiver can sort out
which chunks are real and which are "chaff" by validating the
checksums with their secret key! Anyone intercepting the information
stream will not be able to determine which chunks are real and which
are chaff, and therefore cannot reproduce the secret message.
see http://theory.lcs.mit.edu/~rivest/chaffing.txt for the original
paper.
The interesting implication of this is that the resulting process is
not encryption. The message chunks are not encrypted, just
authenticated. This method would seem not be export-controlled since
the message chunks are sent in the clear and numbered in order.
Breaking the message into single bits would seem to make the job of
the attacker trying to reassemble the message hopeless given that for
each bit sent, the complementary bit with a random authentication is
sent as well, but that is not the senders problem. :)
Best Wishes,
Johnny Bravo
------------------------------
From: [EMAIL PROTECTED] (Riky Oleman)
Subject: Re: dictionary attack
Date: Mon, 20 Dec 1999 01:21:13 GMT
[EMAIL PROTECTED] (Guy Macon) wrote:
>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.
If you operate a system that has lots of users who are required to enter
passwords then you could automatically compile a list of the commonly
chosen ones, but it sure doesn't sound like a very ethical thing to do.
Aside from that, I don't know where such a list could come from.
--
"Riky Oleman" is actually [EMAIL PROTECTED] (7126 983540).
0123 456789 <- Use this key to decode my email address and name.
Play Five by Five Poker at http://www.5X5poker.com.
------------------------------
From: Matthew Montchalin <[EMAIL PROTECTED]>
Subject: Re: dictionary attack
Date: Sun, 19 Dec 1999 17:37:27 -0800
On Sun, 19 Dec 1999, Michael Velten wrote:
| Hi,
|
| can anybody tell me, where i can find a good (german) dictionary for a
| Brute Force-Attack?
I think the folks at Wordperfect may have a few thesaurus files from which
you could extract or construct a German dictionary...
And speaking of which, that is something I'd like to get my hands on.
------------------------------
From: [EMAIL PROTECTED]
Subject: Code Puzzle
Date: Mon, 20 Dec 1999 01:45:40 GMT
Hi everyone!
Here is a code puzzle that so far has not
been solved. It is one sentence and punctuation
is ignored. Here it is!
82 44 22 67 83 11 35 93 52 11 51 64 71 45 15 31
94 51 66 32 58 93 83 15 52 77 94 21 47 96 34 22
71 56 22 63 82 48 23 31 85 73 16 39 72 15 11 55
47 96 34 22 71 51 26 91 95 12 16 92 91 19 12 35
71 54 33 23 11 96 31 31 73 82 91 33 79 82 34 52
81 78 52 75 31 27 72 93 95 22 57 92 93 79 22 59
17 96 35 11 73 51 27 93 96 15 35 37 87 18 54 71
54 14 33 92 76 71 16 67 95 71 37 39 95 46 11 93
82 44 29 57 44 71 91 13 15 56 23 35 71 14 55 94
66 35 17 54 13 91 71 72 26 39 85 17 58 87 91 18
46 84 51 47 17 58 48 96 66 21 47 77 33 33 72 52
27 38 95 71 37 51 46 82 33 24 59 31 85 14 53 87
38 33 13 84 53 44 16 66 77 15 57 85 35 11 71 94
98 51 83 11 33 91 94 15 27 92 51 27 42 93 65
I hope someone can help! Thanks!
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: S-Box evolution
Date: 19 Dec 1999 18:42:38 -0800
In article <[EMAIL PROTECTED]>,
lordcow77 <[EMAIL PROTECTED]> wrote:
> 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.
Can you say anything more about the bugs in the MARS S-box testing code?
Any details, descriptions of the buggy cases, etc. would be very interesting.
Thanks!
------------------------------
From: Raddatz Peter <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: random numbers straight out of MS BASIC
Date: Sun, 19 Dec 1999 18:44:45 -0800
Scott Nelson wrote:
>
> On Sat, 18 Dec 1999 Raddatz Peter <[EMAIL PROTECTED]> wrote:
>
> >I keep reading about how weak and predictable the built in RNG from MS
> >is, so I did some testing. The MS RNG has a repeat series of approx.
> >256^3 or 16777215.
>
> Mine doesn't. Either there's a flaw in your testing,
> in my testing or we have different versions.
> Which MS RNG version are you talking about?
>
> >If I create 10 sboxes with 1000 rnd numbers betw. 0 and 256 based on 2,
> >rather large, seeds (> 111111111111111 & < 999999999999999)
>
> That's not reasonable as described.
>
> Could you describe that step in a little more detail?
> How are you using those large seeds?
> Where are the random numbers coming from?
> How does the MS RNG fit into all this?
>
> Scott Nelson <[EMAIL PROTECTED]>
I'm petty sure that MS does not use the whole 15 digits as its seed, I'm
pretty sure that there's a MOD in there somewhere. All I'm trying to
achieve is to have the seed a little larger than TIMER. The point that
I'm trying to explore is... the numbers generated are betw. 0 and 255
inclusive the only thing that is "random" is the order in which they
occurr. 201 15 39 118... or 117 28 93 247 or whatever, it is the order
of 10, 100 or a 1000 "randomly" arranged numbers within a certain range
that is of importance here. If the array that holds these numbers is
only 256 cells and holds 256 values and every value can only occurr once
then the possibilities are extremely limited. In a larger array, though,
where any number could occurr numerous times in any given location poses
a slightly higher challenge. The large seed I use simply determines the
order of the numbers not the size.
I fail to see where numbers within the range of 0 - 255 arranged
"randomly" by the MS algo are inferior to those 0 - 255 arranged by a
different algo. But then... what do I know.
Peter Rabbit
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: S-Box evolution
Reply-To: [EMAIL PROTECTED]
Date: Mon, 20 Dec 1999 02:48:48 GMT
Glenn Larsson <[EMAIL PROTECTED]> 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.
Key-dependent S-Boxes are your friend.
: 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.
You seem to be talking about "evolution" in the sense of "change over
time".
Doing things dynamically with your s-boxes /may/ mean too much work
at runtime - given the set of constraints s-boxes usually have to
operate under.
/Perhaps/ cycling through a predetermined list would be enough for
whatever security benefits you're trying to obtain.
: 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?
There's a significant (and complex) literature on the constraints which
apply to s-box design - and to "bent" boolean functions in general.
A few such pages:
http://www.iicm.edu/jucs_1_2/the_relationship_between_propagation/html/paper.html
http://www.cs.uow.edu.au/people/grc01/jennie/lifework.html
AFAICS, most such constraints apply to individual s-boxes. I believe it
/should/ be possible to lift some of the constraints on the s-boxes
themselves if other constraints on their arrangement were employed.
I don't know if people have tried doing this - so this is just idle
speculation on my part - but I would welcome any information about this.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Small change can often be found under seat cushions.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: compression & encryption
Reply-To: [EMAIL PROTECTED]
Date: Mon, 20 Dec 1999 03:25:07 GMT
Jerry Coffin <[EMAIL PROTECTED]> wrote:
: 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.
I hope I don't have to do that. Getting the first two bytes will usually
involve decrypting the first block.
: 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, you have 2 bytes of known plaintext in every message sent using the
system - compared to potentially none at all.
: Well, if the first two bytes are fixed, we can (obviously) determine
: whether we have a good key by decrypting only one block. [...]
: 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).
*If* you have an uncompressed plain text file - and know that it has no
top set bits, then you also have a very similar known-plaintext attack
to the one I was describing against the 2-byte compressed header.
You're comparing two systems with /roughly/ equivalent security problems.
I would have thought you should be comparing 1-1 compression with non 1-1
compression if you're drying to draw any conclusions about its utility.
We already know failing to compress text files gives the analyst a
bundle of interesting statistics to target his attack with.
: 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).
FWIW, I don't recall mentioning a 256-bit block size. That's a lot larger
than is used in many circumstances.
Brute force of the whole keyspace is only what needs to be used if there
is no other known attack on the block cypher. If you're /seriously/
trying to read the messages, it would be useful to have some other sort
of attack as well, to reduce the effective keyspace further.
: 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.
Well, you're still comparing a poor compression scheme to the /awful/
technique of not compressing at all. Use a reasonable compressor that
effectively diffuses information over a significant region of the
file, and you may find you need to decrypt and decompress more blocks
before you can think about plaintext frequency analysis. The difference
in the work factor can also depend on how big your blocks are.
The keyspace reduction I mentioned won't generally translate directly
into improved cracking speed - but depending on the sizes of the
messages, and how much work is needed to reject keys without the
known-plaintext, large speed improvements can be on the cards.
The message need not be text. It could be fairly short. There may be
only a few bits of plaintext known. If this is the case, a 2-byte header
could make the difference between a near certain idintification of the
file, and a hopless problem, with large numbers of possible solutions.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
The cigarette does the smoking - you're just the sucker.
------------------------------
From: Arthur Dardia <[EMAIL PROTECTED]>
Subject: Re: Code Puzzle
Date: Sun, 19 Dec 1999 22:34:28 -0500
The way it looks, each two-digit number stands for a letter. Taking the
mod 26 of each number doesn't result in a message, so I'm thinking that
maybe it's a substitution cipher based on the mod 26 of the two-digit
numbers. I'm too lazy to try it though. :)
[EMAIL PROTECTED] wrote:
> Hi everyone!
> Here is a code puzzle that so far has not
> been solved. It is one sentence and punctuation
> is ignored. Here it is!
>
> 82 44 22 67 83 11 35 93 52 11 51 64 71 45 15 31
> 94 51 66 32 58 93 83 15 52 77 94 21 47 96 34 22
> 71 56 22 63 82 48 23 31 85 73 16 39 72 15 11 55
> 47 96 34 22 71 51 26 91 95 12 16 92 91 19 12 35
> 71 54 33 23 11 96 31 31 73 82 91 33 79 82 34 52
> 81 78 52 75 31 27 72 93 95 22 57 92 93 79 22 59
> 17 96 35 11 73 51 27 93 96 15 35 37 87 18 54 71
> 54 14 33 92 76 71 16 67 95 71 37 39 95 46 11 93
> 82 44 29 57 44 71 91 13 15 56 23 35 71 14 55 94
> 66 35 17 54 13 91 71 72 26 39 85 17 58 87 91 18
> 46 84 51 47 17 58 48 96 66 21 47 77 33 33 72 52
> 27 38 95 71 37 51 46 82 33 24 59 31 85 14 53 87
> 38 33 13 84 53 44 16 66 77 15 57 85 35 11 71 94
> 98 51 83 11 33 91 94 15 27 92 51 27 42 93 65
>
> I hope someone can help! Thanks!
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
--
Arthur Dardia Wayne Hills High School [EMAIL PROTECTED]
PGP 6.5.1 Public Key http://www.webspan.net/~ahdiii/ahdiii.asc
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: compression & encryption
Reply-To: [EMAIL PROTECTED]
Date: Mon, 20 Dec 1999 03:46:36 GMT
lordcow77 <[EMAIL PROTECTED]> wrote:
: In article <[EMAIL PROTECTED]>, Tim Tyler <[EMAIL PROTECTED]> wrote:
:> lordcow77 <[EMAIL PROTECTED]> wrote:
:> : Pray tell, but how would one decrypt just the first two bytes
:> : from a single block encrypted with a block cipher? You can't, and
:> : that's why your "mechanically reject" comment is just wrong.
:> Simple: pick a key to be tested and decrypt the first block. [...]
:> Placing mathematical constraints on the keys that can be valid by
:> using this technique is likely to be more useful to an analyst than
:> *actually* decrypting and rejecting individual keys.
: Exactly. You still have to decrypt the entire first block. The time
: complexity of breaking the cipher by brute force remains asymtopically
: the same. [...]
This will be no consolation to the sender - if it takes the analyst a day
to break a message that would normally take him a year.
I /presume/ the "asymptote" you are talking about is something to do with
the way the work factor required changes as the keyspace increases.
Given that the method I mentioned is - at best - a reduction of the
keyspace by as many bits as are added by the compressor, it's hardly
suprising that the "order" of the search is itself unchanged.
Consider that the attacker only has to deal with a single block - and he
can reject keys independent of the message contents or the message length,
without applying frequency analysis to the results - or even bothering to
decompress any of it.
Don't forget that compressed files should decompress to files with
convincing-looking source statistics - if the compressor is any good -
so the halting criteria for the brute-force search may be much harder
than it would normally be.
I'd have though the benefits of avoiding this problem were clear enough
- yet I seem to wind up repeating them again and again in this forum.
: The analyst does have to "*actually*" decrypt the test block using
: individual keys.
Sort of. The ideal would be to use this to find some mathematical
constraints that are a way of representing the keyspace reduction,
produced by the known-plaintext, to reduce the search time further.
For example, you may be able to determine that a key is wrong while the
block cypher is still half way through its operation and has not yet
reached the final rounds. This sort of thing can speed up the operarion
of the search when compared with an ordinary decryption operation.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Some things have to be believed to be seen.
------------------------------
From: Arthur Dardia <[EMAIL PROTECTED]>
Subject: Re: Code Puzzle
Date: Sun, 19 Dec 1999 22:55:55 -0500
Okay, I wrote a quick program to take in the numbers and than print the
letter of the alphabet that it's modulus corrosponded too. For instance: 82
44 are the first two numbers. The Mod 26 of each of these numbers are 4 and
18. The 5th and 19th letters of the alphabet are e and s. In case anyone
wants to tinker with my attempt, here's my data:
the numbers mod 26 turned into letters a=0, z=25:
eswpfljpalzmttpfqzoggpfpazqvvsiwtewlewxfhvqnupldvsiwtzanrmqontmjtchxlsffvenhbeia
daaxfbuprwfopbwhrsjlvzbpspjljsctcohoytqprtlnrulpesdfstnnpexjtodqojrcnntuanhrgjns
ugzvrgwsovvzhhuabmrtlzuehyhfhobjmhngbsqozpfhjltquzflhnqpbozbqpn
running vcrack on this resulted in:
ervwslstl{lsapsrooffwsptydvwrnbtptyevya}vdm`pmeqfibwoaosjdo{wxjubomlfesvdoowe|b
e`fmfwvervghebbkgskmqobepejmktvtvl}oxuverao{rtmwpsqeftoowpxwzdpnmgc{mau`ooggmf
t`ovgdbsnwqoh}vtblssyz`f}yigozbn}nfctdoosshkmsduoeyhopwwooadpo
It obviously didn't work. :) Oh well. Quick 5 minute attempt.
Arthur Dardia wrote:
> The way it looks, each two-digit number stands for a letter. Taking the
> mod 26 of each number doesn't result in a message, so I'm thinking that
> maybe it's a substitution cipher based on the mod 26 of the two-digit
> numbers. I'm too lazy to try it though. :)
>
> [EMAIL PROTECTED] wrote:
>
> > Hi everyone!
> > Here is a code puzzle that so far has not
> > been solved. It is one sentence and punctuation
> > is ignored. Here it is!
> >
> > 82 44 22 67 83 11 35 93 52 11 51 64 71 45 15 31
> > 94 51 66 32 58 93 83 15 52 77 94 21 47 96 34 22
> > 71 56 22 63 82 48 23 31 85 73 16 39 72 15 11 55
> > 47 96 34 22 71 51 26 91 95 12 16 92 91 19 12 35
> > 71 54 33 23 11 96 31 31 73 82 91 33 79 82 34 52
> > 81 78 52 75 31 27 72 93 95 22 57 92 93 79 22 59
> > 17 96 35 11 73 51 27 93 96 15 35 37 87 18 54 71
> > 54 14 33 92 76 71 16 67 95 71 37 39 95 46 11 93
> > 82 44 29 57 44 71 91 13 15 56 23 35 71 14 55 94
> > 66 35 17 54 13 91 71 72 26 39 85 17 58 87 91 18
> > 46 84 51 47 17 58 48 96 66 21 47 77 33 33 72 52
> > 27 38 95 71 37 51 46 82 33 24 59 31 85 14 53 87
> > 38 33 13 84 53 44 16 66 77 15 57 85 35 11 71 94
> > 98 51 83 11 33 91 94 15 27 92 51 27 42 93 65
> >
> > I hope someone can help! Thanks!
> >
> > Sent via Deja.com http://www.deja.com/
> > Before you buy.
>
> --
> Arthur Dardia Wayne Hills High School [EMAIL PROTECTED]
> PGP 6.5.1 Public Key http://www.webspan.net/~ahdiii/ahdiii.asc
--
Arthur Dardia Wayne Hills High School [EMAIL PROTECTED]
PGP 6.5.1 Public Key http://www.webspan.net/~ahdiii/ahdiii.asc
------------------------------
** 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
******************************
