Cryptography-Digest Digest #795, Volume #11 Wed, 17 May 00 04:13:01 EDT
Contents:
Re: TWO PARTS CRYPTOGRAM ("Douglas A. Gwyn")
Re: Diffie's Randomized Stream Cipher ("Douglas A. Gwyn")
Re: bamburismus ("Douglas A. Gwyn")
Re: Recommend traffic analysis references. (Was: Mixmasters encrypt ("Douglas A.
Gwyn")
Re: Crypto & UNICODE??? ("Douglas A. Gwyn")
Re: Skipjack implementation in C ("Douglas A. Gwyn")
Re: (May 16, 2000) Cipher Contest Update ([EMAIL PROTECTED])
Re: Crypto & UNICODE??? ("Scott Fluhrer")
Re: Fixed the stream cipher "Slime"? ("Scott Fluhrer")
Re: Diffie's Randomized Stream Cipher (Paul Rubin)
Re: Creating a good key-shedule (Runu Knips)
problem solving (Nicolas Riesco)
Re: Crypto & UNICODE??? (Runu Knips)
Re: Key generation (Will Rose)
Re: About Hardware RNG (Guy Macon)
Re: Destructive crypting (Bryan Olson)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: TWO PARTS CRYPTOGRAM
Date: Wed, 17 May 2000 04:21:46 GMT
[EMAIL PROTECTED] wrote:
> YHIHX RVHKK KSKHK IQQEV IFLRK QUZVA EVFYZ RVFBX UKGBP KYVVR
> QTAJK TGBQO ISGHU CWIKX OUXIH DUGIU LMWKG CHXLV WFKIH HEHGB
> EXXSF DMIIL UPSLW AJKTR WTOWP IVXBW NPTGW EKBYV SBQWS
> and
> PNDFF FLFAS LXSGL OEWPV SHDSN HUGYA QAXUG RWIHH LWFXX LXWLD
> MIILV TQPEJ HXKFN AISAX QKIHH VVHAS ISYEW KSJFF LCLVI KDTRR
> HMURQ
> If you are able to decrypt this text; please send me solution
You should not ask this newsgroup to do your homework for you.
The whole point of such an exercise is for you to think hard
about them yourself, in order to learn some lesson that you
will neither understand nor retain if somebody else does the
thinking.
Note that IHH......X..DMIIL appears in both messages (at
positions 93 and 37); that is unlikely to be a mere accident.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Diffie's Randomized Stream Cipher
Date: Wed, 17 May 2000 04:40:27 GMT
Andru Luvisi wrote:
> On page 419 of the 2nd edition of Applied Cryptography, ... "
> you send someone 2^n random bit strings, and then the message
> xored against one of them. The key is an n bit value which
> specifies which one. ... Any attack must examine an expected
> number of bits which is in O(2^n).
So the attacker has to do about as much work as the
transmitter or receiver of the 2^n bit strings.
However, the legitimate receiver knows in advance which
bit string is the useful one, so he doesn't need to
*store* the other 2^n-1 strings, but the attacker does.
(However, if there are a lot of messages sent using this
horribly low effective bandwidth scheme, the attacker
can test smaller subsets, a different one per message.)
> Rueppel points out that if you send n random strings instead
> of 2^n, and if the key is used to specify a linear combination
> of those random strings, the security is the same."
> Am I correct in understanding this to mean that if I use a 128
> bit key, and for every plaintext byte I send 128 random bytes,
> along with the xor of the ones selected by the 1 bits in the key
> and the plaintext byte (129 bytes in total), the result is a 128
> bit cipher against which brute force is guaranteed to be the best
> attack?
No. Consider what can be done with >= 128 bits of known
plaintext.
> Also, does anyone know how important the randomness of the
> random parts is?
All theoretical work based on an assumption of "random bit
streams" depends on their being truly uniformly random.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: bamburismus
Date: Wed, 17 May 2000 04:48:09 GMT
yevaud wrote:
> [ AFAIK the mathematical background of Turing's deciban
> scoring system is not yet available beyond the hints
> dropped by I.J.Good in various articles. If anyone does
> know the details please let me know !!! ]
Apart from the terminology, certain conventions,
and specific examples of its application,
it's just standard log-likelihood-ratio stuff,
which you should be able to find explained
in a good statistics text.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Recommend traffic analysis references. (Was: Mixmasters encrypt
Date: Wed, 17 May 2000 05:07:03 GMT
William Rowden wrote:
> Would someone recommend references that discuss traffic analysis? ...
> I have seen mention of these documents so far:
> (The Zendian Problem)
> * Military Cryptanalytics, Part II, Volume II, Lambros D. Callimahos and
> William F. Friedman
> * Traffic Analysis And The Zendian Problem, Lambros D. Callimahos
The former essentially embeds the latter (which is set in larger type),
and contains about 10 pages of discussion of the subject.
Aegean Park Press also reprinted (C-66) the 1948 "Fundamentals of
Traffic Analysis (Radio-Telegraph)", which contains over 100 pages
of much more detailed discussion of the subject.
In the US National Archives there is a 167-page typewritten
document from 1944, "Basic Traffic Analysis (Circular B-1)",
intended to cover the subject at an introductory level, including
information on Morse, transmitter position location, etc.
Of course, these are all oriented toward military point-to-point
radio (TTY) nets.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Crypto & UNICODE???
Date: Wed, 17 May 2000 05:09:27 GMT
Kenneth Cascio wrote:
> (zeros). Now, he/she knows half of my original message! With this
> information, I would think that a "Known Plaintext Attack" could be
> used in an attempt to decrypt the ciphertext.
Any decent cryptosystem must withstand a known plaintext attack.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Skipjack implementation in C
Date: Wed, 17 May 2000 05:15:36 GMT
"Douglas A. Gwyn" wrote:
> SKIPJACK implementation in Standard C
Oops, sorry! I meant for that to go to the requester,
not the newsgroup. (Darned "user-friendly" newsreader
interface.) However, you're welcome to use it,
just please don't tell me how to "improve" it.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: (May 16, 2000) Cipher Contest Update
Date: Wed, 17 May 2000 05:11:19 GMT
In article <31jU4.40$[EMAIL PROTECTED]>,
"Adam Durana" <[EMAIL PROTECTED]> wrote:
>
> Well the contest has picked up quite considerably. Right now there
are 8
> ciphers in the listing. Since my last update posting, 3 new ciphers
have
> been added. LJA2 by Andru Luvisi, SNAPPY by Tom St Denis, and
BREAKME by
> yours truly. I also updated the web site. I added a new list, which
lists
> the ciphers that have been broken. The cipher I submitted, BREAKME,
should
> be easy to cryptanalyze and that is the reason it was submitted. I
put it
> together in under an hour. It will be interesting to see how long it
takes
> until it is broken. Also if anyone has any programs they have
written to
> help them analyze any of the ciphers and would be willing to share,
send
> them to me and I will post them on the web site.
>
> - Adam
>
>
Adam,
Differential crypto works again. As I am sure you know, this cipher is
vulnerable to classical differential attacks. The sbox has many
examples of different input going to the same output. In a
differential sense S[J]^S[K] = 0. This can be used to break the cipher
with about less than 2^15 plain/cipher texts. Better attacks probably
exist.
I will not post the solution. I will let the newcomers give it a hack
first.
--Matthew
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Crypto & UNICODE???
Date: Tue, 16 May 2000 22:07:30 -0700
Kenneth Cascio <[EMAIL PROTECTED]> wrote in message
news:q0kU4.26017$[EMAIL PROTECTED]...
> ALL:
>
> I have been pondering a crypto issue that I can't grasp. If this is not
an
> issue, I would appreciate an explanation. Thanks in advance! Below is a
> detailed example of my problem:
>
> If I have a plaintext Message "ABCDEFG" (Represented in memory by 7-Bytes
> (HEX): 41, 42, 43, 44, 45, 46, 47) that I want to keep a secret (i.e.
> encrypt) and my application is using standard ASCII character strings (1
> byte per character), than an eavesdropper, unless he has other methods,
can
> not infer anything about my original message from the ciphertext.
>
> On the other hand, if my application is using UNICODE instead of ASCII,
the
> same message "ABCDEFG", now occupies 14-Bytes of memory (UNICODE is a
> multi-byte character) and is represented in memory (on an Intel based
> machine) as: 41, 0, 42, 0, 43, 0, 44, 0, 45, 0, 46, 0, 47, 0. Any
algorithm
> acting on this block of memory (now 14 bytes) will be encrypting the 0s
> which are now part of the message.
>
> The eavesdropper could now infer (if he knows anything about my system)
> parts of the original plaintext message. He/she could assume that the
> original message looked something like this: ?, 0, ?, 0, ?, 0, ?, 0, ?,
0,
> ?, 0. The "?" represents an unknown BYTE and the 0s are the known BYTES
> (zeros). Now, he/she knows half of my original message! With this
> information, I would think that a "Known Plaintext Attack" could be used
in
> an attempt to decrypt the ciphertext.
Well, yes. That is why we don't use ciphers that are known to be vulnerable
to known plaintext attacks. In fact, it is advisable to use ciphers that
are invulnerable to chosen plaintext attacks -- even if the attacker can ask
"what is the encryption of plaintext block 'ZYXWVUTS'", he still is unable
to make heads or tails of it.
And, since there are a number of cryptosystems where there is no publicly
known practical way to attack it even with a chosen plaintext attack, this
is a practical approach.
Examples of such systems are: triple-DES, Blowfish, and any of the AES
finalists.
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Fixed the stream cipher "Slime"?
Date: Tue, 16 May 2000 22:27:23 -0700
Tom St Denis <[EMAIL PROTECTED]> wrote in message
news:8fssfq$jkp$[EMAIL PROTECTED]...
> In article <8fsra4$ibl$[EMAIL PROTECTED]>,
> Tom St Denis <[EMAIL PROTECTED]> wrote:
> > I found if I changed the constant '1' to something with 16 significant
> > bytes (the simplest constant I could find see the paper) I get way
> > better results.
> >
> > The revised paper is at
> > http://www.tomstdenis.com/slime.txt
> >
> > Tom
>
> And of course my test vectors don't match for DJGPP and Turbo C... sure
> why not... it's all byte arithmetic... arrrrrggggg!!!!!!..
>
> Any help....?
Well, one problem I spotted was in slime_expand. You had:
for (y = x - 1; y >= 0; y++)
t = sbox[t ^ key[y]];
You meant:
for (y = x - 1; y >= 0; y--)
t = sbox[t ^ key[y]];
I don't know if that's your problem. BTW: main returns int.
Also, it is "rather quick"??? For a block cipher, it appears slow. For a
stream cipher, it's extremely slow. Eyeballing it, the current
implementation appears to take a minimum 48 cycles per byte: each loop
iteration does the two xors and the sbox lookup, with each calculation
depending on the results of the previous one, so they cannot be overlapped.
--
poncho
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: Diffie's Randomized Stream Cipher
Date: 17 May 2000 06:23:58 GMT
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>> Rueppel points out that if you send n random strings instead
>> of 2^n, and if the key is used to specify a linear combination
>> of those random strings, the security is the same."
>
>> Am I correct in understanding this to mean that if I use a 128
>> bit key, and for every plaintext byte I send 128 random bytes,
>> along with the xor of the ones selected by the 1 bits in the key
>> and the plaintext byte (129 bytes in total), the result is a 128
>> bit cipher against which brute force is guaranteed to be the best
>> attack?
>
>No. Consider what can be done with >= 128 bits of known
>plaintext.
Rueppel's remark doesn't make any sense to me. If the strings are
long enough, it's straightforward to get the key back with much less
than 2^n work, unless I'm missing something. For example, let the
strings be s1, s2, ... where s1[n] denotes bit n of s1. Without
loss of generality assume the known plaintext is all 0. Let M
be the encrypted message = xor of the sk's selected by the key.
Now in about 2^64 operations, find a bit position b1 where
s1[b1]=s2[b1]=s3[b1] = ... = s64[b1] = 0.
Do the same thing another 99 times so you have b1, b2, ... b100,
total work about 100*2^64. That means that for those bit positions,
the message output comes from xoring only the s's from s65, s66, ... s128.
I.e. you can now find the upper 64 bits of the key by brute force search
in another O(2^64) operations with high confidence.
Now find c1, c2, ... c64 so that this time it's s65,...s128 that are 0,
and repeat the brute force search to get the upper 64 bits of the key.
Total work to get the whole key is O(n * 2^(n/2)) where n is the # of bits
in the key. This is much less than 2^n.
It sounds like you have something in mind to do much better than that,
but the above is the first thing I thought of. Is there a better way?
------------------------------
Date: Wed, 17 May 2000 08:36:20 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Creating a good key-shedule
Tom St Denis wrote:
> In article <8fsgvf$76l$[EMAIL PROTECTED]>,
> Simon Johnson <[EMAIL PROTECTED]> wrote:
> > Fair enough, 32-bit enough or would u use a large bits size?
>
> I would say at the very least 48 bits... but I would stick with 64 bits
> as a min, since it's kinda standard.
An old one. The AES candidates have to use 128 bits. I think even
using 256 or 512 bits would be no harm, too. Leaves only the
question what to do with that much data ;-)
------------------------------
Subject: problem solving
From: Nicolas Riesco <[EMAIL PROTECTED]>
Date: Wed, 17 May 2000 02:53:59 -0400
Is there any easy way to solve this kind of equation?
(a*b*GIVENNUMBER)/ (A+B) = OTHERGIVENNUMBER
the thing is that a and b are integers and threr's one solution only
thanks
--
Para responder borra NO_SPAM en mi direccion...
------------------------------
Date: Wed, 17 May 2000 08:49:12 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Crypto & UNICODE???
Kenneth Cascio wrote:
> I'm lost....
If you're using ciphers which can't withstand plaintext attacks you're
truely lost no matter what you do. The attacker ALWAYS can guess SOME
parts of your plaintext. Thats why modern ciphers have to withstand
them !
By the way, one normally doesn't store unicode the way you've described
it. Basically, one sets the msb of the first byte if the character is
larger than 7 bit, saving the rest of the bits in the next character
where again a flag is set if that character is still not enough. This
way every unicode character is stored in 1 to 3 bytes on disk.
------------------------------
From: Will Rose <[EMAIL PROTECTED]>
Subject: Re: Key generation
Date: 17 May 2000 06:56:00 GMT
Eric Lee Green <[EMAIL PROTECTED]> wrote:
: Will Rose wrote:
:> Is there an advantage to using a hash function over eg. a CRC of the
:> passphrase? Both conversions have a 1:1 correspondence between phrase
:> and key; the main problem seems to be that a CRC typically has only
:> 32 bits of output. OTOH, it's cheap to generate.
: 32 bits of output is the problem. That means that the attacker can get in by
: trying only 2^32 possible encryption keys. A teenager with an Apple II could
: have done that in 1982. Meanwhile, a cryptographically strong one-way hash
: like MD5 or SHA1 have the property that it randomly distributes your input
: bits amongst the resulting 128 or 160 bits on the output. Add random bits of
: output_size length in addition to your passphrase, and the output becomes
: effectively random.
I'm not worried about randomness in this context, since that comes out of
the passphrase, but yes, 32 bits is now too small a space.
Thanks - Will
[EMAIL PROTECTED]
------------------------------
From: [EMAIL PROTECTED] (Guy Macon)
Subject: Re: About Hardware RNG
Date: 17 May 2000 03:21:06 EDT
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
>
>Tom St Denis <[EMAIL PROTECTED]> wrote:
>
>>I was wondering (being spoiled as I am) does anyone have a bread-boarded
>>version of
>>
>>http://world.std.com/~wware/hw-rng.html
>>
>>Using either a 18v input or on-board 9v batt supply?
>>
>>That you can spare? I want to try it out, but I don't know how to read
>>the diagram properly (I know the basic symbols....).
>
>Which bit of the diagram are you having trouble with? (This is a tad
>OT so email me if you'd prefer).
>
>FWIW I built a circuit a little while ago that worked on the same
>principle (i.e. sampling noise from a reverse-biased zener).
>
>Some typical results, from a 1024-byte sample (taken one bit at a
>time):
>
>Entropy 7.647 bits / byte
>chi-sq probability 0.01%
>mean 148.17
>serial correlation 0.0173
>
>In short, it's strongly biased, and hence not really random on its
>own; I suspect this is where the lousy chi-square comes from. However,
>there does appear to be good entropy there, so provided it's fed into
>a cryptosecure hash you should get good results (is MD2 up to the
>job?). I'm planning to assume 4 bits per byte of real entropy to allow
>for the limited predictability the circuit gives.
>
>A couple of implementation issues to bear in mind:
>
>1. If your +ve rail has significant ripple then this is coupled into
>the noise generator and turns it into a 50Hz oscillator (assuming 50Hz
>ripple). 9V battery should be OK, mains-powered "battery eliminator"
>will need to go through a good regulator first. Since the circuit
>state will be osciallating rapidly, your battery life may be much
>shorter than you might think.
>
>2. put a small capacitor as close as you can get to the power-supply
>pins of the logic chip. ALS may be more forgiving, but certainly AC
>logic tends to dump charge pulses onto its rails when it switches.
How does the circuit determine the threshhold to compare the noise to
in order to decide whether to call the current bit a 1 or a 0? Is this
a logic input, comparator, op-amp, Transistor (FET or bipolar?) or what?
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Destructive crypting
Date: Wed, 17 May 2000 07:44:01 GMT
Daniel wrote:
>
> Hi ppl,
>
> I need to know of a good (worldwide accepted) one-way crypt
> algorithm
[...]
> (I will use it to send a password over tcp/ip)
Based on other strands of the thread, I gather that
you are doing remote log-in with a password. The
best techniques known use "key amplification"
protocols which combine a small shared-secret with
public-key math. Given only a small shared secret,
they stand up to attackers who can both spoof
both sides and complete exhaustive search of the
secret-space.
Techniques include EKE, SPEKE and SRP. See
http://srp.stanford.edu/srp/
or
http://www.integritysciences.com/speke.html
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
