Cryptography-Digest Digest #280, Volume #12 Mon, 24 Jul 00 12:13:01 EDT
Contents:
Re: random malar-key (Mike Rosing)
Re: Rabin's information dispersal algorithm (Mike Rosing)
Re: Random Appearance (Paul Koning)
Re: Proving continued possession of a file (Rķkharšur Egilsson)
Re: Hash function? (Boris Kazak)
Re: Random Appearance ("Tony T. Warnock")
Re: Proving continued possession of a file (Mark Wooding)
books by W. F Friedman (Charles Blair)
Re: New stream cipher ("Trevor L. Jackson, III")
Re: Practical application of Ciphersaber (Was: RC4-- repetition length?) ("Trevor L.
Jackson, III")
Re: Hash function? (Sander Vesik)
Re: Hash function? ("Scott Fluhrer")
Re: Practical application of Ciphersaber ("Scott Fluhrer")
----------------------------------------------------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: random malar-key
Date: Mon, 24 Jul 2000 08:18:46 -0500
Abyssmal_Unit_#3 wrote:
>
> don't worry, it only takes power away (can u spare it?) , & it doesn't (shouldn't)
>introduce any unwanted abberations of thoughts.
> heee ! ;-))
>
> ok, maybe try hooking up like an ECG instead? how about an aura detector? ;-D
EEG's would work fine. You just have to sample at > 10 kHz and integrate for
at least 1000 samples. the result (modulo your sample bit width) will be
random.
It's stuff like this that got me into crypto in the first place. About 15 or
so years ago I built an EEG digitizer. (I also was pumping signals into my
head, but it worked, so I stopped :-) What I wanted to do was ship EEG signals
around, mostly for gaming and music purposes, but I could see lots of other
applications. A direct link to my thoughts is something worth protecting,
and I think strong crypto is required.
I gave up on EEG's, but crypto is still fun!
Patience, persistence, truth,
Dr. mike
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Rabin's information dispersal algorithm
Date: Mon, 24 Jul 2000 08:34:48 -0500
Wei Dai wrote:
> IDA is a method of producing k pieces from a message such that any n of
> them can be used to recover the message. If the message length is m,
> then each piece has size m/n, and it takes O(m*k) operations to
> generate the pieces and O(m*n) operations to recover the message. The
> new method improves the run-time to O(m+m*(k-n)) operations to generate
> the pieces and O(m+n^2+m*r) operations to recover the message, where r
> is the number of pieces among the first n pieces that are missing.
> The new method treats the message as the values of a degree n-1
> polynomial evaluated at points 0,...,n-1. The first n pieces are
> produced simply by cutting the message into n equal sized chunks. The
> other k-n pieces are produced by interpolating the polynomial at k-n
> other points. Recovery involves interpolating the values of the
> polynomial at only the missing points. The coefficients of the
> polynomial is never explicitly determined.
I assume you mean the coefficients are not determined during recovery,
but they must be known during generation. How does one know which
points are "missing" if you don't know the coefficients?
Patience, persistence, truth,
Dr. mike
------------------------------
From: Paul Koning <[EMAIL PROTECTED]>
Subject: Re: Random Appearance
Date: Mon, 24 Jul 2000 10:00:43 -0400
Mack wrote:
>
> >Joseph Ashwood wrote:
> >> That's not correct. OTP's are subject to known-plaintext
> >> attacks, ...
> >
> >No, they are not, since the only plaintext that is "recovered"
> >is exactly the plaintext that was already known. The point
> >being that "One-Time Pad" in such a context means the
> >theoretically secure system, not a potentially flawed
> >attempt at implementation of such a system.
> >
> >
>
> The code book systems to which I was refering are exactly
> the same as OTP's. The pad may be reused at the risk of
> a known plaintext attack. The words for messages are
> compiled into a list each word has a different meaning.
> These pads are usually only a couple of pages and then
> compiled into a book. Different 'chapters' are used depending
> on some information. This system was used during WW2
> if I am not mistaken. Each 'chapter' is an OTP. If a chapter is
> reused it is subject to known-plaintext attack . Of course if the
> OTP is stolen it is also broken. In actual use pads were used
> for a certain time period.
Clearly if they were used "for a certain time period" they
were nothing at all like OTP.
Your description sounds thoroughly muddled. Can you point
to a reference that supports the "one time" notion of
these "code books"? I find it hard to believe considering
the work involved in creating codes by hand.
What does sound familiar is code books of widely varying
sizes (from one page tactical codes to quite large code
books). And of course all of these would be reissued
from time to time. That cycle might be days or years.
But in no way would that make it at all similar to OTP.
paul
--
!-----------------------------------------------------------------------
! Paul Koning, NI1D, D-20853
! Lucent Corporation, 50 Nagog Park, Acton, MA 01720, USA
! phone: +1 978 263 0060 ext 115, fax: +1 978 263 8386
! email: [EMAIL PROTECTED]
! Pgp: 27 81 A9 73 A6 0B B3 BE 18 A3 BF DD 1A 59 51 75
!-----------------------------------------------------------------------
! "A system of licensing and registration is the perfect device to deny
! gun ownership to the bourgeoisie."
! -- Vladimir Ilyich Lenin
------------------------------
From: [EMAIL PROTECTED] (Rķkharšur Egilsson)
Subject: Re: Proving continued possession of a file
Date: 24 Jul 2000 13:57:59 GMT
Reply-To: [EMAIL PROTECTED]
On 23 Jul 2000 13:46:19 GMT, Mark Wooding <[EMAIL PROTECTED]> wrote:
>
>And finally, can anyone think of more sensible protocols which have
>similar properties but save Bob from having to do all of that
>computation?
Solution #1
The server computes 2 cryptographically strong numbers A and B such that
both A and B are < size_of_M, and A < B
The server then sends A and B to Bob and asks him to compute md5(M')
where M' is the data from M starting at A and ending at B.
When Bob has calculated md5(M'), the server does the same, compares
the two values and act accordingly.
M' only has to be a few K from anywhere within M, the
calculation md5(M') can take a split second.
Solution #2
The server computes 1 cryptographically strong number A and asks Bob to send
him M' where M' is made of 8 bytes of M starting at location A.
The server then compares what he has, with whatever BOB sends him.
But this is so simple that I have the feeling I missed something ...
--
RIKHARDUR EGILSSON - Why pay for drugs when you can get Linux for free ?
echo '[q]sa[ln0=aln80~Psnlbx]16isb15CB32EF3AF9C0E5D7272C3AF4F2snlbxq'|dc
This is by-design behavior, not a security vulnerability.
Scott Culp of Microsoft Public Relations (CNET 5/5/00)
------------------------------
From: Boris Kazak <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Hash function?
Date: Mon, 24 Jul 2000 14:24:54 GMT
Scott Fluhrer wrote:
>
****************
> > Any feedback will be appreciated.
*********************
> According to my calculations, with 128 bit Kazakhash [1] using the default
> array initialization (no user-provided key), and including the optional
> length hashing, the following two files:
>
> 00 00 00 00 00 00 00 00 00 00 01 00 00 00 00 00
> 01 6a 0a 36 f9 a0 db c0 01 71 f9 e5 f8 f8 4d 0d
>
> have the common hash value:
>
> 9c 60 63 b9 53 4b 4f 16 ed ac 98 41 90 f4 49 4c
>
> I found these two files by looking for input streams whose input
> differential (after the first byte, whose input differential I didn't bother
> worrying about) is restricted to buffer[0], buffer[1], buffer[2] -- that is,
> I choose the input streams so that buffer[0] immediately before the rotate
> had a zero differential.
>
> Further comments:
>
> - The length hashing is optional??? That really doesn't make sense; it
> should be either required or forbidden.
>
> - And, if you are going to hash in a length, putting in a limit of
> 4Gigabytes is somewhat restrictive for applications with huge files -- a 64
> bit length field is less restrictive.
>
> - The "final squashing" is both unneeded and dangerous. It's unneeded
> because the requirement on a hash function is to make forgery (either
> finding preimages, or finding colliding messages) difficult, and this step
> does nothing to make it any more difficult [2]. It's dangerous because the
> operation is noninvertable, and so may generate additional collisions.
>
> [1] I had to call it something...
>
> [2] Ok, it does appear to make finding a file that files to a given value
> more difficult, but that isn't a very common attack.
>
> --
> poncho
=======================
Sorry, this attack does not work (probably your implementation deviates
from
description in some aspect).
The reasons are:
1) First bytes have a nonzero difference. They are immediately
rotated
to the tail of the array and stay there, different, waiting for their
turn to come back to the head and participate in multiplication.
2) Before being rotated to the tail, these different bytes were each
of them part of 16-bit numbers multiplied with SEED. This produced
different products, which were XORed byte by byte into buffer[0],
buffer[1], buffer[2], buffer[3]. Thus there are already 3 bytes
affected by the input difference, so even if you choose a byte that will
make up for the difference in buffer[0] (after rotate), the
existing difference will show up when you will concatenate buffer[0]
and buffer[1] to make a new multiplier. As a result, 3 more bytes to the
right will be affected, and this difference will persist in the buffer.
3) I am going to introduce printf() into my implementation and
illustrare what happens in course of your attack, with all intermediate
buffer contents, multiplicands, products, etc. This will take me an
evening or two.
4) Thank you for naming the algorithm.
Best wishes BNK
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: Random Appearance
Date: Mon, 24 Jul 2000 08:31:13 -0600
Reply-To: [EMAIL PROTECTED]
Mack wrote:
> >Joseph Ashwood wrote:
> >> That's not correct. OTP's are subject to known-plaintext
> >> attacks, ...
> >
> >No, they are not, since the only plaintext that is "recovered"
> >is exactly the plaintext that was already known. The point
> >being that "One-Time Pad" in such a context means the
> >theoretically secure system, not a potentially flawed
> >attempt at implementation of such a system.
> >
> >
>
> The code book systems to which I was refering are exactly
> the same as OTP's. The pad may be reused at the risk of
> a known plaintext attack. The words for messages are
> compiled into a list each word has a different meaning.
> These pads are usually only a couple of pages and then
> compiled into a book. Different 'chapters' are used depending
> on some information. This system was used during WW2
> if I am not mistaken. Each 'chapter' is an OTP. If a chapter is
> reused it is subject to known-plaintext attack . Of course if the
> OTP is stolen it is also broken. In actual use pads were used
> for a certain time period.
No. One time is 1.00000000000 time. Any reuse means you are not using a
one-time-pad.
1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1=1
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Proving continued possession of a file
Date: 24 Jul 2000 14:34:23 GMT
Rķkharšur Egilsson <[EMAIL PROTECTED]> wrote:
> But this is so simple that I have the feeling I missed something ...
Yes. That's my fault. I wasn't clear enough in my problem description.
The server doesn't keep the file in fast storage (it's on a tape or
semething), there are lots of putative Bobs, and she'll want to run this
protocol lots of times.
-- [mdw]
------------------------------
Subject: books by W. F Friedman
From: [EMAIL PROTECTED] (Charles Blair)
Date: Mon, 24 Jul 2000 14:44:58 GMT
I've gotten a catalogue from Aegan Park Press, including several
books by Friedman. These include 4 volumes called ``Military Cryptanalysis''
and another series ``Military Cryptanalytics,'' by Friedman and
Callimahos.
Could somebody familiar with these comment on the amount of overlap,
and also whether more recent works (e.g., the ``Decrypted Secrets''
book by Bauer) contain equivalent material?
------------------------------
Date: Mon, 24 Jul 2000 10:46:27 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: New stream cipher
[EMAIL PROTECTED] wrote:
> <[EMAIL PROTECTED]> wrote in message
> news:8l6v3n$je5$[EMAIL PROTECTED]...
> > AOTP-Alex One Time Pad stream cipher.
> >
> > Performance of this implementation is 190 Mb/sec.
> > It was measured sending 256 byte in loop 777215 times.
> > Some random comments:
>
> > - Unless you want to be labeled as a Klewless Newbie(tm), I recommend
> that
> > you don't call it a "One Time Pad stream cipher". It's not a One
> Time Pad,
> > and at least here on this newsgroup, calling something a "One Time
> Pad" when
> > it's not is a definite sign of snake oil.
>
> I choose 'One Time Pad' only for the sake of joke:-)
> Right call may be 'Quasi One Time Pad'.
No.
The right call is "Repeating Pad". There is no meaningful "oneness" about
your system, so "quasi one" is inaccurate.
Note that systems like yours are considered to be stream ciphers, so people
will understand you better if you use that term. If you _don't_ want people
to understand you, then invent a term of your own such as "<adjective> Time
Pad".
But I do not recommend the latter approach here. It will only engender
disrespect.
------------------------------
Date: Mon, 24 Jul 2000 11:05:17 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Practical application of Ciphersaber (Was: RC4-- repetition length?)
Scott Fluhrer wrote:
> Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote in message
> news:[EMAIL PROTECTED]...
> [Re: Guy Malcom's method of marking messages within a long random stream by
> using a fixed 64 bit marker symbol]
> > Your special code may be a problem. I'd recommend using each only once.
> Question: why? What potential weaknesses are you worried about?
My concern is that the proposed system provides a quantity of known text. If
the prefix is outside the cipher envelope, then it's frequency will stand out
and thus reduce the value of the background noise by making it easy to
distinguish messages from noise. If the prefix is inside the cipher envelope,
it provides the basis for a known plaintext attack within each message.
Note that on such a point-to-point link external behavior may expose the
approximate message boundaries. For example, if the system's traffic were
intermittent flurries, an observer would be able to predict that a region of
high message density would accompany the observable change in state/ or
behavior of the recipient.
N.B., if the system's traffic were continuous rather than intermittent then the
value of the noise filler is small.
------------------------------
From: Sander Vesik <[EMAIL PROTECTED]>
Subject: Re: Hash function?
Date: 24 Jul 2000 15:45:05 GMT
Boris Kazak <[EMAIL PROTECTED]> wrote:
[snip]
> Sorry, this attack does not work (probably your implementation deviates
> from
> description in some aspect).
Why don't you just post the code somewhere on the web and send in an URL?
[snip]
> Best wishes BNK
--
Sander
FLW: "I can banish that demon"
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Hash function?
Date: Mon, 24 Jul 2000 08:39:18 -0700
Boris Kazak <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Scott Fluhrer wrote:
> >
> ****************
> > > Any feedback will be appreciated.
> *********************
> > According to my calculations, with 128 bit Kazakhash [1] using the
default
> > array initialization (no user-provided key), and including the optional
> > length hashing, the following two files:
> >
> > 00 00 00 00 00 00 00 00 00 00 01 00 00 00 00 00
> > 01 6a 0a 36 f9 a0 db c0 01 71 f9 e5 f8 f8 4d 0d
> >
> > have the common hash value:
> >
> > 9c 60 63 b9 53 4b 4f 16 ed ac 98 41 90 f4 49 4c
> >
> > I found these two files by looking for input streams whose input
> > differential (after the first byte, whose input differential I didn't
bother
> > worrying about) is restricted to buffer[0], buffer[1], buffer[2] -- that
is,
> > I choose the input streams so that buffer[0] immediately before the
rotate
> > had a zero differential.
> >
> > Further comments:
> >
> > - The length hashing is optional??? That really doesn't make sense; it
> > should be either required or forbidden.
> >
> > - And, if you are going to hash in a length, putting in a limit of
> > 4Gigabytes is somewhat restrictive for applications with huge files -- a
64
> > bit length field is less restrictive.
> >
> > - The "final squashing" is both unneeded and dangerous. It's unneeded
> > because the requirement on a hash function is to make forgery (either
> > finding preimages, or finding colliding messages) difficult, and this
step
> > does nothing to make it any more difficult [2]. It's dangerous because
the
> > operation is noninvertable, and so may generate additional collisions.
> >
> > [1] I had to call it something...
> >
> > [2] Ok, it does appear to make finding a file that files to a given
value
> > more difficult, but that isn't a very common attack.
> >
> > --
> > poncho
> -----------------------
> Sorry, this attack does not work (probably your implementation deviates
> from
> description in some aspect).
I found a bug in my code that printed out the colliding messages -- they
were both 61749 bytes long, my print routine only printed the first 16
bytes.
Also, could you publish a reference implementation? Preferably in C? I
went through your description again, and my implementation looks like it
does exactly that. One ambiguity I did notice wasn that, when you "split
_product_ into 4 bytes from prod[0] to prod[3]", you didn't specify how to
do this. I assumed you used bigendian ordering, that is prod[0] is the most
significant byte -- you used bigendian ordering everywhere else.
If you assume little-endian ordering there, I found a pair of colliding
messages 132742 bytes long. If you are using little-endian ordering, I'll
send them to you.
And, once I have the word on what the ordering is, I'll see if I can find a
shorter pair of colliding messages.
>
> The reasons are:
> 1) First bytes have a nonzero difference. They are immediately
> rotated
> to the tail of the array and stay there, different, waiting for their
> turn to come back to the head and participate in multiplication.
> 2) Before being rotated to the tail, these different bytes were each
> of them part of 16-bit numbers multiplied with SEED. This produced
> different products, which were XORed byte by byte into buffer[0],
> buffer[1], buffer[2], buffer[3]. Thus there are already 3 bytes
> affected by the input difference, so even if you choose a byte that will
> make up for the difference in buffer[0] (after rotate), the
> existing difference will show up when you will concatenate buffer[0]
> and buffer[1] to make a new multiplier. As a result, 3 more bytes to the
> right will be affected, and this difference will persist in the buffer.
You misunderstood my approach: I chose a byte that makes up for the
difference in buffer[0] before the rotate, and so that buffer[15] always has
zero differential (after the first byte, where I didn't bother tracking the
differential). Since buffer[15] always has zero differential (after the
first step), buffer[3] through buffer[14] always has zero differential after
startup.
And, I'm not trying to explicitly make the difference not persist -- I'm
keeping it localized, and hoping it acts like a random function on 24 bits.
If you print out the internal buffers, you should see that, after all 16
bytes, that buffer[3] through buffer[15] was a zero differential -- if it
doesn't, the approach is wrong (or I took the wrong ambiguity mentioned
above).
> 3) I am going to introduce printf() into my implementation and
> illustrare what happens in course of your attack, with all intermediate
> buffer contents, multiplicands, products, etc. This will take me an
> evening or two.
> 4) Thank you for naming the algorithm.
Seemed appropriate...
--
poncho
------------------------------
From: "Scott Fluhrer" <[EMAIL PROTECTED]>
Subject: Re: Practical application of Ciphersaber
Date: Mon, 24 Jul 2000 08:42:01 -0700
Guy Macon <[EMAIL PROTECTED]> wrote in message
news:8lgu7u$[EMAIL PROTECTED]...
> Scott Fluhrer wrote:
>
> >Trevor L. Jackson, III <[EMAIL PROTECTED]> wrote in message
> >news:[EMAIL PROTECTED]...
> >[Re: Guy Macon's method of marking messages within a long random stream
by
> >using a fixed 64 bit marker symbol]
> >> Your special code may be a problem. I'd recommend using each only
once.
> >Question: why? What potential weaknesses are you worried about?
>
> I was worried about the special code showing up as the output of the
> RNG.
Oops, the question wasn't for you, it was for Trevor. I wasn't questioning
the need for such a code, I was questioning Trevor's claim that reusing the
code was dangerous.
--
poncho
------------------------------
** 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
******************************
