Cryptography-Digest Digest #199, Volume #12 Tue, 11 Jul 00 04:13:01 EDT
Contents:
Re: Who was that girl? (Benjamin Goldberg)
Re: DES Analytic Crack (Mok-Kong Shen)
NTRU PKC (Vin McLellan)
Re: Random Numbers (Mok-Kong Shen)
Re: Random Numbers (Mok-Kong Shen)
Re: Random Numbers (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: Proposal of some processor instructions for cryptographical (Mok-Kong Shen)
Re: key dependent s-boxes (Hideo Shimizu)
Re: One plaintext, multiple keys (Mok-Kong Shen)
Re: Concepts of STRONG encryption using variable base http://www.edepot.com/phl.html
(Bryan Olson)
----------------------------------------------------------------------------
From: Benjamin Goldberg <[EMAIL PROTECTED]>
Subject: Re: Who was that girl?
Date: Tue, 11 Jul 2000 06:19:47 GMT
Arthur Dardia wrote:
>
[snip]
>
> I believe you are referring to the Irish girl named Sarah Flannery
> (yes, no, maybe)? Her cipher was a modified version of RC5 but it
> was later broken.
Yes as to the name, but her cipher was a public key algorithm, using
matrix multiplication mod n. It had no relation to RC5, AFAIK.
--
This is the signature worm.
Help me spread by appending me to your signature.
This is the signature worm.
Help me spread by appending me to your signature.
This is the signature worm.
Help me spread by appending me to your signature.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: DES Analytic Crack
Date: Tue, 11 Jul 2000 08:35:51 +0200
"Douglas A. Gwyn" wrote:
> Mok-Kong Shen wrote:
> > But the formal equations describing DES in terms of bits as variables
> > after optimizations are, I guess, still beyond the reach of current
> > resources to handle, in time, if not in storage.
>
> Even without any significant "optimizations", the DES enciphering
> equations can be "handled" in both storage and time -- in the *forward*
> direction. It is the inversion (solution for key bits) that is hard.
> The combined equations are an AND of the individual CT bit expressions,
> each of which contains a huge number of terms like P0K0!P1K1P2!K2 ...
> Most naive attempts to simplify these merely move the complications
> from one part of the expression to another. In fact one can estimate
> the size of the *solution* expression(s) in terms of the PT and CT
> bits treated as independent variables, for example via straight
> elimination techniques, and that is indeed unworkable. That's why
> another approach is necessary.
I believe that's true. But if one does not intend to solve for the key,
then one can use the original formulation of DES to derive the output
of DES from the input. I suppose that the main point of establishing
a formal set of equations in terms of bits is to compute the key bits
out of a pair of input and output bits.
M. K. Shen
------------------------------
From: Vin McLellan <[EMAIL PROTECTED]>
Subject: NTRU PKC
Date: Tue, 11 Jul 2000 02:58:50 -0400
In a sci.crypt post about SecurID crypto, I twitted Joseph Ashwood
<[EMAIL PROTECTED]> about the harsh comments someone (with the same name
and e-mail address) had posted to the Cypherpunks mailing list, on July
4th, about the July 3 NY Times "Patents" column on the new NTRU
public-key crypto patent.
Mr. Ashwood, in reply, denied making those statements and demanded a
retraction.
Joe: If you have been the victim of an identity theft, you have my
sympathy and a very sincere apology. If, OTOH, this was just an off the
cuff response to the NYT article -- perhaps written without bothering to
look up the patent at issue -- I wouldn't want to make too much of it,
either.
IMNSHO, only a fraction of the 400 people who posted geek-hysterial
comments on SlashDot, about Sabra Chartrand's NYT article, had bothered
to sort the media fluff about encrypted music from the spanking new NTRU
patent her/his column was based on;-)
Suerte,
_Vin
===========================
Monday, on sci.crypt, Vin McLellan <me> wrote:
> > (Elsewhere, Mr. Ashwood recently described the NTRU PKC a piece of
> > "shit" which doesn't deserve the patent it just received -- a crisp
> > cryptographic evaluation which I suspect his professional and personal
> > friends may find opportunity to recall often in the years to come;-)
Joseph Ashwood <[EMAIL PROTECTED]> replied:
> Now we get to the part that is the actual reason I replied. I think you have
> mistaken me for someone else. A quick search of www.deja.com helps assure
> me, the only occassions where my name and NTRU appear in the same message is
> the one I'm replying to, and in one where I state that with finitely sized
> keys brute force is always possible, and one reply to my brute force
> comment. Searching for my name and the word "shit" shows nothing that was
> written by me. In fact searching for NTRU and "shit" turns up only your
> message. If your abilities at journalism are anywhere near you abilities at
> writing to newsgroups I'm sure you've heard what I have to say quite often.
>
> Either provide some evidence or I would appreciate a retraction of your
> statement. However since it would be off-topic for sci.crypt, having it
> inline of the rather innevitable response your going to make to this message
> will be more than suitable.
[The topic of NTRU doesn't seem off-topic for sci.crypt -- and I
thought my message on C'punks was substantive -- so I am going to
append, below, a couple of the Cypherpunks posts on this topic.
[The message signed by a Joseph Ashwood <[EMAIL PROTECTED]>, can be found
in the C'punk archive at:
<http://www.inet-one.com/cypherpunks/dir.2000.07.03-2000.07.09/msg00076.html>
_Vin]
1. The original post:
From: "Anonymous" <[EMAIL PROTECTED]>
To: <[EMAIL PROTECTED]>
Sent: Monday, July 03, 2000 12:07 AM
Subject: New Encryption System Would Protect Digital Music
http://www.nytimes.com/library/tech/00/07/biztech/articles/03pate.html
>
> New Encryption System Would Protect Digital Music
[snip]
===============================
(2) One response, which appeared to be from Mr. Ashwood:
To: [EMAIL PROTECTED]
From: Joseph Ashwood [[EMAIL PROTECTED]]
Date: Tue 7/4/00 3:23 AM
Subject: Re: New Encryption System Would Protect Digital Music
I can't believe someone is stupid enough to believe that this might
actually even slow someone down. just grab the output of the program
(aka the input to the sound card), and pipe it into a wav file. Gee,
that put's us exactly where one would desire to be to create a
redistributable compressed file. And they were granted a patent on this
useless shite?
Joe
=============================
(3) My reply:
From: Vin McLellan [[EMAIL PROTECTED]]
To: [EMAIL PROTECTED]
Sent: Tue 7/4/00 11:03 PM
Subject: RE: New Encryption System for Music (nytimes)
On Cypherpunks, Joseph Ashwood <[EMAIL PROTECTED]> wrote:
> I can't believe someone is stupid enough to believe
> that this might actually even slow someone down. just
> grab the output of the program (aka the input to the
> sound card), and pipe it into a wav file. Gee, that
> put's us exactly where one would desire to be to
> create a redistributable compressed file. And they
> were granted a patent on this useless shit?
Yo, Joey! Check out the forest behind the tree! ;-)
All this bombast about how NTRU might be used, could be used, will be
used, to protect music and other multimedia is only a reflection of the
NYT's current obsession (albeit, widely shared) with music and film
"copyright," and crypto-enhanced intellectual property protection.
A couple of months ago, I saw another article which described NTRU
wholly in terms of its "broad potential" for enhancing wireless devices
and applications.
One does not preclude the other, obviously -- but it is unwise for
tech-savvy observers to let a NYT columnist define too narrow a
perspective for what is basically an intriguing new public-key
cryptosystem.
EduPage's paraphrase of the NYT column on NTRU put the newly patented
cryptosystem in context a lot better than either the Times, or the most
of the hundred-odd geeks who have commented about the NTRU column on
Slashdot, C'punks, sci.crypt, and other online forums.
Expanding on the NYT's narrow focus, EduPage noted the obvious:
>> [NTRU's] "public key" encryption...
>>works for virtually all data transmissions between
>>computers, cell phones, digital music players, or any
>>consumer electronic device that has Web access.
What the NTRU patent describes may be the smallest, and perhaps by far
the fastest, of the 70-odd second-generation public-key crypto
algorithms
that have been published or patented. See:
<http://www.patents.ibm.com/details?&pn=US06081597__>
NTRU claims as much as a two order of magnitude relative increase in
speed over alternative PKC systems, as well as the advantage of a tiny
code footprint. See the FAQ by Joe Silverman, one of the three NTRU
inventors and a prominent ECC scholar:
<http://www.ntru.com/tech.learning.faq.htm#Why is NTRU fast>.
I've done some consulting for NTRU, so my opinion should be taken with
a grain of salt, but I've been intrigued by what new applications might
be possible with PKC keys that can be generated so quickly and so
cheaply that they can be considered "throw-aways."
I'll leave debate about the relative security of NTRU to
mathematicians, but suffice to say that NTRU has, for the past couple of
years, been the subject of extensive study by those who specialize in
cracking
this type of structure. Current results seem to be positive. (Where
potential vulnerabilities have been identified, they have been
addressable them with some reconfig of the internal parameters: a
fairly standard
process for shaking down a new cryptosystem.)
RSA has a twenty-year head start in building trust thru endurance, of
course; but few cryptographers are gonna dismiss NTRU as a paper tiger
today. There are market niches that will go to a PKC with the greatest
speed, smallest size, and lowest power requirements; there are markets
that will go to the most trusted PKC; and others that will go to some
PKC which balances
betwixt. (I expect we will also see more application environments that
will harness multiple PKCs, to take advantage of their relative
strengths.)
While NTRU will doubtless be used to secure (probably several
different) multimedia IP formats -- eventually it will be the consumer
market, the Congress (at least in the US), and the Courts, which will
determine how far the owners of copyrighted media will be allowed to
extend their control, post-sale, over the users' daily use of CDs, DVDs,
memory sticks, etc.
Today's trends often spur tomorrow's reactions.
While discussing the potential for NTRU for media content control,
<[EMAIL PROTECTED]> pointed out:
> [1] Consider if Sony (which owns a lot of content
> producers) were to only release future content on
> players of their manufacture. Ignore the antitrust
> fnord) issues for the moment.
I don't know how the anti-trust issues play out, but one of the things
that the NYT article didn't mention is that Sony -- perhaps the largest
owner of copyrighted content -- is also a major equity shareholder in
NTRU Cryptosystems. See "NTRU Announces $11M Funding," at <www.ntru.com>
Sony stepped in with financial support for NTRU's initial development a
couple of years ago, shortly after the inventors -- three Brown
University mathematicians -- first published the NTRU cryptosystem and
filed for a patent. A couple of months ago, Sony greatly expanded it's
equity position when NTRU went out for VC funds.
The prospect for expanded corporate (or creator) control of copyrighted
content and media is really a political issue, not a technical issue. I
think, however, that it would be rash to presume that just
because an absolute barrier to "unorthodox" use is unlikely -- given
that content must eventually hit the analogue speaker or screen -- that
there will not be a variety of more or less burdensome options for
PKC-enabled restrictions on access to copyrighted content and the reuse
of media.
Not all controls on consumer praxis seem to be especially irksome,
especially if they are intended to block commercial contenders rather
than hassle unorthodox users. One of the earliest RSApkc licensees was
Atari, which encrypted and digitally signed all Atari game cartridges.
Users required an Atari console (with an embedded RSA key) to unlock the
cartridge for play.
Seemed to be very successful, although I can't recall Atari ever
bragging about it. Actually, it seemed to be a competitive detail that
the vendor didn't think mere users need be bothered with;-)
Suerte,
_Vin
"Cryptography is like literacy in the Dark Ages.
Infinitely potent, for good and ill... yet basically an
intellectual construct, an idea, which by its nature
will resist efforts to restrict it to bureaucrats and
others who deem only themselves worthy of such
Privilege." _A Thinking Man's Creed for Crypto _vbm
* Vin McLellan + The Privacy Guild + <[EMAIL PROTECTED]> *
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random Numbers
Date: Tue, 11 Jul 2000 09:12:16 +0200
John Savard wrote:
> Of course, if one wants to produce random integers with a uniform
> distribution that range between some other set of limits than 0 and
> 32,767 or 0 and 65,535; say, from 0 to 999, then one does need special
> techniques. They're doubtless explained somewhere on the web, but here
> they are anyways, since it isn't clear what keywords to use to find
> them:
>
> Let's say you want to convert a stream of bits into uniformly
> distributed numbers from 0 to 999.
>
> Then, you start by taking the bits 10 at a time to give you a number
> from 0 to 1023. If that number is less than 1000, you've got a number.
>
> Otherwise, subtract 1000 from the number, to give you a number from 0
> to 23. Treat that as a base-24 digit, and introduce it into another
> accumulator (acc = acc*24 + new_digit) that holds numbers up to 24^3,
> or 13824.
>
> When this has happened three times, if the number in the accumulator
> is from 0 to 12999, take the last three digits as your number.
>
> If you want, you can take the first few digits, as a number from 0 to
> 12, and therefore a base-13 digit, and save them in an accumulator;
> and, if you get a result you can't use, a number from 13000 to 13824,
> you can subtract 13000 and save that result as a base-824 digit.
I don't know whether it is (or easily) possible to prove rigorously that
your procedure is exact. I would simply throw away the out of range
values.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random Numbers
Date: Tue, 11 Jul 2000 09:12:22 +0200
Nicol So wrote:
> Alternatively, you can collect enough samples to have >= 16 bits worth
> of randomness, then hash the samples (as a bit string) down to 16 bits.
> If you have good reasons to believe that the sampled bits don't exhibit
> any weird structure that may interact with a simple hash function, you
> can use a simple hash function such as CRC. If you don't feel
> comfortable with that, you can use a cryptographic hash function
> instead.
Question: Would taking the parity of groups of bits also do?
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Random Numbers
Date: Tue, 11 Jul 2000 09:12:33 +0200
Herman Rubin wrote:
> Diodes tend to have rather nasty types of dependence.
>
> There are ways to remove this, and the bias. The easiest
> to carry out, if enough are available, is to add the blocks
> with or without carry, discarding the overflow. It would
> be better to have the blocks widely separated in time; even
> storing the numbers and doing this weeks later is not a bad
> idea.
I suppose an equivalent to your suggestion is to use several
devices and combine them together. (I attempted to use
combination of a number of pseudo-random streams to get
better result in a combined PRNG.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Tue, 11 Jul 2000 09:38:34 +0200
Boris Kazak wrote:
> Mok-Kong Shen wrote:
> > It seems to be the majority opinion that the IP and inverse IP of
> > DES are entirely useless. Does anyone know any probable
> > design rationale for that?
>
> This made the design of PCboards and specialized chips for DES
> far more simple, many of the wire crossovers were untangled.
I know too little about hardware. Do you really mean that putting in
IP and inverse IP simplifies the hardware implementation as compared
to leaving these out? (It's difficult for a layman to imagine the
reasons.)
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Tue, 11 Jul 2000 09:38:38 +0200
Runu Knips wrote:
> When I have worked on Paranoia, my little cipher in the
> contest, I had to spend much time thinking about exactly
> that theme. I have described a network in the cipher paper
> which requires 109 bits to specify all (32!) possible
> bit permutations of a 32 bit word. One could implement
> that with using the following 4 instructions:
>
> BRT1 src, dest, mask
>
> - For each pair of bits at the position 2*n and 2*n+1,
> n in 0..15, of bits in src, if the bit n is set in mask,
> the values of the bit pair is swapped before getting
> assigned to dest. Therefore the mask has 16 bits.
[snip]
I am interested to see a formal proof that your scheme works for any
arbitrary permuation. Or could you illustrate on a reduced example
of an 8 bit permutation? Thanks.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Tue, 11 Jul 2000 09:38:28 +0200
Paul Hsieh wrote:
> [EMAIL PROTECTED] says...
> > Mok-Kong Shen wrote:
> > > Transposition is one of the basic operations in cryptography.
> > > However, it is in my view poorly supported currently by processor
> > > instructions at the bit level at which all modern block ciphers
> > > operate. [...]
> >
> > Since future crypto algorithms will work with a minimum block size of
> > 128 bits, this instruction would at the very minimum be capable of
> > working with half that size, i.e. 64-bit registers. A generalized
> > bit-shuffle operation would then need something like 64 * 6 = 384 bits
> > of shuffle index data. (This could theoretically be limited to the
> > number of bits needed to encode 64!, but I would not like to try to
> > dynamically split this at runtime. :-()
>
> Hmmm ... do you really need this to be that totally general? What I mean
> is -- is the permutation itself rapidly changing or is it typically
> fixed?
I would be happy if the permutation is key dependent, i.e. not fixed once
for all in the algorithm description.
M. K. Shen
------------------------------
From: Hideo Shimizu <[EMAIL PROTECTED]>
Subject: Re: key dependent s-boxes
Date: Tue, 11 Jul 2000 16:21:10 +0900
I remember folloings :
- paper propose Blowfish (maybe old FSE)
- aes proposal paper on Twofish (published).
See http://www.counterpane.com .
Generally, key dependent s-boxes can not be guarantee strength.
This is why many encryption algorithm avoid key dependent one.
Hideo Shimizu
TAO, Japan
Vladimir Castro Alves wrote:
>
> Hi,
>
> I am looking for references on key dependent s-boxes
> and their robustness compared to "conventional" s-boxes.
>
> Thanks for any hint on the subject.
>
> Vladimir Castro.
> [EMAIL PROTECTED]
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: One plaintext, multiple keys
Date: Tue, 11 Jul 2000 10:04:38 +0200
David A Molnar wrote:
> Paul Pires <[EMAIL PROTECTED]> wrote:
>
> > Any in the class of DES, AES finalist? Can you give an example of one and
> > show the type of information leaked?
>
> RSA if everyone is stupid.
>
> By "stupid" I mean everyone picks e = 3 and uses no padding.
[snip]
He was however asking for an example of block cipher, I suppose.
M. K. Shen
------------------------------
From: Bryan Olson <[EMAIL PROTECTED]>
Subject: Re: Concepts of STRONG encryption using variable base
http://www.edepot.com/phl.html
Date: Tue, 11 Jul 2000 07:45:24 GMT
[EMAIL PROTECTED] wrote:
> Tuche! (how do you spell that? Its the words you say
> when you raise a sword at another person. And what
> does it mean anyways?)
,
It's spelled touche and it means "touch". It's not the term
when raising a sword, but when acknowledging one's opponent
has scored. On the subject of definitions, NP is the set of
languages that can be accepted by non-deterministic Turing
machines in polynomial time.
> I respect that you have a somewhat more knowledgable understanding
> of Base Encryption. There are a few assumptions that you have
> made though that led you to wrong conclusions.
>
> Assumption one: The "keyspace" can be permutated through.
The keyspace can be searched through; that's not an
assumption but a fact. As long as some description of the
transform actually used is finite and its implementation
terminates, the attacker can form an search that reaches
that transform in finite time.
> Please read the algorithm again. There is a section
> that details this in more detail. There is not a n+1
> sequence like numbers where you can try the next
> number until you reach from lowest to highest.
But enumerable nevertheless.
> As explained, you do not know the symbols involved
> so you have no idea if n+1 requires an infinite
> number of steps (to take into consideration the
> infinite number of algoirhtms and var base).
Doesn't help the argument. The symbols start in the
plaintext alphabet and the translation is finite in
description and terminates. The attacker doesn't need
to know it in advance because he can search and find it
in finite time.
[...]
> All these conditions do not apply in base
> encryption. Please read the garage door example
> and chinese newspaper section.
There's no garage door actually used in the algorithm. The
analogies only illustrate the author's misconceptions.
> Assumption two: The algorithms must travel from one
> entity to another, and thus must "reside in the
> keyspace" (although it can)
No such assumption. I only relied on encryption taking
finite space and time.
--Bryan
--
email: bolson at certicom dot com
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
** 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
******************************
