Cryptography-Digest Digest #853, Volume #8 Wed, 6 Jan 99 07:13:03 EST
Contents:
Re: Birthday Attack calculations. (Fred Van Andel)
Re: One-time pads not secure ? (NSA's Venona project) (Arnold Trembley)
Re: What is left to invent? ("Douglas A. Gwyn")
Re: What is left to invent? ("Douglas A. Gwyn")
Re: U.S. Spying On Friend And Foe ("Douglas A. Gwyn")
Re: Help: a logical difficulty ("Douglas A. Gwyn")
DES Hardware Implementation!! (Samer EL HAJJ)
Re: What is left to invent? (Pascal Brisset)
Announcement: Multi-Precision Integer library ([EMAIL PROTECTED])
Chosen-Signature Steganography (Signatory)
Re: symmetric vs various asymmetric [was: DH is "stronger" than RSA?] ("Sam Simpson")
Re: One-time pads not secure ? (NSA's Venona project) ("Trevor Jackson, III")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Fred Van Andel)
Subject: Re: Birthday Attack calculations.
Date: Wed, 06 Jan 1999 06:01:50 GMT
Reply-To: [EMAIL PROTECTED]
I would like to thank those who spent time in answering my question.
It has proven to be very helpful.
Terry Ritter wrote:
>It might be interesting to know of an application where this sort of
>precision is useful.
The reason for the needed precision is that I am designing a variable
length hash function and I want to test it for resistance to
collision. Since I don't have the resources to do a full test for a
256 bit hash I am going to test 8, 16, 24, 32 and maybe 40 bit hashes
and search for trends. If the algorithm is resistant to collision in
the smaller sizes and there is no trend away from the "proper" value
then due to the nature of the algorithm I can be quite confidant that
the larger hashes are also resistant to collisions.
Fred Van Andel
------------------------------
From: Arnold Trembley <[EMAIL PROTECTED]>
Subject: Re: One-time pads not secure ? (NSA's Venona project)
Date: 6 Jan 1999 07:23:02 GMT
Reply-To: [EMAIL PROTECTED]
Serge-Antoine Melanson wrote:
>
> Hi all,
>
> I once read in Bruce Schneier's "Applied Cryptography" that one-time
> pads were un-breakable but I saw an article on CNN's web site
> about NSA's VENONA project that seems to contradict this:
>
>
>http://www.cnn.com/SPECIALS/cold.war/experience/spies/spy.gadgets/espionage/one-time.pad.html
>
> So did the russians used pseudo-random number generators to print
> those pads or what? If those pads were breakable does it mean their
> characters sequence was not truly random or generated using a
> reproducible process?
>
> /S.A.M.
The Venona project was mentioned in the book "Spycatcher" by Peter
Wright. It says that during WWII, the Soviets ran short of key material
and used the same "pads" more than once. Their security was compromised
by reusing the keys, not by any fault in the OTP system.
I don't think that book comments on how the keys were generated.
--
Arnold Trembley
http://home.att.net/~arnold.trembley/
"Y2K? Because Centuries Happen!"
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: What is left to invent?
Date: Wed, 06 Jan 1999 08:01:56 GMT
Darren New wrote:
> Just out of curiousity, what is the theoretical cutting edge
> nowadays?
That depends on your interests and goals, which differ between the
official (secret) and public (open) domains.
> Other than user interfaces, efficiency, ubiquity, and trying to
> circumvent stupid politics, what's left to be invented?
Lots of stuff, although until it is invented nobody will know what.
Many things that were invented "behind the fence" have not yet been
discovered outside, or their significance hasn't been appreciated.
The public doesn't have a clue about cryptanalyzing stream ciphers,
and nobody has much of a clue about cryptanalyzing block ciphers.
One of my own research projects is in the latter area.
Every practical cryptosystem involves a protocol, which often proves
to be the system's weakest link. There is much work to be done in
the area of reliable identification/authentication.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: What is left to invent?
Date: Wed, 06 Jan 1999 08:05:27 GMT
Frank Gifford wrote:
> If you do a little research into rotor machines, you can get the
> feeling that all one has to do is make the rotor movement complex
> enough and the rotor system can't be broken.
No, because rotor machines are by nature composed of loosely coupled
*short-cyclic* components, and there are ways to exploit that.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: U.S. Spying On Friend And Foe
Date: Wed, 06 Jan 1999 08:09:26 GMT
Mike McCarty wrote:
> I didn't get in on the who quote, so I may be off base. But I
> *certainly* find it humo(u)rous to find that someone thinks
> that a Legislative Act can cause secrets to be kept.
A severe law that is enforced can certainly act as a disincentive
to disobedience.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Help: a logical difficulty
Date: Wed, 06 Jan 1999 08:16:45 GMT
Nicol So wrote:
> Enumerating and checking all descriptions doesn't work when the
> interpreter of descriptions is a universal computer, because of the
> halting problem (you can't even decide if a "description" really
> describes any finite string).
That's a valid point, when one is searching for the shortest
description. (The finiteness is not a problem, since as soon as
the generated string is too long, that trial can be stopped.
The real problem is that it can take an arbitrary amount of time
to produce a symbol, for example when the description evaluates
Ackerman's function before producing a symbol.) The trials can
be conducted as parallel threads (pseudo concurrency via, e.g.,
time-slicing), but the first success then isn't necessarily the
shortest matching description.
------------------------------
From: Samer EL HAJJ <[EMAIL PROTECTED]>
Subject: DES Hardware Implementation!!
Date: Wed, 06 Jan 1999 09:58:52 +0100
Hello!
I'm working on the hardware inmplementation (with VHDL into an FPGA) of
DES decryption.
after many searh I did not find any publication or example about this
topic.
Can anyone point me to some documentation on the subject?
Thanks in advance!!
------------------------------
From: Pascal Brisset <[EMAIL PROTECTED]>
Subject: Re: What is left to invent?
Date: Wed, 06 Jan 1999 09:58:53 +0100
Frank Gifford wrote:
> One thing which isn't invented yet, to my knowledge is a way for a CPU to
> execute an encrypted program, but without that CPU being able to do any
> decryption itself.
There has been some additional work on this recently. See for example :
"On Software Protection Via Function Hiding" at
http://www.icsi.berkeley.edu/~tschudin/ps/ihws98.ps.gz .
Sounds exciting, but I'd like to have an opinion from cryptography
experts.
How far is this from being implemented ?
-- Pascal Brisset
------------------------------
From: [EMAIL PROTECTED]
Subject: Announcement: Multi-Precision Integer library
Date: Wed, 06 Jan 1999 09:54:26 GMT
For some months now I have been working on a Multi-Precision Integer
(MPI) package, and now have it to the Beta stage. The library is written
in assembly language for Eric Isaacson's A386 assembler, and as presently
assembled is for 128 but ingeters; upgrading to say 1024 bits is a trivial
change. The math functions implemented are addition, multiplication,
division, subtraction (no produce a negative result) and exponentiation
in a finite field (modulo exponentiation). Several utility routines
are included, such as input, output, clear, size, shift (l and r) etc.
The files are available as mpi.zip on either of the web sites listed
below. I invite testing and comments.
--
Robert G. Durnal
Web pages at www.afn.org/~afn21533
and members.tripod.com/~afn21533
============= Posted via Deja News, The Discussion Network ============
http://www.dejanews.com/ Search, Read, Discuss, or Start Your Own
------------------------------
From: Signatory <[EMAIL PROTECTED]>
Subject: Chosen-Signature Steganography
Date: Wed, 06 Jan 1999 03:06:56 -1000
Chosen-Signature Steganography
Summary
=======
The Digital Signature Algorithm (DSA) is likely to become
widely distributed in many nations in the next few years.
The signatures contain 320 random-looking bits, and so, the
signatures are a good place to put messages without being
noticed. This essay for sci.crypt describes a way to choose
the signatures to send private messages securely and how to
decode those private messages using simple calculations which
can be done by hand or by a simple, non-cryptographic program.
This can be categorized as a type of steganography.
The General Concept of Chosen-Signature Messaging
=================================================
Signatures are created after a public message is specified.
DSA uses a pseudo-random number generator so any one message
will have different signatures each time the signature program
is run for the one message. For people who do not have encryption
software, the DSA is sometimes a good choice for sending private
messages. The private message is sent in small fragments in several
signatures. The first fragment is put in a signature by creating
many signatures for a public message until one signature is found
which has a bit pattern which matches the private message fragment
when it is scattered around the signature according to a secret
key. That signature is chosen to be sent with a public message.
The signature can be verified the normal way for DSA. The person
receiving the signature uses the secret key to select the correct
bits from the signature to reconstruct the message fragment.
Details of Chosen-Signature Messaging With Bootstrapped Keys
============================================================
Two people share a secret 3 digit key and then they part company.
This key will enable them to recover 3 bits from a signature. Those
3 bits form another digit in the key so 4 bits can be recovered in
the next signature. The 4 bits recovered form another new digit in
the key, so now the key is 5 digits long. This bootstrapping
continues until the key has 6 digits and then the private message
is recovered from all of the remaining signatures, with 6 bits
recovered from each DSA signatures.
Letters of the alphabet are coded in 6 bits using 1 through 26 to
signify a through z. Numbers are coded in 6 bits using 32 through
63 to signify 0 through 31. As each signature is evaluated, the
resulting 6 bit code is added to each key digit, mod 10, to form
the key for the next signature.
A key is used, as defined in this paragraph, to recover the bits.
(This is for a 3 digit key, 927 as an example). Bit 9 of the 320
bits in the signature is the first bit. Bit 92 of the 320 bits is
the second bit of the private message. Bit 927 mod 320 is the last
of 3 bits of the private message. (920-2*320 = 280 so bit 280 is
the last bit). So in general, the key digits are used in groups of
1, 2, and 3 digits to select the private message bits from the
signature.
Let's assume the 3 bits are 101 binary. This is 5 in decimal so 5
becomes the fourth key digit and 5 is added to the other digits
mod 10. So 927 becomes 4725 as the key for the next signature.
When the next signature arrives, bit 4 is the first bit, bit 47 is
the next bit, 472 mod 320 is the next bit and bit 4725 mod 320 is
the last of 4 private message bits. This 4 bit value is added to
each digit in the key mod 10, and this 4 bit value (mod 10)
becomes the fifth digit of the new key. This is repeated in the
next signature to get the 6 digit key. All future keys have 6
digits calculated by adding the new fragment to each key digit
mod 10.
In order to find a signature with 6 bits which conform to this
protocol, about 64 signatures will need to be generated. After
about 64 signatures have been evaluated there is a good chance
that one of them has bit values in the correct locations which
match the values of the bits in the private message fragment.
Rationale for the Bootstrapping Method
======================================
There are 2 reasons to bootstrap the key distribution. First, it
is easy to memorize a 3 digit number for most people in the world.
Some people may forget a 6 digit number too easily. The second
reason to bootstrap the key distribution is to prevent frequency
analysis from succeeding. While the 4 signatures are received to
produce a random 6 digit key, no linguistic frequency analysis
would be of any use in recognizing which bits are most likely to
be used for the private message. After these 4 rounds are used to
establish the 6 digit key, there are much more than 10^6 possible
interpretations of the messages hidden in the signatures. There
are more like 10^(6+5+4) possible interpretations, as a rough
estimate. 10^15 is about 2^48 possible interpretations. This
level of uncertainty approaches a cryptographic quality level.
This key bootstrapping method could have been extended to any
number of digits, but the more bits are hidden in the signature,
the more trial signatures need to be discarded before a
signature is found with the corect bit pattern. This work
increases exponentially, so if 16 bits need to be matched in a
signature, 66,000 signatures must be tested instead of 64 being
tested. This is a thousand fold more work to less than triple
the message density. Also, instead of decimal key digits being
grouped, binary digits could be grouped to determine the bit
locations in the signature to be used to match the private
message fragment. Decimal digits were chosen to keep this
protocol understandable for non-experts. Clearly there are
several variations that are possible to improve either the
efficiency or the ease of understanding for the layman. Along
that line, just one bit could be used in one location so that
a layman could easily interpret the signature correctly.
Conclusion
==========
The author of this "Chosen-Signature Protocol" welcomes comments
and criticisms. It is true that this type of messaging
is slow and inefficient compared to standard cryptographic
methods, but some people may not want to send private messages
with the expectation that key-recover tricks are being played on
them. Freedom-loving people now have one more way to prevent
surveillance of their private communications, by using DSA in
its normal embodiment.
------------------------------
From: "Sam Simpson" <[EMAIL PROTECTED]>
Crossposted-To:
alt.security.pgp,comp.security.misc,talk.politics.crypto,comp.security.pgp.discuss
Subject: Re: symmetric vs various asymmetric [was: DH is "stronger" than RSA?]
Date: Wed, 6 Jan 1999 08:48:14 -0000
Hi David,
Symmetric key sizes shouldn't really be compared in this way (at least not
for PGP...). Breaking one symmetric key just allows an adversary to read a
single message - breaking an asymmetric key allows the users to read all
messages past, current and future (and in the RSA allows the adversary to
forge sigs).
Bruce Schneier wrote (to sci.crypt):
"Being someone who put a table of comparisons in my book, I should say
something here. I don't think comparison tables are valid, in
general, and have to be made specific to the application. The threat
model is different. In PGP, for example, breaking the symmetric
algorithm yields one message. Breaking the public-key algorithm
yields all messages. How do you compare relative strengths there?"
Basically, choose a fairly large (e.g. 3000-bit) asymmetric key and use the
largest symmetric cipher implemented, which is currently 168-bit 3DES
(though the strength of this algorithm is more like 112-bits).
Anyway, this question has also been answered in the FAQ (which is now
complete but being proof read).
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.
David Crick wrote in message <[EMAIL PROTECTED]>...
>[EMAIL PROTECTED] wrote:
>>
>> I am producing a FAQ for comp.security.pgp.discuss to explain the
>> differences between the old style RSA keys and the new style DH
>> keys, along with all the other cryptography related changes.
>
>With the massive caveat of comparing apples and oranges (and
>insecure operating systems, relevant-IMPORTANCE vs -strength,
>etc, etc), I was wondering if the following tables could be
>completed.
>[current entries taken from AC2, and may need ammending]
>
>The * next to the column indicates that this is the "index"
>column of that table
>[I realise these could be re-done as one huge table with
> lots of entries, but felt it would be clearer this way.
> A fourth table could even be added as an index to ECC
> strength, but I feel it's not used as much at the moment
> so the other tables will suffice.]
>
>*Symmetric RSA "DH"(EG) ECC
>---------------------------------
> 40 ? ? ?
> 56 384 ? ?
> 64 512 ? ?
> 80 768 ? ?
> 112 1792 ? ?
> 128 2304 ? ?
> 168 ? ? ?
> 192 ? ? ?
> 256 ? ? ?
> 512 ? ? ?
>
> Symmetric *RSA "DH"(EG) ECC
>---------------------------------
> 56 384 ? ?
> 64 512 ? ?
> 80 768 ? ?
> ? 1024 ? ?
> ? 2048 ? ?
> ? 3072 ? ?
> ? 4096 ? ?
> ? 8192 ? ?
> ? 16384 ? ?
> ? 32768 ? ?
> ? 65536 ? ?
>
>Symmetric RSA *"DH"(EG) ECC
>---------------------------------
> ? ? 1024 ?
> ? ? 2048 ?
> ? ? 3072 ?
> ? ? 4096 ?
> ? ? 8192 ?
> ? ? 16384 ?
> ? ? 32768 ?
> ? ? 65536 ?
>
>I know that some of these numbers get 'quite' silly,
>but (for example) OpenPGP specifies RSA with up to 64Kbit
>keys.
>
>Basically I think the above completed 3 tables could sit
>quite happily in various FAQ, and given their completeness
>and length, probably wouldn't need updating for some time -
>barring mathematical breakthroughs of course!
>
>I also think that a few quotes from AC2 would be approriate
>alongside these tables if they do make it into a FAQ, namely:
>
>(from section 7.3)
>"A system is going to be attacked at its weakest point. If
>you are designing a system that uses both symmetric and
>public-key cryptography, the key lengths for each type of
>cryptography should be chosen so that it is equally difficult
>to attack the system via each mechanism."
>[...]
>"In general though, you should choose a public-key length
>that is more secure than your symmetric-key length. Public
>keys generally stay around longer, and are used to protect
>more information."
>
>(from section 7.5)
>"How long should a key be? There's no single answer to this
>question; it depends on the situation. To determine how much
>security you need, you must ask yourself some questions.
>How much is your data worth? How long does it need to be
>secure? What are your adversaries' resources?"
>
>(from 7.6)
>"Be conservative. If your keys are longer than you imagine
>necessary, then fewer technological surprises cam harm you."
>
>--
>+---------------------------------------------------------------------+
>| David Crick [EMAIL PROTECTED] http://members.tripod.com/~vidcad/ |
>| Damon Hill WC '96 Tribute: http://www.geocities.com/MotorCity/4236/ |
>| Brundle Quotes Page: http://members.tripod.com/~vidcad/martin_b.htm |
>| PGP Public Key: (RSA) 0x22D5C7A9 00252D3E4FDECAB3 F9842264F64303EC |
>+---------------------------------------------------------------------+
------------------------------
Date: Wed, 06 Jan 1999 06:53:30 -0500
From: "Trevor Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: One-time pads not secure ? (NSA's Venona project)
Serge-Antoine Melanson wrote:
> Hi all,
>
> I once read in Bruce Schneier's "Applied Cryptography" that one-time
> pads were un-breakable but I saw an article on CNN's web site
> about NSA's VENONA project that seems to contradict this:
>
>
>http://www.cnn.com/SPECIALS/cold.war/experience/spies/spy.gadgets/espionage/one-time.pad.html
>
> So did the russians used pseudo-random number generators to print
> those pads or what? If those pads were breakable does it mean their
> characters sequence was not truly random or generated using a
> reproducible process?
>
> /S.A.M.
The security of an OTP depends upon it being used properly. ONCE. If you use the pad
multiple
times, as the Russians did, you compromise all of the messages sent witht he pad.
The security of an OTP also depends upon keeping it secret. If an extra copy gets
out, as has
happenned several times, you probably want to cover up your penetration of the
organization by
claiming to have compromized the cipher technically rather than by old fashioned
spying.
------------------------------
** 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
******************************
