Cryptography-Digest Digest #850, Volume #8 Tue, 5 Jan 99 16:13:03 EST
Contents:
Re: New Twofish Source Code Available (Joerg Heitkoetter)
The RIPEMD-160 page (David Crick)
Re: Help: a logical difficulty (Jonah Thomas)
Re: On the Generation of Pseudo-OTP (Mok-Kong Shen)
Re: U.S. Spying On Friend And Foe ("Tony T. Warnock")
Re: On the Generation of Pseudo-OTP (R. Knauer)
Re: symmetric vs various asymmetric [was: DH is "stronger" than RSA?] (Anne & Lynn
Wheeler)
Re: CTS a la Schneier, Rivest (David Hamilton)
Re: PGP International (David Hamilton)
Re: On the Generation of Pseudo-OTP (R. Knauer)
What is left to invent? (Darren New)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Joerg Heitkoetter)
Subject: Re: New Twofish Source Code Available
Date: 5 Jan 1999 19:16:43 +0100
Reply-To: [EMAIL PROTECTED]
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] (Bruce Schneier)
writes:
|> On Tue, 05 Jan 1999 02:16:05 GMT, [EMAIL PROTECTED] (James Pate Williams, Jr.)
|wrote:
[..]
|> Even so, if someone finds the new code on ftp sites outside the U.S.,
|> please let me know so I can put the data up on the website.
There is a small Norwegian firm called FAST that created the largest FTP
search engine in '98 (www.fast.no); they got owned by Lycos and the
machine is now available as http://ftpsearch.lycos.com just type
in "towfish" and find a gazillion non-us FTP sites with twofish.
--
Have fun, -joke
UNIX is user friendly. (It's just selective about who the friends are.)
------------------------------
Date: Tue, 05 Jan 1999 18:39:07 +0000
From: David Crick <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: The RIPEMD-160 page
http://www.esat.kuleuven.ac.be/~bosselae/ripemd160.html
I found this page a while ago (followed a link from some thread or
web page) and have spent ages trying to find it again. Anyway,
it's at the address above, if you want to see it :)
David.
--
+---------------------------------------------------------------------+
| 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 |
+---------------------------------------------------------------------+
------------------------------
From: Jonah Thomas <[EMAIL PROTECTED]>
Subject: Re: Help: a logical difficulty
Date: Tue, 05 Jan 1999 18:42:34 GMT
[EMAIL PROTECTED] (John Briggs) wrote:
>Mok-Kong Shen <[EMAIL PROTECTED]> writes:
>>This is also an essential problem. If for two given sequences
>>one machine says the first is less complex than the other but
>>the second machine says the contrary, which result should one take?
>Algorithmic complexity is a function of the algorithm.
>If you want to know the complexity of "54" in an absolute sense,
>you're out of luck.
That was what was asked for, and if you're willing to accept an
arbitrary criterion you can give an answer. So "54" could be
considered more complex than "31" and less complex than "97" based
on the number of binary bits required to express it in the binary
code we usually use. Or vice versa based on the number of ones in
the binary representation. Or it could be considered more complex
than "53" because it has more factors. Or you could base your
measure of complexity on how high the page numbers (and secondarily
the locations on the pages) of _War and Peace_ would required to
express it according to some code.
My claim (which you appear to agree with) was that there's a degree
of arbitraryness to such schemes. There might still be some sort of
value in attempting them.
>Of course, any algorithm worth its salt is going to let you supply
>an arbitrary Turing machine in the input stream. And so you're looking
>at a "plus a constant" worst case on the difference between the
>algorithmic complexity of any two arbitrary input streams as
>measured against any particular pair of salt-worthy, Turing-computable
>algorithms.
I may have missed your point here, this is somewhat new to me. I've
noticed that when I venture into somebody else's turf they pretty
often complain about it. When I look at what happens when it's
somebody else, when I *do* understand what's going on, sometimes they
are OK on the ideas but they use bad words (like, they say "Evolution
tries to..." and people jump on them, "Evolution doesn't try to do
anything, it just is, there's nothing teleological about it") and
sometimes they have ideas that I know don't work in my context
("You can't evolve unless you can put your acquired characteristics
into the genes, so that has to be happening even though you geneticists
don't see how.") Since I'm on your turf I don't know which of those
I'm doing.
In your example, are you saying that you want to measure the
algorithmic complexity of your algorithm, plus the turing machine in
its input stream, plus the string in the input stream? And the
difference in complexity of the two turing machines is some constant,
so the difference in complexity of the whole thing is a constant?
That makes sense to me. But can it be that one variety of turing
machine can produce the desired output using a string S while the
other produces the desired output using a shorter string T? Then
our complexity would be that of the underlying algorithm, plus that
of the turing machine (which is different in the two cases) plus
that of the strings (which is also different in the two cases). So
you might get two different answers.
>Am I missing something or should this have been obvious to everyone?
I'm sure it's obvious to everybody who shares your background and
assumptions. The only value to paying any attention to strangers
who lack that background (beyond charity, or perhaps the opportunity
to vent spleen) is that on rare occasions it might happen that your
assumptions are extended to situations where some other point of
view might have some value. Those may be rare enough not to be
worth your time.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 05 Jan 1999 19:01:59 +0100
jay wrote:
>
> Nonetheless, I suppose a secure encryption program based on books would
> quickly be placed under the Wass. restrictions, placing us back with the
> Ciphersaber approach: publish the format and the algorithm, develop the
> software locally. The same problems would exist, that is, people would not
> have easy access to appropriate privacy software without writing it
> themselves or having a qualified friend.
The techniques I mentioned are all very simple to implement. So
regulations wouldn't work much in reality. In general, I believe
simplicity of is of vital importance for all algorithms that are so
to say immune to the export regulations for this very reason.
For people with some programming proficiency will be able to
do easy implementations outside of the export-regulating countries.
Sufficient strength can usually be achieved through higher number
of rounds, etc. In circumstances where the paradigm 'security
through inefficiency' can function I can see no justification of
using complicate to understand (hence implement) algorithms.
Above all, I like to solicite giving more efforts to research
and development of good algorithms within the 56-bit bound, thus
sacrificing (unfortunately because any person's time is limited)
in leaving consequently more work on perhaps scientifically
more interesting algorithms with larger key lengths to the others
(including the regulating officials and their helpers).
M. K. Shen
------------------------------
From: "Tony T. Warnock" <[EMAIL PROTECTED]>
Subject: Re: U.S. Spying On Friend And Foe
Date: Tue, 05 Jan 1999 10:48:21 -0700
Reply-To: [EMAIL PROTECTED]
Douglas A. Gwyn wrote:
> "Tony T. Warnock" wrote:
> > The great problem of "friends" spying on the US is that the
> > "friend" may not be able to keep secrets. Some of our allies may not
> > mean harm to us, but they cannot keep secrets. Vice versa.
>
> The British can keep secrets, and they have an Official Secrets Act to
> enforce it.
That's a Blunt statement. Both the Brits and the US believe that the other
cannot keep secrets. They are both Wright.
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 05 Jan 1999 19:14:52 GMT
Reply-To: [EMAIL PROTECTED]
On Tue, 05 Jan 1999 16:13:23 +0100, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>But before doing that I want to
>recall that a pseudo-OTP can be obtained trivially from a PRNG, if
>the sequence is not longer than the period of the PRNG and each
>subsequence is never reused.
A "pseudo-OTP" is just a stream cipher, and has nothing to do with the
OTP cryptosystem unless the stream is generated by a TRNG. IOW, the
term "pseudo-OTP" is an oxymoron. I discovered this myself when I made
the same kinds of proposals here on sci.crypt a year or so ago.
All PRNG-based stream ciphers suffer from the fact that output is
limited to the number of possible seeds. That means that if an
intelligible message is uncovered in an attack, it must be the
intended message.
With the OTP system, all possible messages can be encrypted to give
the same ciphertext, making it impossible for the attacker to know if
he uncovered the intended message even if it is intelligible. That
makes the OTP system totally unbreakable.
>One simple and convenient such source suggests
>itself: natural language texts.
You must not have been around when we discussed a similar method I
proposed about a year ago on sci.crypt. I am sure I was not the first
to do so.
In the system I proposed you would pre-agree on certain text sources
that would change daily, like an online newspaper. Then you would use
certain least significant digits of daily closing market figures
(e.g., DJIA, S&P, etc.) as your offset into the various text streams.
You would use only the least significant bits of the selected text
which you would clean up using the methods discussed by Schneier to
remove bias and correlation in stream ciphers. As long as you kept the
procedure a secret you had a pad that for all effects and purposes
looked like it was generated by a TRNG. Or so it would seem.
That system I proposed was criticized on several counts. One person
stated that the methods for removing correlation mentioned by Schneier
does not work reliably in all cases, in particular LSB text streams.
Another noted that an analyst could try all possible sources of
Internet text, although that seems a bit much. Another claimed that it
is unnecessary to go to all that trouble since modern cryptosystems
such as IDEA with sufficiently large keys can never be broken as a
practical matter. But that is not a valid criticism here, since you
are looking for ways to circumvent key length restrictions.
>For one
>needs only to record the offsets of the different streams participating
>in the pseudo-OTP that has been arrived at by the previously sent
>messages.
You do not need to do that if the source of the text changes each day,
such as online newspapers or mailing lists that you and your
correspondent receive.
>Some remarks to special cases: Some of the participating streams could
>even be from the same text, i.e. differing only in offsets. In place of
>natural language texts one could also use mathematical constants, e.g.
>Pi. Further, since the sources are entirely public, these need not even
>be stored at the user's place but downloaded as needed from some server
>of the internet.
At that time a year ago I also proposed using the "digit expansions"
of certain transcendental constants like pi, ln(2), 2^1/2, etc., which
can be computed (see Bailey-Borwein-Plouffe) using known algorithms.
To confuse matters, one could combine different sequences from
different offsets of different expansions and attempt to remove any
possible bias and correlation by known techniques. The one redeeming
feature of this over text streams is that the bit sequences
transcendental constants are not periodic - or supposedly they are not
periodic. Whether the sequences are biased or correlated is something
I have never seen discussed.
The one redeeming feature of this system is that there is no need to
acquire text. All that is required is to keep the system a secret
(like a key) and never reuse the same pad.
>In the above I have made a humble attempt to sketch one possible way
>of obtaining a pseudo-OTP. I should appreciate your opinions on that
>and suggestions of other ways of advantageously generating such for
>applications in the future 56-bit environment.
I suspect that if such systems became widespread, the authorities
would claim that the pad thus obtained constitute a key of length
greater than 56 bits, and therefore is restricted.
After all, the whole purpose for a 56 bit key is that there can only
be 2^56 possible plaintexts and therefore any intelligible message
over the unicity length of 8.2 ASCII characters obtained by a brute
force attack must be the intended message. IOW there is only one
intelligible message possible of length greater than 8.2 ASCII
characters with a 56-bit cryptosystem.
Bob Knauer
"It could probably be shown by facts and figures that there is no
distinctly native American criminal class except Congress."
--Mark Twain
------------------------------
From: Anne & Lynn Wheeler <[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: 05 Jan 1999 11:07:31 -0800
Reply-To: Anne & Lynn Wheeler <[EMAIL PROTECTED]>
one approximation i've seen is that RSA "strength" is roughly
10**(sqrt(N))
where N is number of bits
and ECC "strength" is roughly
10**(N/4)
sqrt(N) 4*(sqrt(n))
2048 45 180
1024 32 128
512 23 91
--
--
Anne & Lynn Wheeler | [EMAIL PROTECTED], finger for pgp key
http://www.garlic.com/~lynn/
------------------------------
From: [EMAIL PROTECTED] (David Hamilton)
Subject: Re: CTS a la Schneier, Rivest
Date: Tue, 05 Jan 1999 19:39:29 GMT
=====BEGIN PGP SIGNED MESSAGE=====
[EMAIL PROTECTED] wrote:
(snip some)
>it would greatly encrease the
>strength of encryption compared to simple methods endorsed by Mr B.S
>and his NSA friends.
What 'simple methods' are you referring to?
> Just my opinion never having read his book.
>David Scott
Not much of an opinion is it then? Still you were never one to let the facts
get in the way of smears, wild statements and unsubstantiated claims.
David Hamilton. Only I give the right to read what I write and PGP allows me
to make that choice. Use PGP now.
I have revoked 2048 bit RSA key ID 0x40F703B9. Please do not use. Do use:-
2048bit rsa ID=0xFA412179 Fp=08DE A9CB D8D8 B282 FA14 58F6 69CE D32D
4096bit dh ID=0xA07AEA5E Fp=28BA 9E4C CA47 09C3 7B8A CE14 36F3 3560 A07A EA5E
Both keys dated 1998/04/08 with sole UserID=<[EMAIL PROTECTED]>
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
Comment: Signed with RSA 2048 bit key
iQEVAwUBNpJpd8o1RmX6QSF5AQEGEAf+NJPmubVMwkH8qyDAxuYx3IIOHgVrqhBc
+8d+SqXs/Ks2mdj3KKCLTSQRScjY3P9ESEQKjSHOXkZE2toxnA8tYez+G5a/ouFk
cuq5kZTiBKF6lFgqqMxpO59Mms6o7dYtrcizER6g6SVd2CiCw7L0DWtf9A56sHf8
pZwJamdltvhGYMsNcxVVIzrTorthy1QcRJvxKZscVVzBl03wCLXxEN9lLOZQko0b
4bs4KaUSgwr+S0mwA+dE4Sm4U2EfapyNIUb3Ekd+g+65J9U1b+E3CR3q+Qa6kF/A
/LAscLQ4V+dEXHhgahCqRh0OOxubKkCSZnda14YWtxgSi4Q9lPhZqA==
=RxTF
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (David Hamilton)
Subject: Re: PGP International
Date: Tue, 05 Jan 1999 19:39:19 GMT
=====BEGIN PGP SIGNED MESSAGE=====
"Jason Shea" <[EMAIL PROTECTED]> wrote:
>Hi all,
>
>i figure ill probably get kicked in the ass for this question, but, is there
>a difference between PGP, and PGP international. Nothing in the manuals seem
>to indicate that it is in anyway different...
>
>Im told by several people that the PGP international version is considerably
>weaker than the american version.
These 'several people' that you refer haven't got a clue about the subject
matter. (ie They are 100% wrong.)
David Hamilton. Only I give the right to read what I write and PGP allows me
to make that choice. Use PGP now.
I have revoked 2048 bit RSA key ID 0x40F703B9. Please do not use. Do use:-
2048bit rsa ID=0xFA412179 Fp=08DE A9CB D8D8 B282 FA14 58F6 69CE D32D
4096bit dh ID=0xA07AEA5E Fp=28BA 9E4C CA47 09C3 7B8A CE14 36F3 3560 A07A EA5E
Both keys dated 1998/04/08 with sole UserID=<[EMAIL PROTECTED]>
=====BEGIN PGP SIGNATURE=====
Version: PGPfreeware 5.5.3i for non-commercial use <http://www.pgpi.com>
Comment: Signed with RSA 2048 bit key
iQEVAwUBNpJhZco1RmX6QSF5AQEx8wgAhzSuUHpa61r4lqz6pThFlHsxrvvl/m/x
i9lex7LEBNKjel5SZr+s6BSqOXNTTEnsVp33n5hKqd3DiOVjoM/fLB9uU3JE2vEx
dLaPusKBCXBDl9SS7yjHN+Es1Ds42fB5xJjeZN0tvmh6rC/tggYlka5Xbhnc8k8b
ws3QGITbep/8UundJ9CVsyc/ncjxjVAU6YQU+hT3fpaw0cDHKwEZ0Na2zk5B4j74
4WbeYubrduOpbpFxeRwOnMPc5z94ost+MLhXtIzoB78y15vkqQq9S1om6NPzK8zp
a5yOdbAkOBncBSLxCHZa28hCh1NEuFt1Ydp82q/dUDnlNOQgII9V3w==
=eSGO
=====END PGP SIGNATURE=====
------------------------------
From: [EMAIL PROTECTED] (R. Knauer)
Subject: Re: On the Generation of Pseudo-OTP
Date: Tue, 05 Jan 1999 19:29:41 GMT
Reply-To: [EMAIL PROTECTED]
On 5 Jan 1999 17:20:49 GMT, "jay" <[EMAIL PROTECTED]> wrote:
>Strictly speaking, I suppose the key length would be the length of the
>titles of the books and offsets, quite a bit larger than 56 bits.
The notion of key length is that there can only be 2^k possible
messages encrypted with a key of k bits. Therefore even the OTP system
with a pad longer than 56 bits is a technical violation of the 56-bit
restriction.
>Of course, as you indicate, it may be quite embarrassing for a government to
>make that claim.
I would never count on the govt displaying embarrasment over anything.
The upshot of the 56-bit restriction is that no matter how you try to
hide your message, it will be exposed in a brute force attack since it
is the only intelligible message possible if it is longer than the
unicity distance (8.2 ASCII characters).
Nowadays 56-bit brute force attacks are easy with the kind of
equipment the govt has.
Bob Knauer
"It could probably be shown by facts and figures that there is no
distinctly native American criminal class except Congress."
--Mark Twain
------------------------------
From: Darren New <[EMAIL PROTECTED]>
Subject: What is left to invent?
Date: Tue, 05 Jan 1999 20:56:05 GMT
Just out of curiousity, what is the theoretical cutting edge nowadays?
We already have
provably-secure cryptography (OTP),
public key cryptography based on known-hard math,
anonymous key exchange,
crypto requiring variable subsets of multiple keys,
blind signatures, digital money you can make change for,
lots and lots of other stuff.
Other than user interfaces, efficiency, ubiquity, and trying to
circumvent stupid politics, what's left to be invented?
The only thing I can think of is the theory behind making a block
cypher's S-boxes secure and knowing it (rather than just making it real
complex and hoping there's no unexpected hole in it).
I suppose there are also unusual combinations, like having anyone able
to decrypt your message but wanting at least three people to have to
cooperate to authenticate it.
Note, this is a serious question from a greenhorn who is just curious
what the current theoretical researchers are into, not intending to
imply we've already invented everything. :-) I realize it might be
secret and proprietary and all until it's finished and patented and all.
--
Darren New / Senior Software Architect / MessageMedia, Inc.
"You could even do it in VB, though that should only be recommended to
folks who think that self-flagellation is for the effete."
------------------------------
** 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
******************************
