Cryptography-Digest Digest #198, Volume #12 Tue, 11 Jul 00 02:13:01 EDT
Contents:
Re: Proposal of some processor instructions for cryptographical ("Douglas A. Gwyn")
Re: Proposal of some processor instructions for cryptographical ("Douglas A. Gwyn")
Re: Random Numbers (Nicol So)
Re: A thought on OTPs (Nicol So)
Re: DES Analytic Crack ("Douglas A. Gwyn")
Re: Quantum Computing (Was: Newbie question about factoring) ("Douglas A. Gwyn")
Re: A thought on OTPs ("Douglas A. Gwyn")
Re: Who was that girl? ("Douglas A. Gwyn")
Secret Messages and the Intelligence War (CryptoBook)
Re: Who was that girl? (Arthur Dardia)
Re: Who was that girl? (David A Molnar)
Re: #sci.crypt irc channel (Arthur Dardia)
Re: SecurID crypto (was "one time passwords and RADIUS") (Roger Schlafly)
Re: Concepts of STRONG encryption using variable base http://www.edepot.com/phl.html
([EMAIL PROTECTED])
Re: Proposal of some processor instructions for cryptographical applications (Paul
Hsieh)
Re: Steganographic encryption system (John Winters)
Re: Proposal of some processor instructions for cryptographical applications (Paul
Hsieh)
----------------------------------------------------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Tue, 11 Jul 2000 00:13:02 -0400
Scott Fluhrer wrote:
> For example, in terms of private key encryption systems, we already
> know how to do secure (at least, to the best of our knowledge)
> encryption in 10-20 cycles per byte encrypted (eg. the AES finalists).
Which were designed specifically with common existing architectures
in mind. On any word-oriented architecture, there will be occasions
when one can treat memory word access as the parallel bit-bus transfer
that it really is, and of course parallelism speeds things up. But
try using such tricks on a good stream cipher some time; they tend to
use inherently serial algorithms, not parallelizable ones.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Tue, 11 Jul 2000 00:16:07 -0400
Jayant Shukla wrote:
> The AES candidates are not too _tiny_. In fact, the fully pipelined
> version of the AES candidates could not be fitted on Xilinx XC4000
> FPGA. The NSA paper shows that even the most efficient implementation
> of these algorithms in hardware takes up > 23 mm^2 of silicon.
> Don't even ask about the fully pipelined versions ( ~1000 mm^2).
Sounds to me like somebody screwed up. The TMS320C6201 versions
were something like 1KB each on average.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Random Numbers
Date: Tue, 11 Jul 2000 00:20:34 -0400
Reply-To: see.signature
Herman Rubin wrote:
>
> Independence is MUCH harder to approximate than lack of
> bias. It is also much harder to detect.
Both statements above relate to the existence of secure encryption
algorithms. Since I tend to believe in their existence, I tend to agree
with the latter statement (but I also believe that independence cannot
be *too* hard to approximate).
Strictly speaking, what I'm going to say depends on how the notion of
security is formalized, but to keep the discussion informal, I'll
handwave. So bear with me.
If secure encryption is indeed possible, one can construct a secure
pseudorandom number generator out of a secure cipher. What a secure PRNG
does is essentially to "stretch" a short random bit string (the seed)
into a longer one in such a way that the resulting string can pass for a
truly random bit string of the same length. That is, no efficient
algorithm have more than a negligible chance of success in telling apart
output of the PRNG from the "real thing".
If secure PRNGs exist, they can fool all efficient algorithms, including
statistical tests. So... independence cannot be too hard to approximate
(when you have the right tools). On the other hand, independence should
be hard to detect, since you can't tell how much randomness there really
is in an apparently random string.
So... in order to do it right, one really needs to have a good model of
how redundancy in the output of a random source manifests.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Date: Tue, 11 Jul 2000 00:21:32 -0400
Reply-To: see.signature
Mok-Kong Shen wrote:
>
> Let's have the hypothesis of independce of two random variables.
> You test for their correlation with the chi-square test and find that
> the correlation is extremely small. How could you claim that the
> given hypothesis of independence is not rejected at certain given
> confidence level (since one knows that two dependent variables
> MAY even have zero correlation)? If you in fact want to test
> independence, you have to use the definition of independence.
> That definition is stated in textbooks. However, there has, as far
> as I am aware, yet been no practical test developed by the
> mathematicians for that, at least for the bit sequences we are
> interested in.
See my message in the thread "Random Numbers", which discusses why
independence is hard to test for in the general case. For sources that
don't exhibit complicated forms of redundancy, efficient test for
independence may be possible. For sources that contains a cryptographic
filter, efficient test may not be possible.
--
Nicol So, CISSP // paranoid 'at' engineer 'dot' com
Disclaimer: Views expressed here are casual comments and should
not be relied upon as the basis for decisions of consequence.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: DES Analytic Crack
Date: Tue, 11 Jul 2000 00:25:06 -0400
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.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Quantum Computing (Was: Newbie question about factoring)
Date: Tue, 11 Jul 2000 00:30:23 -0400
Bill Unruh wrote:
> ... NMR computations are the the only computers which have been
> created with more than one or two qubits, but ...
Check out the news about Josephson junctions.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: A thought on OTPs
Date: Tue, 11 Jul 2000 00:36:08 -0400
Bryan Olson wrote:
> The significant issue is that the "for" and "against"
> sides are no where near equally convincing. A test
> may definitely show that two generators are not random
> and independent, but it cannot show that they are.
The right way to design such tests is to consider whether
minimization of Type I or of Type II error is more important.
(There is of course a trade-off.) For cryptography, it is
usually Type II error that we wish to minimize, and so the
power of the test becomes the most important criterion.
------------------------------
From: "Douglas A. Gwyn" <[EMAIL PROTECTED]>
Subject: Re: Who was that girl?
Date: Tue, 11 Jul 2000 00:37:24 -0400
Sarah Flannery; do a Web search.
------------------------------
From: [EMAIL PROTECTED] (CryptoBook)
Subject: Secret Messages and the Intelligence War
Date: 11 Jul 2000 04:50:41 GMT
10 July 2000
Classical Crypto Books is pleased to announce the following recent update to
the CCB catalog.
ESPIONAGE AND INTELLIGENCE
THE INTELLIGENCE WAR: World War II Chronicles
by Donald P. Steury, Foreword by Lt. Col. Roger Cirillo (Ret.)
A BEST BUY! A vivid chronicle of the secret war of 1939-1945, from SIGINT and
codebreaking to daring exploits of field agents. The author is a longtime CIA
analyst and an expert on military intelligence. Large format; profusely
illustrated in B&W and color.
HB, MetroBooks, 2000, 128 pp.
Nonmember $16.95, Member $14.95
HISTORY
SECRET MESSAGES: Codebreaking and American Diplomacy, 1930-1945
by David Alvarez
Most complete account to date of the US Army Signal Intelligence Service:
creation, struggles, rapid growth, contributions to the war effort. First
comprehensive analysis of the impact of SIGINT on
American foreign policy and strategy from 1930 to 1945. Published at $35.00.
HB, University Press of Kansas, 2000, 304 pp.
Nonmember $33.95, Member $31.95
==============
HB = Hardbound
SB = Softbound
MG = Magazine
==============
All items are in stock and available now. Member prices are available to
members of the American Cryptogram Association, the U.S. Naval Cryptologic
Veterans Association, and full-time students. Shipping and handling are extra.
For complete ordering information, a free catalog of crypto books by return
e-mail, or for information about membership in the American Cryptogram
Association, please send e-mail to: [EMAIL PROTECTED]
Best Wishes,
Gary Rasmussen
Classical Crypto Books
E-Mail: [EMAIL PROTECTED]
Fax: (603) 432-4898
------------------------------
From: Arthur Dardia <[EMAIL PROTECTED]>
Subject: Re: Who was that girl?
Date: Tue, 11 Jul 2000 00:56:55 -0400
An Metet wrote:
> Please accept my apologies for this tyro question. I scanned the FAQ and
> didn't see any reference to this.
>
> About a year ago there was a news item in the popular press that a young
> girl (age 13-16) had created a rather sophisticated new cipher (I hope I
> have that right). I've not seen anything on the subject since then, and I
> would very much like to follow up on it.
>
> If someone could direct me to a good URL that discusses this, I would be
> most appreciative. I recall reading the list of research topics undertaken
> by the young people that won (whatever prize it was), and it too was most
> impressive. A link to those topics would be very helpful too.
>
> Probably this is old news to you regulars in here, but I'm still learning.
> Thanks in advance for any guidance anyone can give me.
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.
--
Arthur Dardia Rensselaer Polytechnic Institute [EMAIL PROTECTED]
PGP 6.5.1 Public Key http://www.webspan.net/~ahdiii/ahdiii.asc
------------------------------
From: David A Molnar <[EMAIL PROTECTED]>
Subject: Re: Who was that girl?
Date: 11 Jul 2000 04:44:13 GMT
An Metet <[EMAIL PROTECTED]> wrote:
> If someone could direct me to a good URL that discusses this, I would be
> most appreciative. I recall reading the list of research topics undertaken
> by the young people that won (whatever prize it was), and it too was most
> impressive. A link to those topics would be very helpful too.
The girl's name was Sarah Flannery. She wrote a book with her father
about the experience which may be available in a bookstore or via amazon.
The algorithm is called Cayley-Purser, and a copy of her paper courtesy
Jean-Jacques Quisquater was posted to the www.cryptome.org web site a
few months back.
Another poster here mentioned a http://www.cayley-purser.ie/ site,
which I haven't visited, but which may contain more information.
As for your other question about topics for her colleagues and
co-contestants...it was my impression that she'd entered several
competitions. One of them seems to have been the Intel Science Talent
Search (was Westinghouse), and another was some kind of pan-Europe
competition. Typing "science talent search" into Google or other
search engine will probably pull those out.
Thanks,
-David
------------------------------
From: Arthur Dardia <[EMAIL PROTECTED]>
Subject: Re: #sci.crypt irc channel
Date: Tue, 11 Jul 2000 00:57:32 -0400
csybrandy wrote:
> I remember seeing a post that someone was trying to get this channel up
> and running again. I believe it is on DalNet, but every time I go
> there, nobody's home. Are people using the channel? If so, when?
>
> csybrandy
The channel got bumped over to EFNet.
--
Arthur Dardia Rensselaer Polytechnic Institute [EMAIL PROTECTED]
PGP 6.5.1 Public Key http://www.webspan.net/~ahdiii/ahdiii.asc
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: SecurID crypto (was "one time passwords and RADIUS")
Date: Mon, 10 Jul 2000 22:30:08 -0700
"Trevor L. Jackson, III" wrote:
> There's an apparent contradiction in the reliance upon customer's testimonials as
> to strength and the same reliance upon the same customers as the source of the
> preference for continuation of trade secret protection. Either the customers think
> the system is strong, or they think it may not be. The construct "they think it is
> strong as long as it is secret" is a weak reed upon which to rest the judgments
> you've endorsed.
Not at all. The customers apparently think it is adequately
strong, or they would not pay for it. But once they've paid,
why should they want it publicized?
You local bank probably thinks it has a secure vault, but
it still doesn't go out of its way to advertise the specs on it.
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: Concepts of STRONG encryption using variable base
http://www.edepot.com/phl.html
Date: Tue, 11 Jul 2000 05:28:28 GMT
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?)
Dear Mr. Olson,
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.
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. 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). It is not in the same domain as
"all the monkeys typing
will end up producing shakespear" argument. All the monkeys
are using the same english typewriter (fixed defined symbols).
All the results
of the monkeys have "shakespear the original" to compare to
(a static length also). They can do comparisons on early
successes... "To be" and "To be or not" and say "these are
on the right track"
All these conditions do not apply in base encryption. Please
read the garage door example and chinese newspaper section.
(as well as the quantum mechanic duality section in more detail).
Assumption two: The algorithms must travel from one entity to another,
and thus must "reside in the keyspace" (although it
can)
Base Encryption can utilize a novel concept of distributed encryption
engine diffused through N servers. As explained in the FAQ
Base Encryption is the future, it takes advantage of the internet.
Look for an update post or FAQ, I will explain in more detail so
newbies to the method do not make wrong assumptions again.
In article <8kbuc7$5sa$[EMAIL PROTECTED]>,
Bryan Olson <[EMAIL PROTECTED]> wrote:
> [EMAIL PROTECTED] wrote:
>
> [...]
> > Any static keylength can be searched through.
> [...]
> > Why not simply provide a scholarly comment on it.
> [...]
> > I have yet to get a solid response from this
> > community that can find errors or problems with it.
>
> Others have pointed out why we do not worry about
> brute-force. I think I can explain where the argument for
> the security of this scheme against arbitrarily powerful
> brute force goes wrong.
>
> I gather that the number of transformations the cipher can
> induce is infinite. The argument is therefore that no
> attacker could ever search through the keyspace, even given
> an unbounded (though finite) amount of computation. Here
> the "key" can be any description of the transformation as
> long as the implementation runs in finite time.
>
> Alas the argument is wrong. The keyspace the attacker must
> deal with is the one from which we actually chose the key,
> not the set the algorithm can accept. For any finite-length
> key, a brute-force search can eventually find it. To defeat
> unbounded brute-force, we cannot choose any finite length
> key with non-zero probability. Thus the argument fails
> unless we actually use infinite length keys, which doesn't
> work because we'd never finish encrypting anything.
>
> Shannon's "theoretical security" took a different approach.
> A brute-force search (even of infinite power) fails because
> the attacker get's no clue when he's found the right key.
>
> --Bryan
> --
> email: bolson at certicom dot com
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Paul Hsieh)
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical applications
Date: Mon, 10 Jul 2000 22:42:39 -0700
[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 mean you can compile a bunch of:
mm7 = ROL(mm0 & MASK0, ROT0);
mm7 |= ROL(mm0 & MASK1, ROT1);
mm7 |= ROL(mm0 & MASK2, ROT2);
... etc.
instructions. In which case you could be desirous of somewhat more
modest instruction acceleration (like a MMX rotate instruction, or a
"mask then rotate then or" instruction as shown above -- though for
crypto purposes I expect you would prefer xor as the last operation.)
But this has a worst case instruction length of 64 instructions (can
someone prove if this is necessarily less? Is it much less on average?)
You can probably do much better with some sort of "rotate by powers of
two" approach (in an effort to reduce the number of operations to
log_2(64)==6, where a bit will be rotated up to 6 times), but I don't
quite see it at the moment.
Another possibility is:
mm7 |= SPREAD( mm0, NIBBLE, DEST(D0,D1,D2,D3) );
...
which would take the nibble of mm0 indexed by the 4 bit number NIBBLE and
xor the bits at (the 6 bit) positions D0, ..., D3 of mm7. The addition 4
bits could be used as an addition constant 4 bit xor of the nibble bits
or something. This would take exactly 16 instructions to complete and
would be flexible to accept new permutations fairly quickly. Its also
seems paralizable.
What do you think?
--
Paul Hsieh
http://www.pobox.com/~qed/
------------------------------
From: [EMAIL PROTECTED] (John Winters)
Crossposted-To: comp.os.linux.development.apps,uk.comp.os.linux
Subject: Re: Steganographic encryption system
Date: 11 Jul 2000 06:46:48 +0100
In article <[EMAIL PROTECTED]>,
phil hunt <[EMAIL PROTECTED]> wrote:
>On 10 Jul 2000 19:59:28 +0100, John Winters <[EMAIL PROTECTED]> wrote:
>>In article <[EMAIL PROTECTED]>, jungle <[EMAIL PROTECTED]> wrote:
>>>phil hunt wrote:
>>>> I am thinking of developing a steganographic encryption system that
>>>> will enable a particular cyphertext to be decrypted into two or more
>>>> different plaintexts, depending on which key is used. (Provisionally
>>>> named 'stes'). To be more precise:
>>>
>>>your concept doesn't work ...
>>>you can't create system that will work on principle that ...
>>>
>>>24 decrypts into 20 or/and 21 or/and 22 or/and 23 or/and ...
>>>[ number represents file size in kb OR mb OR ... ]
>>
>>You can if you use OTP, but OTOH your "keys" would need to be the same
>>size as your encrypted texts.
>
>Not at all. For example, I could encrypt 3 texts, of size 1k, 5k, and 10k,
>and if the resultant cyphertext file was 30k, I'd have plenty of room to
>hold them all. (Different bits of the cyphertext file code for the
>different plaintexts).
Explaining quite why a 1k plaintext encrypts to a 30k cyphertext
might keep you busy.
John
--
John Winters. Wallingford, Oxon, England.
The Linux Emporium - the source for Linux CDs in the UK
See http://www.linuxemporium.co.uk/
------------------------------
From: [EMAIL PROTECTED] (Paul Hsieh)
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical applications
Date: Mon, 10 Jul 2000 22:50:51 -0700
[EMAIL PROTECTED] says...
> "Terje Mathisen" <[EMAIL PROTECTED]> wrote:
> > I hope we all know that, but session setup is still important enough
> > that the server end, at least today, needs dedicated hw assist. The
> > problem is "simply" to make cpu cycles cheaper at a faster rate than the
> > WAN guys are increasing the bandwidth of their fibers, and as we
> > discussed a few days ago re. dense wavelength division multiplexing,
> > this is a tough task. :-)
> >
> > It does look like IA64, if not Merced, could be capable of doing this,
> > since it becomes feasible to keep even 2048-bit keys inside a range of
> > cpu registers.
>
> OK, but this brings up one of my questions about IA64. It appears that
> there is no carry flag and that the add instructions can't set a predicate
> bit if there is a carry (similarly for subtract / borrow). Wouldn't that
> help bignum addition and subtraction. I know you can get around it, but it
> seems a curious omission.
At the last IDF (Intel's Developer Forum) they presented some MMX code
for doing some bignum multiplies. Their approach was to use something
like 53 of the 64 bits so that the carries would propogate into the
unused bits. Either way, I don't see why they couldn't have optionally
used predicate bits for carries -- maybe they just ran out of instruction
bits or something (I haven't looked at it closely enough to figure this
out.)
--
Paul Hsieh
http://www.pobox.com/~qed/
------------------------------
** 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
******************************
