Cryptography-Digest Digest #146, Volume #11 Thu, 17 Feb 00 22:13:01 EST
Contents:
Re: Method to break triple-DES (Johnny Bravo)
Re: Question about OTPs (Tim Tyler)
Re: Question about OTPs (Tim Tyler)
Re: Period of cycles in OFB mode (Tim Tyler)
Re: Funniest thing I've seen in ages - RSA.COM hacked :) ([EMAIL PROTECTED])
Re: EOF in cipher??? ("Trevor Jackson, III")
Re: EOF in cipher??? ("Trevor Jackson, III")
Re: EOF in cipher??? ("Trevor Jackson, III")
Re: EOF in cipher??? ("Trevor Jackson, III")
Re: Question about OTPs ("Trevor Jackson, III")
Re: RSA Speed (Paul Rubin)
Re: NTRU Speed Claims (100x faster, etc.), explained ([EMAIL PROTECTED])
Re: VB & Crypto (lordcow77)
Re: NSA Linux and the GPL ("Adam Durana")
----------------------------------------------------------------------------
From: Johnny Bravo <[EMAIL PROTECTED]>
Subject: Re: Method to break triple-DES
Date: Thu, 17 Feb 2000 20:18:56 +0000
On 17 Feb 2000 23:07:16 GMT, [EMAIL PROTECTED] (Mickey
McInnis) wrote:
>That sounds much more difficult than the description I heard of, but since
>I didn't pay that much attention to it, I can't be sure. I think the
>number or operations required was much less, in the range of 2**64 or
>less.
You could be remembering the 2**56 part of the paper. It might be
easier for 2 key 3DES, where keys 1 and 3 are the same. For the normal
three key version you need to precompute one set of 2**56, store it in
memory, and use it with the rest of the 2**112 operations of the other two
keys. It is a known plaintext break; 2**113 operations compared to 2**168
operations, but you are still left with 112 bits to check for the 50/50
chance. The attack is real, is a massive reduction in the strength of the
cipher, but the remaining strength is still damn strong.
>My recollection is that it was something difficult and expensive, but
>not completely beyond the realm of possibility for a government or
>multinational company in the near future.
Gig machines are currently in use, and it would certainly be possible
for a dedicated machine to be built with 500 gig of RAM, but the 2**112
operations are still going to take quite a bit of time to complete. It
would be easy for a government or a large company to build such a machine,
112 bits is still pretty secure but it is about time to retire it and
implement the AES to be on the safe side.
--
Best Wishes,
Johnny Bravo
"The most merciful thing in the world, I think, is the inability
of the human mind to correlate all it's contents." - HPL
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Question about OTPs
Reply-To: [EMAIL PROTECTED]
Date: Fri, 18 Feb 2000 01:02:11 GMT
James Felling <[EMAIL PROTECTED]> wrote:
: "Dr.Gunter Abend" wrote:
[...]
:> Especially if you use a compression algorithm that nearly
:> completely removes the redundancy of the original byte streams.
: There is no such thing at present.( and likely there will never be such
: a thing). The better the compressor the harder the attack is to carry
: out, but even the best existing compressors do not produce absolutely
: uniform or characteristic free output.
A deterministic compressor is not likely to be capable of producing a
uniform distribution of cyphertexts - because some messages are sent more
frequently than others.
I expect extremely high quality deterministic compression could easily be
made available in some fairly trivial domains today. As an example, one
such simple domain includes aspects of weather measurement - traffic
which has been encrypted during times of war.
If you want close-to-uniform frequency of cyphertexts - that too would
probably not be too hard in certain restricted domains.
The problem is not so much that these things are hard to create, or don't
exist for *some* types of traffic - it's that they are hard to build for
non-trivial traffic like email messages.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
It's meaningless to speak of domesticating a child.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Question about OTPs
Reply-To: [EMAIL PROTECTED]
Date: Fri, 18 Feb 2000 01:07:37 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: Zero-redundancy plaintext, on the other hand, could be encrypted
: unbreakably even by a trivial system of encryption, since even if it
: was easy to try all possible keys, every key would yield a possible
: plaintext.
You'd better not make the encryption *too* trivial, though.
If there are less keys than there are possible decompressed files of
a plausible length, the attacker may be able to get /some/ useful
information - despite the fact that every decrypt looks like a plausible
message.
If all the possible decompressed decrypts (but not all the possible
decompressions) begin "The king is dead" when decompressed, the
attacker may have learned something he did not know before he
intercepted the message.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
Love is chemistry; sex is physics.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Period of cycles in OFB mode
Reply-To: [EMAIL PROTECTED]
Date: Fri, 18 Feb 2000 01:38:15 GMT
Paul Koning <[EMAIL PROTECTED]> wrote:
: Mok-Kong Shen wrote:
:> Scott Fluhrer wrote:
:>
:> > > > Well, one obvious approach would be to add in a step counter after every
:> > > > encryption step. That is, (if X(n) is the internal state at step n),
:> > > > turn:
:> > > >
:> > > > X(n+1) = Encrypt( X(n) )
:> > > >
:> > > > into
:> > > >
:> > > > X(n+1) = Encrypt( X(n) ) + n
:> > > >
:> > > > where the above + is either xor, or addition modulo the block size.
:> > > > Then, cycles are impossible (if X(n) = X(m) for some n!=m, then
:> > > > X(n+1) != X(m+1) )
[much snip]
:> O.K. But yet this only 'formally'/'artificially' prevents cycles.
: No, it doesn't prevent cycles at all, neither formally, nor actually,
: nor any other way.
It appears to *me* that it does.
You raised this objection before - and Scott Fluhrer advised you that
you were mistaken. I agree with him.
: Nor is there any reason to believe it changes the average cycle length,
: or the worst case cycle length. All it does is change what the cycles
: look like. [...]
: If x(k) == x(0) - n, then you have a cycle of length k for adder n,
Not necessarily:
If x(k) = x(0) - n, then when you add n, you get x(0) once again, yes.
However, x(k + 1) is not going to be equal to x(1):
x(1) = cypher(x(0) + 0)
x(k + 1) = cypher (x(k) + n + 1) :.
" " = cypher (x(0) + n + 1)
Now, since the cypher is a reversible bijection,
cypher(x(0) + 0) != cypher (x(0) + n + 1) [*]
:. x(1) != x(k + 1) :. there's no cycle of length k.
[*] ...given some conditions on the size of k, n and the block size.
This equation is true while k is smaller than the maximum value of n
(if this exists), or the size of the block of the cypher - whichever
is smaller.
The method appears to guarantee high period, offer whatever security is
associated with the block cypher, and avoids the birthday-like issue
associated with setting initial state using some type of counter.
You can equally well use a high-period LFSR (rather than a simple count)
to avoid a carry chain - if the implausible circumstances where this
serial construct is limiting the overall speed arise.
If you're going to build a stream cypher or PRNG out of a block cypher,
this appears to be an interesting way of doing it.
It's a shame it doesn't offer "random access" to the data stream, though.
--
__________
|im |yler The Mandala Centre http://www.mandala.co.uk/ [EMAIL PROTECTED]
It's not hard to meet expenses - they're everywhere.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: comp.security.pgp.discuss,alt.security.pgp
Subject: Re: Funniest thing I've seen in ages - RSA.COM hacked :)
Date: Thu, 17 Feb 2000 18:11:36 GMT
In article <88bncu$e4o$[EMAIL PROTECTED]>,
Bob Silverman <[EMAIL PROTECTED]> wrote:
> Note the date! RSA Security changed its name in fall of 1999.
> The database is out of date!
The most damning part of this thread appears to be in the next thread
(on my screen anyway) Sorry to be verbose, but here's a cut'n'paste...
<<<
Subject: RSA Cryptography Today FAQ (1/1)
Date: 15 Feb 2000 12:06:01 GMT
From: [EMAIL PROTECTED]
Organization: RSA Data Security, Inc.
Newsgroups: sci.crypt, talk.politics.crypto, alt.security.ripem,
sci.answers, talk.answers, alt.answers, news.answers
Followup-To: poster
Archive-name: cryptography-faq/rsa/part1
Last-modified: 1997/05/21
An old version of the RSA Labs' publication "Answers to Frequently Asked
Questions about Today's Cryptography" used to be posted here until May
1997. These postings were not sponsored or updated by RSA Labs, and
for some time we were unable to stop them. While we hope the
information
in our FAQ is useful, the version that was being posted here was quite
outdated. The latest version of the FAQ is more complete and
up-to-date.
Unfortunately, our FAQ is no longer available in ASCII due to its
mathematical content. Please visit our website at
http://www.rsa.com/rsalabs/ to view the new version of the FAQ with your
browser or download it in the Adobe Acrobat (.pdf) format.
RSA Labs FAQ Editor
[EMAIL PROTECTED]
>>>
So, it appears to be a classic case of left hand right hand syndrome.
Or arse elbow syndrome as we Brits would say.
Please do let us know how many heads roll...
Phil
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Date: Thu, 17 Feb 2000 21:25:06 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
[EMAIL PROTECTED] wrote:
> Hi. After getting lots of advice here on what kind of encryption I
> could build, I decided to write a stream cipher (semi based on rc4). It
> works great however I did encounter one rare issue.
>
> Question is: What do most algos do when the output is going to be EOF?
> Example say I do some bit shifting, xoring etc and I'm outputing the
> encrypted results to a file. If one of the chars in the stream when
> encrypted happens to be EOF (Ascii #26) then when my program reads it
> back in for Decryption it stops at that character.
If you read the documentation that comes with your compiler, you'll find
that EOF is not a character that you read from a file. It is a state that a
file reaches when it has read all the characters in a file. If you continue
reading the read returns an integer code that is represented by the
preprocessor symbol EOF, which is usually -1. There is no ASCII code for
EOF.
MS-DOS, in its infinite stupidity, sometimes interprets the character code
26 as a sentinel that means "no more data". The ASCII code 26 actually
stands for the control symbol SUB (substitute), and can be typed with
control-Z. MS-DOS only does this to silliness to "text files". It does not
do this to "binary" files. For further documentation see the MS-DOS
reference manual for COPY switches /a and /b.
To avoid this problem open your files in "binary" mode. See the
documentation for open() and fopen() for more details.
------------------------------
Date: Thu, 17 Feb 2000 21:27:13 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Mok-Kong Shen wrote:
> Stephen Houchen wrote:
> >
>
> > If you're programming in C, open the file as "binary" (mode "rb", for
> > example).
>
> I am ignorant of what the C standard specifies. Question: Does
> 'binary' require the file to be multiple of words or just any multiple
> of bytes will do? Thanks.
Neither. The elements written to files are characters. Sometimes
(usually) that means bytes.
------------------------------
Date: Thu, 17 Feb 2000 21:29:55 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Runu Knips wrote:
> JPeschel schrieb:
> >
> > "Douglas A. Gwyn" writes:
> >
> > >When reading random bit patterns, the program should not perform any
> > >text format interpretations. In C, the file should be opened as a
> > >binary stream, not a text stream.
> >
> > And use FEOF to detect the end of the binary file being read.
>
> FEOF is not standard. Which compiler defines such a strange variable ?
> EOF works well, because EOF is defined to be -1, while all characters
> are returned as nonnegative values.
>
> If you want to read binary data, use fread (buf, 1, 1, file). It reads
> always in the 'binary' way no matter if you have opened the file in
> text or binary mode. You cannot open file in binary mode on some unix
> systems (they simply fail to open if 'b' is in the open specification,
> even if that conforms not to ISO C), so this is the portable way.
I suspect he means feof(), typically a macro.
------------------------------
Date: Thu, 17 Feb 2000 21:31:36 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: EOF in cipher???
Runu Knips wrote:
> JPeschel schrieb:
> >
> > "Douglas A. Gwyn" writes:
> >
> > >When reading random bit patterns, the program should not perform any
> > >text format interpretations. In C, the file should be opened as a
> > >binary stream, not a text stream.
> >
> > And use FEOF to detect the end of the binary file being read.
>
> FEOF is not standard. Which compiler defines such a strange variable ?
> EOF works well, because EOF is defined to be -1, while all characters
> are returned as nonnegative values.
This is _completely_ off topic. But the last statement is completely
false. The signedness of characters is implementation defined. Thus on
some systems characters are signed.
------------------------------
Date: Thu, 17 Feb 2000 21:50:09 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Question about OTPs
"Dr.Gunter Abend" wrote:
> Mark VandeWettering wrote:
> >
> >> Arthur Dardia: Reusing the pad ("OTP") at different offsets
> >
> > The crack proceeds as following: You can find the offset
> > rather easily by basically taking the two texts at different
> > offsets, and XORING them together.
> > If the two streams are synchronized at the offset you've
> > chosen, you get a MASSIVELY different frequency distribution.
>
> Is that still true if you compress the plaintexts beforehand?
> Especially if you use a compression algorithm that nearly
> completely removes the redundancy of the original byte streams.
> You always should compress your texts in order to use less pad
> material. Your suggested crack woun't work:
>
> > ... you basically just take common words and run them through
> > the combined text, and see if real words pop out the other side.
> _____________________
>
> > You can't reuse any part of a OTP without seriously
> > jeopardizing it's security. The same error sometimes happens
> > when people reuse seed values for stream ciphers.
>
> I'm sure, you're right. I'd not suggest compression as a *cure*
> of the security problem -- I only ask if still a *simple* attack
> exists against Arthur's method.
>
> A few months ago, I asked the experts in this group to quantify
> the insecurity of a "modified" OTP. They refused, because even my
> small manipulation would be a sacrifice to the holy OTP.
>
> I proposed to skip a part of the pad if a spurious accident
> happened, i.e. I would like to omit *sending* a certain message,
> and use the pad for a different, perhaps a dummy one, or even
> discard it completely.
>
> This slight reduction of the security should, as I guessed, render
> OTP not worse than other encryption tools with reasonable key
> lengths, but omit occasionally sending readable cipher texts.
> (Please don't repeat the discussion, *why* I want to avoid
> intelligible cipher texts, and how to test it automatically).
>
> I still ask you experts: please quantify the lack of security!
>
> OTP is an extremely promising technique -- it provides absolute
> security (if you have a reliable channel for the transmission of
> the pad material, may be long time before you use it), and it is
> deniable: As soon as the pad is destroyed you can neither prove
> nor disprove the contents of an encrypted message, especially if
> you always append some garbage (so that even the length of a
> message carries no information).
>
> 1. How insecure is an algorithm that skips a few bytes of the pad
> (instead of using just the position at the end of the previous
> transmission) for those x % of all messages that fall through
> the "readability" test?
The answer depends upon the reason for skipping a few bytes. In
principle skipping a few bytes representing a message not sent is
identical to not skipping a few bytes and not sending the message. If
the pad is composed of independent, unpredictable key values, they
skipping or not skipping is irrelevant.
If, however, you skip key bytes due to the contents of the keys rather
than their position, you can easily compromise the strength of the
system.
>
>
> 2. How insecure is an algorithm that reuses the pad (instead of
> transmitting a new one) in case you run out of material? You
> might reorder the pad by a predefined algorithm so that both
> parties can do it identically. I know that the pad is no more
> completely random, but it still is randomly distributed, as
> before. You might use a few of these permutations -- if you are
> sure that you always stay far away from identity. You might
> prove theoretically whether the permutation algorithm avoids
> coincidences. The algorithm may be controlled by a few still
> unused bytes of the pad itself so that an eavesdropper only knows
> that you used one of a huge number of possible permutations.
Completely insecure. The definition of "one time" is one time. If you
use a key value multiple times then you aren't using it one time.
Multiple times <> one time.
No matter how sophisticated the permutation algorithm, the material
being permuted is no longer unpredictable.
>
>
> I guess: The length of the "key" for these permutations is a
> comparable measure of the security like the key length for other
> encryption techniques. If you append 10.000 keys of 100 bytes
> length ( = 1MB ), you can use your pad material 10.000 times.
> It should be nearly impossible to hide a backdoor within this
> permutation algorithm. Therefore it is more trustworthy than
> commercially available complicated cryptosystems.
No.
If your messages average 5 Kb (about two pages of a letter), then they
have 40K bits. Attempting to protect 40K bits with 800 bits (100 bytes)
violates the definition of the OTP. Only if the permutation keys were
the same size as the messages and you had a permutation key for each
message would you have sufficient entropy. But if you had that much
permutation key material you might as well use it directly as cipher
keys rather than recycling used cipher key material.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Re: RSA Speed
Date: 18 Feb 2000 02:49:32 GMT
Erik <[EMAIL PROTECTED]> wrote:
>Thanks. After I improved my multiplication routine and implemented
>Montgomery multiplication, it came down to around 2 seconds. But how do
>you use the C.R.T? AC gives an algorithm for it, but doesn't explain
>how to use it to find C^d mod n.
Basically you use the secret factors p and q, where n=pq. You can
figure out two new exponents d1 and d2, then get C^d mod n by
computing (C^d1 mod p) and (C^d2 mod q) and combining the residues
together with the CRT. Look in Knuth vol. 2 or some similar math
book about how to do this (see "Garner's algorithm").
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: NTRU Speed Claims (100x faster, etc.), explained
Date: Fri, 18 Feb 2000 02:44:31 GMT
In article <88g2ij$1f9$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (David Wagner) wrote:
> Coppersmith's work was great pioneering work, but the characterization
of
> it given in the NTRU FAQ is, IMHO, a misinterpretation. And, of
course,
> this is a mistake which makes NTRU look better. If one reinstates use
> of RSA with low exponents (e=3), a large portion of the claimed
speedup
> of NTRU quickly evaporates.
A lot of people have abandoned RSA with e=3. I think more people
use e=65537 now. Whether there is a solid security reason for
doing so is a matter for some debate, but if someone is going
to compare against RSA I think it is fair to compare against
RSA in the manner that it is most commonly used.
> NTRU looks intriguing. And there are some very interesting academic
> papers on the subject. It might even be a better, faster, and
> more secure public key cryptosystem. If it is, I want to use it!
I think the real problem is that NTRU is a knapsack-style system,
and such systems do not have a good track record. The NTRU folks
may have found a rock-solid, but convincing everyone is tough.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
Subject: Re: VB & Crypto
From: lordcow77 <[EMAIL PROTECTED]>
Date: Thu, 17 Feb 2000 18:56:46 -0800
VB is a poor prototyping language for anything other than GUIs.
The lack of bit operations and unsigned integer support really
hurts and the weak typing of the language allows (ie. Variants)
logic and algorithm errors to creep in where they normally would
be caught in a more strongly typed language.
* Sent from RemarQ http://www.remarq.com The Internet's Discussion Network *
The fastest and easiest way to search and participate in Usenet - Free!
------------------------------
From: "Adam Durana" <[EMAIL PROTECTED]>
Subject: Re: NSA Linux and the GPL
Date: Thu, 17 Feb 2000 22:06:20 -0500
> "Personally, I don't know if the Linux license allows the NSA to
> make a secure version of the operating system if they are not going to
> freely distribute the results."
The bigger question is why is the NSA wasting thier time with Linux? If I
were them I would work on something like OpenBSD, or maybe FreeBSD since
OpenBSD is based in Canada. I guess the NSA is just being trendy.
------------------------------
** 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
******************************
