Cryptography-Digest Digest #941, Volume #8 Thu, 21 Jan 99 06:13:03 EST
Contents:
On the null trail, Part III (wtshaw)
Re: long numbers math - how to ? (Mike Johnston)
Re: Metaphysics Of Randomness (Joseph H Allen)
Re: Turing Machines For Sale (Steve Roberts)
Beale Cipher - FreeWare Software! (jgore)
Cayley
Re: Word List Utilities ("donoli")
Re: Dumb Question: Relationship between RSA and Factoring ("Sam Simpson")
Seemingly secure family of scaleable large block ciphers (WHu9539962)
Re: 3DES cracked in 22 hours ??? (Was: Re: (fwd) DES Challenge III Broken in Record
22 Hours !) ("Sam Simpson")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: On the null trail, Part III
Date: Wed, 20 Jan 1999 23:08:48 -0600
First, there was Rimfire 8/12/16/24, base 100 to base 22.
Then, there was Balsas 10/20, base 100 to base 18.
Now, the next in the series is Ping 6/12/18/24, base 100 to base 16.
As before there are two keys, substitution and transposition, the
substitution key be a deranged sequence of 16 letters drawn from the
alphabet, and the null pool being the other 10. The transposition key is
a deranged sequence of the first 6/12/18/24 letters of the alphabet. THF
keying? Of course.
Ping is a river in Thailand, runs generally north to south, and is close
to 100 E 16 N.
One of many problems in making these few programs is that with each step
the mathematics requires more precision. Rimfire was only 4 digits,
Balsas was 5, and Ping is 6. The next one will take 8. I tried with Ping
to make more generic functions for the key structure, so it should help
with the next step downwards.
--
The devil is always in the details.
------------------------------
From: [EMAIL PROTECTED] (Mike Johnston)
Subject: Re: long numbers math - how to ?
Date: Tue, 19 Jan 1999 17:32:26 GMT
Reply-To: [EMAIL PROTECTED]
check out
http://www.spektracom.de/~arndt/fxt/
Mike J
------------------------------
From: [EMAIL PROTECTED] (Joseph H Allen)
Subject: Re: Metaphysics Of Randomness
Date: Thu, 21 Jan 1999 04:45:03 GMT
In article <[EMAIL PROTECTED]>,
R. Knauer <[EMAIL PROTECTED]> wrote:
>This discussion has raged on for as long as I have been on sci.crypt,
>which is off and on for over a year. We had a huge discussion
>involving many participants from different fields which resulted in
>over 1,000 posts by one person's count.
:-) :-)
This very same discussion is a permanent topic in comp.compression as well,
where at least three times a year somebody claims that they can compress
random data (even though it is trivially proven that it is impossible to do
so). The discussion almost alway ends in deadlock when the poster refuses
to believe the trivial proof, also refuses to post his magical new
algorithm for fear of others stealing it, but is eagerly awaiting investment
money to market his algorithm. Always the poster is paranoid.
Anyway, the discussion usually hinges on "random" being a heavily overloaded
word. It can have several meanings depending on your point of view:
- the mathematical definition: a random process where each of the possible
events is equally probable, I.E., impossible to compress with any method.
- the mathematical definition: a process which is still random, but the
events may or may not be equally probable, I.E., it may be worthwhile to
use arithmetic or Huffman coding to effeciently transmit the
non-equiprobable symbols.
- the mathematical definition: a process which is still random, but the
data may or may not be correlated in some way, I.E., there may be
repeating patters which can be compressed with statistical modeling or
dictionary methods.
- the information theory definition: data which you don't posses (I.E., if
you could predict the data, you'd already have it). This is useful for
the quantum mechanics metaphysics thing. You can't really tell the
difference between a real random process and God's One Time Pad. As long
as you can't see the One Time Pad, the data might as well come from a
random process. The real question is whether God reuses His One Time Pad
because it turned out to be too short for His Experiment and could we ever
hope to detect and exploit this in some way.
- the data is random. I.E., 111010011011001011000100001 seems like a more
random piece of data than 101010101010 or 000000000000. this casual
definition causes most of the problems, since most people would assert
that the previous statement is true. They are not necessarily wrong: they
just have a different definition for "random". This definition goes
something like: "random" data is any data where I can't guess the right
half of it, after seeing the left half of it. So any of these are
non-random: 3.14.... 1010.... 1234.... When in the course of human
events.....
This leads to the common dictionary compression algorithms (when the left
side contains hints about the right side), but it also leads to an another
interesting algorithm: Use all of the data on your hard drive as a
dictionary, and come up with a small hash value for every 1K block. Now
when you download a new software package (or anything) from the net, send
its hash values plus any 1K blocks you don't have hash values for. Now
this is not guaranteed to correctly download the data, but the probabity
of it doing so can be made arbitrarily high, and it will probably save
money on your long distance bill (especially if you are stealing MS-Office
and already have one componant of it like, MS-Word).
Inevitably the "Kolmogorov-complexity" card is played... now I don't what
this term means exactly, but in the compression realm it indicates that the
poster doesn't understand that although simple algorithms like LFSRs and the
like can make lots of very "random appearing" data, this fact is useless
when it comes to making good compression algorithms (unless your data
frequently is the output of LFSRs).
Always remember that you will not win the nobel prize for mathematics (were
there one) if you use the file size word part of the directory entry to
store part of the data.
--
/* [EMAIL PROTECTED] (192.74.137.5) */ /* Joseph H. Allen */
int a[1817];main(z,p,q,r){for(p=80;q+p-80;p-=2*a[p])for(z=9;z--;)q=3&(r=time(0)
+r*57)/7,q=q?q-1?q-2?1-p%79?-1:0:p%79-77?1:0:p<1659?79:0:p>158?-79:0,q?!a[p+q*2
]?a[p+=a[p+=q]=q]=q:0:0;for(;q++-1817;)printf(q%79?"%c":"%c\n"," #"[!a[q-1]]);}
------------------------------
From: [EMAIL PROTECTED] (Steve Roberts)
Subject: Re: Turing Machines For Sale
Date: Thu, 21 Jan 1999 06:43:36 GMT
"J. Staphros" <[EMAIL PROTECTED]> wrote:
>I have built a small number of Turing Machines in my garage and now I am
>ready to sell the first production run. They come with either paper tape
>or magnetic tape operation. The prices are $2,000 and $1,800 US dollars,
>respectively. They are guaranteed to halt.
If they are guaranteed to halt on any problem then this is good
value!! I want one ... no, I want an infinite number of them.
------------------------------
From: [EMAIL PROTECTED] (jgore)
Subject: Beale Cipher - FreeWare Software!
Date: Thu, 21 Jan 1999 06:10:07 GMT
I have written a program called Beale Cypher Magic which
encodes and decodes Beale Ciphers. It will do True Beale Ciphers
or Advanced Beale Ciphers which can reproduce your text exactly
the way you wrote it! It has many options and will let you
configure the cipher exactly how you want it!
It's FreeWare! - No registration or anything!
For Win 95/98/2000.
My URL is:
http://members.tripod.com/~j_gore/
I hope you add a link to my Page. Thanks! ........Jerry
------------------------------
From: [EMAIL PROTECTED] ()
Subject: Cayley
Date: 21 Jan 99 07:18:45 GMT
Recently, there has been interest in a news item concerning a young woman
from Ireland who developed a new public-key algorithm, called the
Cayley-Purser algorithm.
(I note that I seem to have misread the description of the Rabin algorithm
in AC: when I looked at it again, it did seem to require high
exponentiations to decipher.)
Anyways, I remembered something about the name Cayley and the number eight
which may, or may not, be relevant.
Matrices, like numbers, can be added, subtracted, and multiplied. However,
not all nonzero matrices are invertible, which is the equivalent of
finding the reciprocal of a number. However, there are mathematical
constructs involving more than one number that always have reciprocals if
they are not zero, and these are called numbers as well.
Complex numbers are an example. The quaternions, invented by William Rowan
Hamilton (of Ireland!) are another - but unlike real and complex numbers,
quaternion multiplication is not commutative. The invention of quaternions
caused quite a stir, and another mathematician developed octonions;
however, these were forgotten.
The logical next step after quaternions, therefore, had to use a different
name - octaves - when it was developed...by Cayley. An octave has eight
components, one real and seven imaginary.
The multiplication table for octaves is as follows:
Second number
* | 1 i j k L p q r
----------------------------
F 1 | 1 i j k L p q r
i i | i -1 k -j p -L -r q
r j | j -k -1 i q r -L -p
s k | k j -i -1 r -q p -L
t L | L -p -q -r -1 i j k
p | p L -r q -i -1 -k j
n q | q r L -p -j k -1 -i
o r | r -q p L -k -j i -1
and this may, or may not, as I have said, have some connection with the
Cayley-Purser algorithm.
John Savard
------------------------------
From: "donoli" <[EMAIL PROTECTED]>
Crossposted-To: alt.2600,alt.hacking,comp.security.misc,comp.security
Subject: Re: Word List Utilities
Date: Thu, 21 Jan 1999 02:36:37 -0000
Myself wrote in message <[EMAIL PROTECTED]>...
>I've changed the groups this was crossposted to, I think they're more
>appropriate. The original thread was about sorting dictionaries for
>crack, but in this reply I raise what I think is an interesting point
>about the vulnerabilities of assigned "random" passwords.
>
>On Wed, 13 Jan 1999 02:36:08 -0000, "donoli" <[EMAIL PROTECTED]>
>wrote:
>>I have a program called dict.zip It won't do anything w/ your files but
>>you can make any size word file you want. Just watch how big you make the
>>file. It took me three days to realize why I had only 2% of a 3 gig HD
>
>Err, well that's not going to do you much good. Sure it'll make a big
>list of random characters but any program can do that. The reason we
>use dictionaries instead of just randomly or systematically checking
>every combination, is that people are more likely to use words as
>passwords (hence the term passWORDs) and there are a lot fewer words
>than there are random combinations.
>
>I've heard of programs that'll parse all the text on your hard drive
>(or the drive of a system you've "acquired") and build a dictionary
>containing all the words it finds. (The beginning of many a search
>engine, no doubt!) This strikes me as very useful, especially if the
>user's personal works (saved email, work files, perhaps even web
>cache) are on the drive, as it'll contain words that they specifically
>are interested in, which might not appear in other dictionaries.
>
>What would be REALLY effective, is a list of the passwords that people
>have FOUND in passwd files, or in other password repositories
>(unencrypted files perhaps.. insecure non-unix systems are great for
>this, or through BO password dumping).. Has anyone ever compiled a
>list like this? It'd be particularly useful on a college campus,
>something like this....
>
>Let's say that the university systems are fairly secure.. Shadowed,
>the root users are never drunk, etc.. And just to make things
>interesting, let's say the university has an assigned-password policy
>that generates a random-gibberish password and assigns it.
>Plain-english passwords are not allowed. So even if someone DID get a
>list from this place, cracking it would be hell. (Actually if I'm
>right, this might be their biggest mistake. Read on.)
>
>First vulnerability, common to all systems:
>
>Now let's say that elsewhere in this college town is a web cafe. The
>connections are useless because every dorm room has a 10baseT jack in
>it, except for one group of students: The ones that don't have
>computers in their rooms. (Read: the computer-stupid ones). These
>students, while they're sucking down caffeine, are likely to create
>their web cafe IDs with the same login names and passwords that they
>use on the secure system. Here's your hole. Break the cafe. It's not
>hard, lots of them use a "security system" which is basically an MS
>Access database with a front end that only lets you start certain
>programs and keeps track of your time used/remaining.
>
>I don't want to give a recipe for this, but let's just say with a
>little creative exploration of the cafe's net mounted drives, you
>might find said database, plaintext. Get that critter and put it
>somewhere you can retrieve it later. (A floppy in your pocket works to
>a point, but it's damning evidence if you get caught.) Sending it to a
>pseudonymous shell somewhere is much better.
>
>When you get home, open that file and dump the interesting fields as
>ASCII into another file, and load THAT into your cracker. Try it on
>some of the passwd files you've found from the university. I betcha
>dollars to double-lattes, that a handful of morons recycled their
>passwords. And I bet the cafe user "doenut" has the same password as
>the university acount "jdoe".. so even if you don't have a passwd file
>to crack, a little optical parsing and some sophisticated wetware
>algorithms will lend a couple of user/pass matches between the
>systems.
>
>So here's a security tip! Don't use the same password on more than one
>system. If one's compromised, your accounts on the others are too.
>
>Second vulnerability, only applies to assigned-password systems:
>
>For the code-heads out there.. Does anyone know anything about the
>PRNG's (Pseudo-Random Number Generators, for the uninitiated
>(unseeded?) among us) that the gibberish-password generators use? My
>logic is this:
>
>If the server which assigns you a password is using its
>seconds-since-boot timer as a seed for the PRNG, and if most passwords
>are generated at the beginning of the schoolyear right after the
>system's been screwed with by the admins, then it's probably undergone
>a few reboots in the last couple weeks and the timer value is likely
>to be relatively low, at least in the first few million seconds. Valid
>so far? And if the code isn't done too well, then it re-seeds the PRNG
>every time the password maker is invoked, instead of saving its state
>for next time.
>
>So get ahold of the code they use to make random numbers into
>passwords, and run it in a loop.. Generate one entry in your
>dictionary file for each possible value of timer since startup.. Let
>it run for about 2 weeks' worth of seconds. Then sic your cracker on
>the passwd armed with the dictionary and let 'er rip.
>
>Is it just me, or is this too simple?
>
>-Myself-
>.nosig
I agree that a dictionary maker won't help if people are just picking words
as passwds although when someone signs up w/ my ISP the passwds are server
generated using a combination of letters and #s, not just english words.
AT&T does the same thing. When you pick a passwd w/ AT&T it's only good for
your e-mail. Otherwise it's a 13 digit combo using all chars. As for
universities, someone here once said, you'd be surprised how many students
use beer as a passwd. Donoli.
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: Dumb Question: Relationship between RSA and Factoring
Date: Thu, 21 Jan 1999 08:58:16 -0000
>From a quick glance of the paper it appears that it discusses key not
message recovery - thus you could possibly get an RSA key without factoring.
Dean Povey wrote in message <784bc7$j1k$[EMAIL PROTECTED]>...
>"Sam Simpson" <[EMAIL PROTECTED]> writes:
>
>>Further to this response, you may wish to look at the paper:
>
>>D.Boneh, R.Venkatesan, "Breaking RSA may not be equivalent to factoring",
>>Eurocrypt '98, Lecture Notes in Computer Science, Vol. 1233,
>>Springer-Verlag, 1998.
>
>>Which provides evidence that certain instances of RSA cannot be equivalent
>>to the IFP. This is contrary to the belief by some that RSA and IFP are
>>equivalent.
>
>Thanks for the reference.
>
>I actually wasn't asking whether breaking RSA was equivalent to factoring,
>merely whether _recovery of the private key_ is equivalent to factoring.
>I am aware that there may be other methods of obtaining plaintext from
>ciphertext which may not be equivalent to factoring. But I am just
>interested in recovering the private key.
>
>Hope that helps.
>--
>Dean Povey, | e-m: [EMAIL PROTECTED] | Cryptozilla:
>Research Scientist | ph: +61 7 3864 5120 | www.cryptozilla.org/
>Security Unit, DSTC | fax: +61 7 3864 1282 | Oscar - PKI Toolkit:
>Brisbane, Australia | www: security.dstc.edu.au/ | oscar.dstc.qut.edu.au/
------------------------------
From: [EMAIL PROTECTED] (WHu9539962)
Subject: Seemingly secure family of scaleable large block ciphers
Date: 21 Jan 1999 07:34:17 GMT
I recently had an idea as to how to make scaleable ciphers using
small-size block ciphers such as DES.
The technique is to use a small, fixed-size block cipher as an S-box
for a larger block cipher. For example, to produce a block cipher of
size 256 bits using DES one can adopt the following procedure:
Encrypt bits 0-63 using subkey A.
Encrypt bits 64-127 using subkey B.
Exclusive-or encrypted bits 0-127 with bits 128-255 to produce
encrypted bits 128-255.
Repeat with subkeys C and D to yield a 256 bit block cipher with a 224
bit key.
Note that, in this context, a subkey is 56 bits long.
If you want a block with key and plaintext the same length, using an
S-box such as DES where the key is shorter than the plaintext, the
best way, using the DES as an example, is to make an LCM(64,56) = 448
bit block cipher and add an extra stage of encipherment with another
56 bits of subkey so that key, plaintext and ciphertext are all 448
bits long, making a convenient building block.
This technique just mirrors the internals of the DES, using the DES
itself as an S-box. Its beauty is that such ciphers are very easily
decodable, given the key and the S-box, by running the procedure in
reverse - the bits output by a particular stage are easily obtainable
from the bits output by the following stage, given its subkey.
One can then produce larger blocks by using, for example, the 448 bit
building block itself as an S-box, and so on. I call this technique
concatenation.
Thus one can produce a block cipher with arbitrarily large blocks,
using this method, where plaintext, key and ciphertext are all the
same length, or, by generating a larger key from a smaller key by any
appropriate means, such as using a block cipher of key size equal to
that of the smaller key with exclusive-or feedback from output to
input as a pseudo-random bit sequence generator, the bit sequence
being the key to the large block cipher, one can have large block
ciphers with shorter keys than block size.
The natural procedure is to build a block cipher of smallest size
greater than or equal to plaintext size, by the above described
technique of concatenation and then one uses whatever size key is needed
for the degree of security required.
The above described technique seems a useful way of building
relatively secure ciphers even with the DES, thus enabling the use of
such things as DES chips.
Comments and suggestions would be welcome.
A. Hunger
A. Hunger ([EMAIL PROTECTED]) - Buses are bosons.
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Subject: Re: 3DES cracked in 22 hours ??? (Was: Re: (fwd) DES Challenge III Broken in
Record 22 Hours !)
Date: Thu, 21 Jan 1999 10:14:46 -0000
Assuming 3DES has an effective keylength of 112-bits then it would take
around 329293306 years on average to break a single key.
This figure is based on the peak keys per second figure (250 Billion) quoted
in the EFF/RSA press release.
Cheers,
Sam Simpson
Comms Analyst
-- http://www.hertreg.ac.uk/ss/ for ScramDisk hard-drive encryption & Delphi
Crypto Components. PGP Keys available at the same site.
Gary Cowell (QI'HoS) wrote in message
<[EMAIL PROTECTED]>...
>Said Mok-Kong Shen <[EMAIL PROTECTED]>
>
>>RSA Code-Breaking Contest Again Won by Distributed.Net and
>>Electronic Frontier Foundation (EFF)
>>
>> DES Challenge III Broken in Record 22 Hours
>
>When I first heard the news about this, someone said Des three has
>been cracked in 22 hours.....
>
>I took this to mean 3DES or tripple des had been cracked in 22 hours
>which is patently not the case.
>
>Needless to say I was somewhat sceptical of the initial report :-)
>
>Any extrapolations on how long it would take to crack 3DES at the same
>key rate as was used during DES challenge III ?
>
>
------------------------------
** 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
******************************
