Cryptography-Digest Digest #187, Volume #12 Sun, 9 Jul 00 20:13:01 EDT
Contents:
Re: Random Numbers (John Savard)
Re: Proposal of some processor instructions for cryptographical (David A. Wagner)
Re: Proposal of some processor instructions for cryptographical applications
("Stephen Fuld")
Re: Proposal of some processor instructions for cryptographical applications
("Stephen Fuld")
www.curious.4ears ("rosi")
Re: Proposal of some processor instructions for cryptographical (Roger Schlafly)
Re: Random Numbers ("David Hyde")
Re: Random Numbers (John Savard)
Re: Advanced Cryptography FAQ ("Trevor L. Jackson, III")
Re: Random Numbers (Nicol So)
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Random Numbers
Date: Sun, 09 Jul 2000 22:15:41 GMT
On Sun, 9 Jul 2000 18:17:16 +0100, "David Hyde"
<[EMAIL PROTECTED]> wrote, in part:
>Does anyone know how to convert a random bit stream into random 16-bit
>numbers with uniform distribution?
As others have noted, taking 16 (or 15, if you only want to generate
positive integers) bits at a time from the random bit stream, if it is
genuinely random, will do just fine.
Is it random, but biased? Is it pseudorandom, and with correlations
between the bits? As the other replies have noted, one needs to know
what other factors make this other than a truly trivial question.
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.
Where you want to stop, and just throw away unusable results, depends
on how efficiently you want to convert the random bit stream to a
random digit stream.
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: [EMAIL PROTECTED] (David A. Wagner)
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: 9 Jul 2000 15:17:57 -0700
Iain McClatchie <[EMAIL PROTECTED]> wrote [excerpts only]:
> Why bother supporting cryptography in the CPU?
>
> - Hardware implementations of the speed-critical cyphers are _tiny_.
>
> - Popularly-used cryptographic algorithms change very slowly.
>
> - Connection speeds are increasing. Software encryption can keep
> up with a 56 Kb/s modem just fine, but a 10 Mb/s cable modem is
> a problem,
>
> - Popular cryptographic algorithms now appear to be exportable.
Those are good points. Still, there's a definite cost, and I wonder
how compelling a need there is for hardware crypto.
Until the AES is chosen, there's no obvious single candidate for hardware
implementation. Each crypto protocol has a different favorite cipher
(SSL -> RC4; IPSEC -> DES; SSH -> IDEA). That will likely change some
years after after the AES is chosen, but even so, I'm not convinced
there's a compelling need for hardware implementation. No matter which
AES candidate is chosen, it is likely to run at about 20 cycles/byte,
so encrypting at even 10 Mb/s should take only something like 4% of the
CPU speed, if I'm not mistaken. Is that a significant enough burden to
justify hardware implementation?
If there is no utterly compelling need for hardware crypto, do you think
the advantages of hardware implementation will still outweigh the costs?
I'm truly interested in your thoughts.
------------------------------
From: "Stephen Fuld" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical applications
Date: Sun, 09 Jul 2000 22:29:41 GMT
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Thomas Womack wrote:
> > "Mok-Kong Shen" <[EMAIL PROTECTED]> wrote
> > > Transposition is one of the basic operations in cryptography.
> > Is it, any more? Having a look at the AES candidates, most of them
> > carefully refrain from calling for bit transpositions simply because
> > they're rather hard to implement.
>
> Whether the operation is basic is a different question from whether
> awkward support for it causes it to be underutilized.
>
> Transposition and substitution, sometimes under the names diffusion
> and confusion, are often considered basic cryptographic principles.
Sure, but I think the question is whether that transposition needs to be on
non-byte boundaries and thus hard for current processors (That is, those
without bit permute instructions.). I think AES shows that one can get very
strong and fast encryption without needing these extra instructions.
--
- Stephen Fuld
------------------------------
From: "Stephen Fuld" <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical applications
Date: Sun, 09 Jul 2000 22:29:42 GMT
"Terje Mathisen" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Stephen Fuld wrote:
> > While I agree with Terje that new interesting instructions are fun to
figure
> > out and give a "eureka" like feeling when you see how they speed up some
> > useful task, I think the trend in cryptography algorithms is away from
this
> > kind of requirement. Look at the requirements for AES (The US
Government's
> > replacement for DES as a federal standard). One of the requirements was
> > efficient implementation on current generation 32 bit systems (and also
on 8
> > bit smart card type processors). If you look at the actual submissions,
as
> > a result, they tend not to require this kind of thing. Some don't even
> > require a multiply instruction or data dependent rotates.
>
> Stephen, you're absolutely right re. AES.
>
> Since I (with 3 others) wrote the asm code for one of the original AES
> submissions,
Terje, I continue to be amazed with the things you have done. And you
presumably find time to do the stuff that Hydro pays you for!
>I know that the few (2?) submissions that couldn't be
> implemented efficiently, preferably with portable C code, got a big hit
> against them early in the process.
>
> Since these restrictions still allow for good cryptographic properties,
> while allowing a 5 year old cpu to keep up with full duplex 100 Mbit/s
> fast ethernet, the need for specialized crypto instructions will not
> increase.
>
> The one thing that's missing from the AES code is bignum arithmetic, for
> setup/authentication, but this is being adressed anyway.
Well, I am sure you know that AES, being for a DES replacement was for a
private key system where bignum isn't needed. This is where the big use of
cycles is as the public key stuff (needing bignums) is typically used only
for session key exchange, etc. with the bulk of the data using private key.
but you knew that :-).
--
- Stephen Fuld
>
> Terje
>
> --
> - <[EMAIL PROTECTED]>
> Using self-discipline, see http://www.eiffel.com/discipline
> "almost all programming can be viewed as an exercise in caching"
------------------------------
From: "rosi" <[EMAIL PROTECTED]>
Subject: www.curious.4ears
Date: Sun, 9 Jul 2000 18:44:26 -0400
WWW Puzzle for the Curious Ears/Years
--------------------------------------------------------
I sincerely hope some kind people who can get in touch with Andrew
Odlyzko of AT&T may kindly help me solve (or partially solve) the www
puzzle:
Where did my e-mail messages to Andrew go?
Whether there is something that prevents Andrew from telling me
of the receipt of my messages? and
Why?
If anybody can get some, I mean any, response from Andrew and let me
know, I would appreciate it very much. Thanks in advance.
(The following is the background and some details about the WWW
puzzle, in case there is at least one kind person who can help out
there)
I have been CURIOUS FOR YEARS (about the three W's). It was a number
of years ago when I finally decided to do something about the loose ends
in the sketchy ideas of mine in cryptography and thought that it might
not be a bad idea to discuss the matter with people prominent in the
field. I sent out a bunch of e-mail messages to people whose names one
sees often and whose articles one sees quoted frequently. It wasn't just
the hope of getting blessing, which in the eye of some (including me)
can be so important. I also wanted to make sure that I did not miss
something obvious. Besides, a one-man-shop can often carry ridiculous
stuff, and since in the years from the age of 10 or 11 till about 22,
I like so many of my contemporaries either had no schooling or no proper
schooling, the chance of errors and overlooks is so formidable.
Messages sent and I waited. I hoped for the best and prepared for the
worst. The best came.
Of all the people I sent e-mail messages to, three and APPROXIMATELY
a half actually replied! There were courteous reply, touching reply,
helpful reply (with direction to search for help), and above all one
from Andrew that I dreamt of getting. It was simply beyond what I
could have hoped!
One of the replies was from another highly respected, leading expert
in the field of cryptography. He suggested that I discuss the matter
with Andrew.
Over the years, the ideas of my cryptographic scheme has been
'leaked', some purposely by me to sci.crypt and I feel no need to
further elaborate here (but I know repetition never bores :)).
I summarized the main characteristics of my idea in the e-mail
message to Andrew, including the property of 'no equivalent zero-one
set'. Later, in the message detailing the basic idea, I also mentioned
in a vague and brief manner that the underlying problem (of one of the
most secure modes) is to:
Find all m >= 0 _valid_ subset sum(s) --- given a set
'of high density'.
In addition, I mentioned 'all-or-nothing' as a tweak so that the
expressed concern (perhaps unjustified) that it is very difficult to
build a viable scheme based on NPc problems may not be a
problem at all.
Anyway, Andrew replied, saying that if the construct does possess
(some of) the properties I claimed, the scheme would be of interest. I
was simply overwhelmed! (But he wanted details).
I immediately wrote back in a very brief, nevertheless complete
manner, which I believe could be understood by a layman and quite easy
for the major points I made to be sensed. To be redundant, let me give
it here in summary once more (in a form easiest to understand):
A subset sum problem.
Build two (compact) sets X and Y. For simplicity, let X, following
MH, be superinc in such a way that the subset sum of X allows
'noise' constructed by elements from Y.
Build an arbitrary mapping from the subset sums of X to certain
subset sums of Y, such that the elements from Y contributing
to the overall subset sum (of elements from both X and Y) can
be 'peeled off' as the (multiple of) elements from X are
identified and extracted (due to the superinc property of
the elements in X).
NOTE: In particular, Y needs not and should not be superinc, so
that we have set (union of X and Y) of high density. The
transformed X and Y will be what we conventionally call 'public
key'. As I mentioned earlier, the mapping can be sessional (as
being arbitrary within allowed range) and may be secret (for
semi-public mode).
I as well gave, in the e-mail to Andrew, an example of zero-one set to
start with the explanation of the idea. --- Such an example was also
posted to sci.crypt in reply to one of Trevor L. Jackson's messages in
our discussion of the topic. I here thank Trevor once more for the
wonderful discussion we had. --- By the way, I do not think I stated in
anyway to Andrew about the Quasi-Public notion or its realization. I did
however mention the concept of key-security in an extremely vague
fashion. Actually, I said something like: suppose it is key-secure.
Hours turned into days; days in to weeks; weeks into months; and now
it looks that time is of no consequence and the word 'history' replaces
as the better abstract notion. I never heard from Andrew again.
In the first few months that followed Andrew's reply, I realized that
I, one from a race sometimes seen as patient and reserved, had been too
exuberant in optimism. I followed up with a number of e-mails to Andrew
asking only that he let me know that he had indeed received my message
with the description of the scheme. That, in the end, was all I could
hope for. The void point in my inbox where I expected Andrew's reply has
since been crowded with the three W's.
--- (My Signature)
P.S.
I have no permission from any of the approximate 3.5 people to reveal
their names (Andrew did not permit me either). I am sorry to have to
mention Andrew's name. Logically, it is an NP-hard position :). Not
asking help this way, may mean that I keep on writing to Andrew asking
for permission. But I find it hard to find something less stupid. I, for
this reason, personally apologize to Andrew.
If anybody would be kind enough to help (asking Andrew in person
when seeing him, put it lightly if I may for example, whether his e-mail
address suddenly changed at that time to:
[EMAIL PROTECTED](.us)
for instance), please e-mail me at
[EMAIL PROTECTED]
or follow up on the post (whichever seems more appropriate). Thanks.
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Crossposted-To: comp.arch
Subject: Re: Proposal of some processor instructions for cryptographical
Date: Sun, 09 Jul 2000 16:13:02 -0700
"David A. Wagner" wrote:
> If there is no utterly compelling need for hardware crypto, do you think
> the advantages of hardware implementation will still outweigh the costs?
Perhaps something like characteristic-2 multiplies or a random
number generators. These are cumbersome without processor help.
The cryptosystems over GF(2^n) are much faster in hardware
than software. This is a drawback if you are using software
but worrying about dedicated hardware threats.
------------------------------
From: "David Hyde" <[EMAIL PROTECTED]>
Subject: Re: Random Numbers
Date: Mon, 10 Jul 2000 00:18:55 +0100
"David Hyde" <[EMAIL PROTECTED]> wrote in message
news:8kac12$nk2$[EMAIL PROTECTED]...
> Does anyone know how to convert a random bit stream into random 16-bit
> numbers with uniform distribution?
>
>
Sorry I left out some detail about the random bit stream. The bit stream
has been generated from a white noise source I built from a zener diode, a
couple of op-amp stages and a comparator. Although the bits produced are
independent of each other, there is a bias that can't be removed by
adjusting the dc mean level of the noise. Therefore I was asking if there
is a way of processing the bit stream to produce 16-bit random numbers with
a uniform distribution?
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Random Numbers
Date: Sun, 09 Jul 2000 23:16:58 GMT
On Sun, 09 Jul 2000 22:15:41 GMT, [EMAIL PROTECTED]
(John Savard) wrote, in part:
>Let's say you want to convert a stream of bits into uniformly
>distributed numbers from 0 to 999.
As often happens when I explain something interesting in a USENET
post, I make it the basis of an added page in my web site. The page
that deals with this method of base conversion is at
http://home.ecn.ab.ca/~jsavard/crypto/mi060305.htm
John Savard (teneerf <-)
http://www.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
Date: Sun, 09 Jul 2000 19:54:16 -0400
From: "Trevor L. Jackson, III" <[EMAIL PROTECTED]>
Subject: Re: Advanced Cryptography FAQ
There you go again, assuming your conclusions. Compare your checklist to the
Snake Oil FAQ. You'll find an uncomfortable number of matches.
[EMAIL PROTECTED] wrote:
> -------------------------------------------------------
> Advanced Cryptography FAQ (Frequently Asked Questions)
> -------------------------------------------------------
>
> The purpose of this FAQ is to inform the cryptographic community of
> future (advanced) directions in the field of encryption as we
> move into the new age of speedy computers and vast internet
> interconnectivity.
>
> -------------------------------------------------------
> Table of Contents:
> 1. What is cryptography?
> 2. What is wrong with it?
> 3. What is the solution to fixed keys?
> 4. What is the solution to fixed algorithms?
> 5. What is the solution to fixed symbols?
> 6. How is the internet going to change cryptography in the future?
> 7. What algorithms out there is going to take us there?
> 8. Where can I find documentation on Base Encryption?
> 9. Is it true Base Encryption is revolutionary?
>
> -------------------------------------------------------------------
>
> 1. What is Cryptography?
>
> Cryptography is the study of encryption and its related components.
>
> ---------------------------------------------------------------------
> 2. What is wrong with it?
>
> The current state of encryption these days have an inherent weakness
> in that they are based on static keylength, static operators and
> operations (algorithms), and a static symbol set (base).
>
> ---------------------------------------------------------------------
>
> 3. What is the solution to fixed keys?
>
> Dynamic length keys that cannot be permutated through.
> ---------------------------------------------------------------------
>
> 4. What is the solution to fixed algorithms?
>
> Dynamic algorithms that are not fixed, so you can't attempt to
> crack and find weaknesses in it like a cypherblock.
>
> ---------------------------------------------------------------------
> 5. What is the solution to fixed symbols?
>
> Dynamic symbol sets (base). Not knowing the base of a cyphertext
> or plaintext prevents any initial basis for attacks.
>
> ---------------------------------------------------------------------
> 6. How is the internet going to change cryptography in the future?
>
> The beginning of the computer industry started on mainframes and black
> boxes that you put things into and obtain result. This provided the
> start of many-to-one relationships between user and machine. As more
> people wanted access to the machine, they either formed queues or
> placed their computational inquiries into tickets to be batch processed
> by the mainframes. This eventually led to dumb clients and smart
> servers. But as things goes, some people wanted more power in their
> clients (why do I always need to
> connect to the mainframe?). This led to client-server
> architectures, and the boom to Solaris OS and Windows NT.
> (but usually the servers just host the filesystem or some
> critical database). As things started picking up and people started
> using their POWERFUL clients (PCs), the internet exploded. Basically
> the powerful servers that the clients communicated with got
> replaced by websites. Now everything is stored on the internet
> and your PC became a dumb client again (just a browser to browse the
> internet). Well, you know how things go... what goes around comes
> around. History repeats itself. So the browsers (dumb clients) became
> more powerful and then had the ability to run applications (java
> applets and ActiveX controls), and do client-side scrypting
> (javascript, Vbscript). Organizations like XML are popping up
> to allow you to do client-side manipulation and rendering.
> Do you know what this trend leads to?
> Yes you guessed it... Client-side webservers. There will be more
> powerful clients to the point where anyone with an internet connection
> can use their browser to host data dynamically (without a registration
> with DNS, or a dynamic way to register on the fly). This is
> basically to balance out the powerful webservers. As clients
> become internet-aware, they will serve as producers (not just
> consumers of the internet like they are now).
>
> The ability to use a website as a cryptographic
> primitive is beginning to take shape. We already have webservers
> dedicated to servicing authentication (verisign is one). There
> are also servers connected to the internet that provided kerberos
> authentication (built in most NT machines these days).
>
> But the question comes to mind... Is it possible to use
> webpages in hierarchical or maybe random order as a cryptographic
> primitive? Absolutely. Most computers communicate
> on the TCP/IP channel through ports. There are special ports
> that are dedicated to serving certain types of traffic. They
> are simply numbered... It happens that telnet uses one port
> and http (the browser protocol) uses another. There are thousands of
> these ports. You can simply make one up and communicate through it
> using any protocol you want. Well, why not use http protocol as the
> default protocol? Why not? The data can be in static
> webpages or dynamically generated via asp, perl, or cgi programs.
>
> The order of the links between webpages (if you want to use
> w3c xhtml 4 conforming pages) can serve as indices to other
> algorithms or segments of the cyphertext (base encryption
> can utilize this concept mind you).
> There are too many ways this can be approached.
>
> Some questions that gives new directions...
> Why does the cypherblock need to be on my local machine?
> Why do I need to use a cypherblock?
> Why not utilize webservers?
> Why not use multiple webservers?
> Why not utilize the whole internet as my algorithm?
>
> See below...
>
> ---------------------------------------------------------------------
> 7. What algorithms out there is going to take us there?
>
> Base Encryption. Its the most revolutionary encryption algorithm
> in existence.
> ---------------------------------------------------------------------
>
> 8. Where can I find documentation on Base Encryption?
>
> http://www.edepot.com/phl.html
>
> ---------------------------------------------------------------------
> 9. Is it true Base Encryption is revolutionary?
>
> Yes. It utilizes the concepts of dynamic keys, dynamic algorithms,
> dynamic base (symbol set), and many other advanced concepts that will
> take cryptography into the future. It breaks new ground and just
> now are the community realizing its revolutionary impact on the
> world.
>
> Many people are now broken up into two groups...
>
> 1) Those that want to have something (anything!!!) to do with it
> to steal credit or get some personal gain as base encryption
> revolutionizes the cryptography world.
> 2) Those that are attacking it.
>
> For people in group 1), there is nothing much to say but thanks
> for confirming your acceptance of my revolutionary invention,
> and no you don't get credit for it. Simply do a deja.com search
> and you will find my invention was created in 96 (the time
> virtual calc was made).
>
> For people in group 2), here are some interesting tidbits...
>
> Many people are not able to think outside of the box.
> They are limited by what they know, and are accustomed to. Its
> like the old story about the young elephant being tied with a
> weak chain, and later in life thinks he can't break it (even
> though he IS able to do it as an adult).
>
> The first rejection of new concepts usually starts with violent
> and aggressive attacks. This is the customary reflex response to
> protect the familiar. It is an instinct inborn in most animals
> against predators. For example, most fishes swim in schools. Most
> animals (with the exception of primarily hunters like lions) gather in
> groups. When things out of the ordinary (a new species encountered)
> happens upon the group, they will all retreat or attack. This is in
> response to the group's need to survive (we are surviving ok without
> this new species, so as a group we want to keep things the same, and
> this new specie is interrupting this balanced stability). Think of the
> spanish inquisition, and the death of many astronomers.
>
> In a similar sense, if you are able to think outside of the box, you
> will realize that what you reject most is usually what you
> are most afraid of, or have least experience in. It is the ego
> of the mind to assure itself that the paradigm that it has built up to
> label and categorize the world is correct. Once a person
> has spent a long time and effort on something, it would hurt to find
> that what they studies was basically wrong or useless.
>
> As for Base Encryption, for those that have read it, it simply
> broke their traditional textbook trained mind. They are afraid to
> admit that it is true. People started asking for source code. They
> could not find a fault with it. They simply just attacked with no
> coherent reason why they are
> rejecting it other than that it was different, and anything different
> can't be right... can it?
>
> Many have failed to even try to attack it because they can only
> think in traditional ways learned from traditional textbooks
> (fixed keylength and fixed algorithms confined in a cypherblock).
>
> Base Encryption breaks new ground and provides future directions
> for cryptography.
>
> The whole base encryption can be found at
> http://www.edepot.com/phl.html
> There is also a tool that can be used to test encrypting and decrypting
> of messages there: Virtual Calc 2000.
>
> Sent via Deja.com http://www.deja.com/
> Before you buy.
------------------------------
From: Nicol So <[EMAIL PROTECTED]>
Subject: Re: Random Numbers
Date: Sun, 09 Jul 2000 20:02:01 -0400
Reply-To: see.signature
David Hyde wrote:
>
> Sorry I left out some detail about the random bit stream. The bit stream
> has been generated from a white noise source I built from a zener diode, a
> couple of op-amp stages and a comparator. Although the bits produced are
> independent of each other, there is a bias that can't be removed by
> adjusting the dc mean level of the noise. Therefore I was asking if there
> is a way of processing the bit stream to produce 16-bit random numbers with
> a uniform distribution?
If the sampled bits are independent and identically distributed, you can
correct the bias using a procedure attributed to von Neumann:
repeat
generate two random bits b1, b2;
until b1 <> b2;
output b2;
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.
If you choose to use a cryptographic hash function, which generally
outputs >= 128 bits, I'd suggest the following. Let N be the length of
the output of the hash function. Collect enough samples to have >= N
bits worth of randomness, then do the hashing. Divide the hash value
into 16-bit chucks.
A word of caution, that the samples are independent cannot be taken for
granted. At a minimum, you need to take measurements and perform
analysis to confirm it.
--
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.
------------------------------
** 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
******************************
