Cryptography-Digest Digest #154, Volume #14 Sun, 15 Apr 01 17:13:00 EDT
Contents:
Re: Reusing A One Time Pad ("Mark G Wolf")
Re: NSA is funding stegano detection (Walter Roberson)
Re: Reusing A One Time Pad ("Tom St Denis")
Re: LFSR Security ("Trevor L. Jackson, III")
Re: Reusing A One Time Pad ("Mark G Wolf")
Re: LFSR Security ("Trevor L. Jackson, III")
Re: Remark on multiplication mod 2^n (Mok-Kong Shen)
Re: Reusing A One Time Pad ("Mark G Wolf")
Re: C Encryption ("Trevor L. Jackson, III")
Re: Advantages of attackers and defenders ("AY")
Re: LFSR Security (Graywane)
Re: Reusing A One Time Pad ("Tom St Denis")
Re: Reusing A One Time Pad ("Tom St Denis")
Re: Password tool! ("Logan Raarup")
Re: Reusing A One Time Pad ("Mark G Wolf")
Re: Reusing A One Time Pad ("Mark G Wolf")
Why Not OTP ? (Frank Gerlach)
----------------------------------------------------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Sun, 15 Apr 2001 15:26:06 -0500
> If no bit position within the pad is used to encrypt more than one
message,
> it's secure (in the information theoritical sense).
>
> If you ever reuse a single bit position within the pad, it's not secure
(in
> theory, and usually in practice as well).
I understand that. And let me take a moment to say that practicality often
gets lost in theory. Even if I was absolutely sure of that one bit, it
wouldn't really do me much good even for a 7-bit ASCII four letter word.
Let me give another example. Let's say I encoded "EAT AT JOES" with pieces
of my one time pad 10 times, and once out of those ten times I reused the
same bits to encode the first "E". One "E" is not very useful, assuming you
can even tell it's part of my message. Remember you don't have my one time
pad.
------------------------------
From: [EMAIL PROTECTED] (Walter Roberson)
Crossposted-To: comp.security.misc,talk.politics.crypto
Subject: Re: NSA is funding stegano detection
Date: 15 Apr 2001 20:34:10 GMT
In article <[EMAIL PROTECTED]>,
<[EMAIL PROTECTED]> wrote:
:I'd have thought that detection of otherwise well constructed
:steganography would be based on statistical analysis of the degree of
:entropy or randomness in the data. Any unencrypted image, or other
:file, intended to convey information is by definition not random.
On the other hand, the data may be compressed. Compression works
by reducing redundancy, so the compressed data is "more random".
Any compression algorithm that leaves statistically-detectable
correlation in its file, could theoretically be improved [but improving
the algorithm might be difficult as a practical matter.]
: So
:GIFs, JPEGs etc are not random. It would be perfectly feasible to
:analyze a huge quantity of such files (ones without hidden messages)
:to establish their statistical properties - in particular the degree
:of randomness.
Not really. "Degree of randomness" has no objective meaning. There
is only "degree of randomness compared to a particular model." And
there isn't just *one* model for GIFs, JPEGs etc.; there is an
indefinite series of models depending on subject matter, equipment
and so on.
:Then one could focus on statistical comparisons of
:files being sent by others with a view to establishing whether there
:is any probability that the degree of randomness is more or less than
:expected.
Yes, but by the time you account statistically for all of those
different models, the statistical measure is going to have to be
very loose -- unable to detect anything but the most obvious
hidden information.
:On this basis, I suspect that those using steganography in pictures
:should:
:1) use messages that are small relative to the container
:2) send images containing messages infrequently
:3) send lots of images which contain no messages
Alternately, have *every* image contain a message, but make it very
difficult to tell which messages are spurious. Perhaps even use
a multi-level code in which the "outer" message was relatively
innocuous and explicable/deniable. For example you could even give
them full source to the image encoding algorithm... source that just happens
to have a "bug" that picks up an "uninitialized" block of memory
(whose contents you very subtly prime if you have something to send.)
And so on.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Sun, 15 Apr 2001 20:34:11 GMT
"Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
news:9bd06m$6o6o$[EMAIL PROTECTED]...
> > If no bit position within the pad is used to encrypt more than one
> message,
> > it's secure (in the information theoritical sense).
> >
> > If you ever reuse a single bit position within the pad, it's not secure
> (in
> > theory, and usually in practice as well).
>
> I understand that. And let me take a moment to say that practicality
often
> gets lost in theory. Even if I was absolutely sure of that one bit, it
> wouldn't really do me much good even for a 7-bit ASCII four letter word.
>
> Let me give another example. Let's say I encoded "EAT AT JOES" with
pieces
> of my one time pad 10 times, and once out of those ten times I reused the
> same bits to encode the first "E". One "E" is not very useful, assuming
you
> can even tell it's part of my message. Remember you don't have my one
time
> pad.
How about using real terminology... it's not a "one time pad" if it's used
more than once....... do you understand that much so far?
Second re-using keystream has been tried before (Maurer....) and is often
broken easily... Reason, chosen plaintexts or known plaintexts can be very
damaging... You can't reuse the bits and still claim it's secure
Tom
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Crossposted-To: sci.crypt.random-numbers
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 20:38:31 GMT
David Wagner wrote:
> Trevor L. Jackson, III wrote:
> >David Wagner wrote:
> >> I haven't see any evidence either way
> >> (short of "well, I can't see how to do it" -- which isn't very convincing).
> >
> >There is more to it that that. Consider the collections of unknowns: the taps,
> >the gap positions, the gap values, and the initial state.
>
> As I suggested before, the gap positions seem likely to be known in all
> scenarios that matter. So, your argument doesn't apply.
>
> My question is: Given known keystream at some known but irregular
> positions, is there a general algorithm to find the taps and initial fill?
With N unknown you just use Berlekamp-Massey. The invariant in BM is that one
always has the smallest configuration that explains the sequence up to the current
bit. By continuing this process through the gaps, assigning each unknown bit the
subsequent output of the current machine, one can maintain the invariant and
preserve the validity of the result.
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Sun, 15 Apr 2001 15:39:02 -0500
> Let's alias the pad (0, 1) = (a, b)
>
> I could reuse the pad like aaaabbbbbababab or ababababababba or .....
OK so the message is either aa, ab, ba, or bb.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 20:44:33 GMT
Graywane wrote:
> While we are on the subject, would the following be a suitable technique to
> generate "random" data for a true OTP:
>
> 1. Seed an RC4 from /dev/random on a Unix machine.
> 2. Use RC4 to provide the 624 words of state for each of 13 different
> Mersenne Twisters (mt19937)
> 3. Get a number X between 100 and 1000 from RC4.
> 4. For each of the MT's (until X bytes is output):
> A. Get a number between 1 and 1000 (from RC4).
> B. Skip that number of outputs from the MT.
> C. Output the next value.
> D. Go to next MT and repeat at step A.
> 5. Get the SHA hash of the bytes generated in step 4.
> 6. For every byte in SHA hash, flip a coin (using RC4) and output
> the byte if the coin is heads.
> 7. Goto step 3 and repeat until desired number of bytes is output.
>
> If you then took the data and burned it to a CD, would it make a descent
> OTP? (assuming you never used the same data twice and destroyed the CD when
> you were through)
I think not. Your example assumes that /dev/random is a reasonable source of
unpredictability. The best use of the source is not a convoluted set of
transforms that impose their own pattern on the keystream, but a simple entropy
still to /i/n/s/u/r/e/ give hope that the keystream has very high entropy.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Remark on multiplication mod 2^n
Date: Sun, 15 Apr 2001 22:41:15 +0200
David Wagner wrote:
>
> Mark Wooding wrote:
> >Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> >> If one has two n-bit entities a and b, then one can obtain
> >> from them a nonlinear combination a*b mod 2^n. [...]
> >> A trivial and ad hoc remedy that suggests itself seems to be to do
> >> first a full multiplication, obtaining c*2^n + d and define the result
> >> to be either c + d mod 2^n or c xor d.
> >
> >I think this isn't a good idea. It stops the combiner from being
> >invertable.
>
> Yes, and if one sets f(a,b) := c + d mod 2^n where c*2^n + d = a*b,
> then one has the interesting consequence that
> f(a,b) = a * b mod 2^n - 1
> holds with probability almost 1. Whether this allows attacks is
> likely to depend on the cipher, but it doesn't look like a good
> property to me.
>
> For instance, if the rest of the cipher contains only additions,
> then the whole cipher might have low degree over the ring Z/(2^n - 1)Z;
> or, if 2^n - 1 has a small divisor d, then the differential
> da = (2^n -1)/d, db = 0 ensures that f(a+da,b+db) - f(a,b) = 0
> with good probability.
As may be evident from the original post, the scheme
is sort of quick-and-dirty. It intends to capture some
of the entropy in the operands that gets lost due to
the normal modular multiplication, without aiming to do
that very well (cheap in cost is the goal). I have
mentioned simultaneously the use of rotation of the
operands, which should alleviate the problem you pointed
out to certain extent, though this involves some additional
processing. As to invertibility, it was not intended.
The scheme is just a rather simple (almost trivial) and
cheap means of combining two pseudo-random sequences in
a non-linear manner, nothing more.
M. K. Shen
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Sun, 15 Apr 2001 15:46:42 -0500
> Second re-using keystream has been tried before (Maurer....) and is often
Good for Maurer.
> broken easily... Reason, chosen plaintexts or known plaintexts can be
very
> damaging... You can't reuse the bits and still claim it's secure
I wasn't claiming anything. I asked a question.
------------------------------
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: C Encryption
Date: Sun, 15 Apr 2001 20:48:31 GMT
Logan Raarup wrote:
> Anyone know how to encrypt a string in C?
Sure. The way to learn how is to ask in comp.lang.c.
------------------------------
From: "AY" <[EMAIL PROTECTED]>
Subject: Re: Advantages of attackers and defenders
Date: Sun, 15 Apr 2001 21:58:40 +0100
quoting from the crypto-gram:
> The ability to react quickly to an attack, and intimate
> knowledge of the terrain: these are the advantages the position of the
> interior brings. A good general knows how to take advantage of them, and
> they're what we need to leverage effectively for computer security.
Somehow I don't think a "war" is a good analogy to network security. In a
physical war, either side can win by eliminating the enemy, or at least
that's the theory. In a network environment, one can only "not lose" but
cannot "win" as such.
It might also be the case that the cracker doesn't have a fixed target, he
just goes around and attack the vulnerable network that he happens to come
across. This is also where the "war" analogy breaks down. I think this is
more a car thief scenario where he is more likely to steal a car with less
defense, all being equal.
Of course I agree with Bruce's remarks about the importance of prompt
detection and response, but I am not sure how the knowledge of "network
terrains" can help defend against attackers. Perhaps knowledgeable sysadmins
could shed some light here.
AY
------------------------------
From: [EMAIL PROTECTED] (Graywane)
Subject: Re: LFSR Security
Date: Sun, 15 Apr 2001 20:55:22 GMT
While I'm at it, rather than having the hardcoded numbers below, the
generator could prompt the user for the numbers (number of MT's, range of
message sizes before hash, range of random skips in step 4, and probability
of accepting each byte of the hash.) The user could just roll a 10 sided die
several times to generate the numbers. Or maybe even have the user pick an
algorithm (3DES, AES, etc) and random key to encrypt the final stream. While
the resulting stream after all of this wouldn't be truly "random", the
"keyspace" would be large enough to prevent a dictionary attack.
Anyway, I'm just rambling now. I'll shutup and let someone tell me how
insecure it is :)
In article <[EMAIL PROTECTED]>, Graywane wrote:
> While we are on the subject, would the following be a suitable technique to
> generate "random" data for a true OTP:
>
> 1. Seed an RC4 from /dev/random on a Unix machine.
> 2. Use RC4 to provide the 624 words of state for each of 13 different
> Mersenne Twisters (mt19937)
> 3. Get a number X between 100 and 1000 from RC4.
> 4. For each of the MT's (until X bytes is output):
> A. Get a number between 1 and 1000 (from RC4).
> B. Skip that number of outputs from the MT.
> C. Output the next value.
> D. Go to next MT and repeat at step A.
> 5. Get the SHA hash of the bytes generated in step 4.
> 6. For every byte in SHA hash, flip a coin (using RC4) and output
> the byte if the coin is heads.
> 7. Goto step 3 and repeat until desired number of bytes is output.
>
> If you then took the data and burned it to a CD, would it make a descent
> OTP? (assuming you never used the same data twice and destroyed the CD when
> you were through)
--
Note: There is no example in my hostname.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Sun, 15 Apr 2001 20:55:30 GMT
"Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
news:9bd0ur$6070$[EMAIL PROTECTED]...
> > Let's alias the pad (0, 1) = (a, b)
> >
> > I could reuse the pad like aaaabbbbbababab or ababababababba or .....
>
>
> OK so the message is either aa, ab, ba, or bb.
No, if I wanted 5 random bits I could use aaaaa or abbba or bbbbb or....
Tom
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Sun, 15 Apr 2001 20:56:29 GMT
"Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
news:9bd1d8$2pgu$[EMAIL PROTECTED]...
> > Second re-using keystream has been tried before (Maurer....) and is
often
>
>
> Good for Maurer.
>
> > broken easily... Reason, chosen plaintexts or known plaintexts can be
> very
> > damaging... You can't reuse the bits and still claim it's secure
>
> I wasn't claiming anything. I asked a question.
Ok, answer, you can't reuse otps....
Tom
------------------------------
From: "Logan Raarup" <[EMAIL PROTECTED]>
Subject: Re: Password tool!
Date: Sun, 15 Apr 2001 23:02:00 +0200
Instead og entering like this:
$ passwd
Enter user's password:
Enter user's password again:
Enter user's new password:
I want to enter it like this:
$ program [user] [new password]
"Mok-Kong Shen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
>
>
> Logan Raarup wrote:
> >
> > Yes, there is a password changer in AIX. But that tool works like this:
> >
> > $ passwd
> > Enter user's password:
> > Enter user's password again:
> > Enter user's new password:
> >
> > And I wan't to make a web based application, which can change users
> > passwords. But this web based application can't enter any text in these
> > inputs!
> > Thats why i need a program, which can do this but with som arguments
> > instead.
> >
> > I hop you can help me with this.
>
> My knowledge in user interface design is very poor. Maybe
> others could help you. It seems not clear, though, how
> you want it differently than the standard way of the
> system above. What do you mean by 'arguments' above?
> (You want to enter something besides the proper password?)
>
> M. K. Shen
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Sun, 15 Apr 2001 16:02:22 -0500
> Ok, answer, you can't reuse otps....
"Mark G Wolf" <[EMAIL PROTECTED]> wrote in message
news:9bcpb4$290q$[EMAIL PROTECTED]...
> Please don't bother telling me you can't reuse a one time pad.
------------------------------
From: "Mark G Wolf" <[EMAIL PROTECTED]>
Subject: Re: Reusing A One Time Pad
Date: Sun, 15 Apr 2001 16:06:44 -0500
> > OK so the message is either aa, ab, ba, or bb.
>
> No, if I wanted 5 random bits I could use aaaaa or abbba or bbbbb or....
You can't have 5 random bits since the pad you've given only consists of 2
random bits.
------------------------------
From: Frank Gerlach <[EMAIL PROTECTED]>
Subject: Why Not OTP ?
Date: Sun, 15 Apr 2001 23:04:57 +0200
Why is it that people do not like OTP ? It seems that some people do not like
Public-Key crypto, so why not just exchanging a box of CDs ?
Some small calculations:
Secure phone
GSM (european-invented digital phone standard) voice enoding yields ca 12kbit/s
CDROMs store about 600Mbyte = 4800*10^6 bits
>>4.6 DAYS of constant speech transmission.
Of course, the CDROM should in addition be encrypted with one or more symmetric
ciphers, in case a low-garde (ie non-government) opponent steals the CD.
With a hub-and-spoke system, organizations (nation states, global companies) could
even realize virtually unlimited connectivity. The hub would decode a stream and
recode it for the receiving party.
Of course, our friends at NSA would then definitely be tempted to ask the FBI/CIA
to physically attack the hub (this is NOT fiction according to "The Puzzle Palace"
- the FBI raided embassies in Washington regularly for crypto material in the
past).
A little illustration (Herbert is the hub, all others are members of the provably
secure communications system)
Session 1
Alice ---OTP A--->Herbert--OTP B---->Bob
Session 2
Alice ---OTP A--->Herbert--OTP C---->Charlie
Session 3
Charlie--OTP C--->Herbert--OTP D---->Denise
Other issues:
-Key generation: possible Intel RNG (80kbit/s) (caution: NSA might bully Intel)
-Insider threat: of ourse, additional Public Key/symmetric crypto won't hurt
Bottom Line: Instead of HOPING that NSAGCHQ has not yet broken a particular cipher,
reduce the problem to key material generation and physical security. This is
exactly how the russians, the brits and the americans do it. Why not everybody else
?
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
