Cryptography-Digest Digest #724, Volume #12 Wed, 20 Sep 00 12:13:00 EDT
Contents:
Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption [an (Mok-Kong Shen)
Re: Hamming weight (Mok-Kong Shen)
Re: On secret Huffman compression (Mok-Kong Shen)
Re: Hardware RNGs ("ScottD")
Re: Parity Checking in DES (Mok-Kong Shen)
Re: Parity Checking in DES (Brian Boorman)
SUN SPOT 6.51 BILLION square kilometers in size ([EMAIL PROTECTED])
Re: CDMA tracking (was Re: GSM tracking) (Craig Paul)
Re: Tying Up Loose Ends - Correction (Tim Tyler)
Re: Tying Up Loose Ends - Correction (Tim Tyler)
Re: Hardware RNGs (Mark Carroll)
Re: RC4: Tradeoff key/initialization vector size? (John Myre)
Re: RSA Questions ([EMAIL PROTECTED])
Re: Known Plain Text Attack (Tim Tyler)
Re: One-way encryption (Tim Tyler)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Quasi Algorithms / Quasi Functions and Polymorph Encryption [an
Date: Wed, 20 Sep 2000 13:52:56 +0200
John Savard wrote:
>
> Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
> >Polymorphism has been known in computer science since
> >decades, though much popularized only after C++. Already
> >in Algol68 one can use a datatype 'union' such that at
> >runtime one can obtain first the type and then the value
> >of an object and with these determine what is to be
> >computed next. Polymorphic Types have been much studied
> >by researchers of the functional languages.
>
> I think that almost the only connection between that and the form of
> encryption under discussion is the use of the same word.
Actually not. He uses the data (at runtime dynamically)
to determine via a case-construct what the function
(at a particular step) should do. In programming, a
polymorphic function is one such that the code queries
the type and/or the value of certain input arguments
and uses that information to determine what is to be
done. In this way, one has only one function name
(instead of a bunch of these each for a different one)
to stand for a whole class of (more or less similar)
functions. That is polymorphism as the term is used in
CS. If a cipher designer indends to exploit variability
at some small granuality level, this programming
paradigm would naturally come to his mind in
implementation. (I myself once thought of letting PRNG
to determine in one of my humble cipher designs whether
xor or modular addition is to be done in certain steps,
but I finally decided to leave that out, considering
that my design already has enough variability and
achieving more 'complexity' for the opponent via adding
more code is not worthwhile in that case. My design
is PRNG driven, i.e. everything is controlled by PRNG
and there is feedback from the result of processing to
the PRNG, thus there is ample variability in my viw.)
So what the original poster does is nothing new at all
from the standpoint of programming. His explicitly
pointing out (stressing) the advantage of using
polymorphism (because of increase of variability) may
on the other hand be considered 'new' in the sense
that he calls one's attention to polymorphism as a
general technique useful in crypto design and
implementation. As you pointed out, you and several
others have earlier employed certain polymorphic
constructs.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Hamming weight
Date: Wed, 20 Sep 2000 13:53:04 +0200
kihdip wrote:
>
> Francois Grieu answered that the Hamming weight was only depending on the
> binary representation.
> The Hamming weight of 19 is thus 3 (2^4, 2^1 and 2^0).
>
> If it's applicable to other bases shouldn't 19 have a weight of 2 (1*10^1
> and 9*10^0) ??
The 'basic' definition is the Hamming distance, which
it the number of unequal pairs of the corresponding
elements of two vectors. From that one 'derives' the
definition of Hamming weight of a vecter, which is
the Hamming distance between that vector and the zero
vector. If by using a different base you are thinking
of obtaining a different vector (the elements are no
longer of 1 bit), then you could have a different
Hamming weight than in the binary case. I am unaware
of practical use of Hamming weight in this way, however.
On the other hand, Hamming distances between vectors
whole elements are arbitrary (i.e. not necessarily 1
bit) are commonplace.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: On secret Huffman compression
Date: Wed, 20 Sep 2000 14:06:53 +0200
Tim Tyler wrote:
>
> IIRC, I've mentioned before the possibility of an attacker using
> known-plaintext at the start of the message to extract much of the
> Huffman tree. *If* you can get the whole tree, it seems likely that it
> will be possible to recover the PRNG stream - which can be used to send
> forged messages (in the absence of a signature scheme).
>
> While the above description doesn't offer a detailed algorithm, ISTM
> that it's likely to suffer from this type of known-plaintext attack.
>
> My memory is hazy - but I believe multiple passes in opposite
> directions was one of the methods proposed to deal with this issue
> the last time around.
I mentioned in the original post that the unmodified
Hamming tree is assumed to be known to the opponent.
That's is of course an assumption on the safe side.
So the only difficulty assumed is that of obtaining
the modified tree. That's certainly not terrifically
hard. On the other hand, the scheme is mainly for
compression, not for proper encryption. The difficulty
introduced by modifing the tree should however be more
than enough to compensate the disadvantage of not
having 1-1 in my humble view. In a follow-up, I
mentioned that, if the (unmodified) tree is sent, then
it is to be sent encrypted. Again, this is only some
extra safety measure, avoiding so to say putting
things right into the hands of the opponent.
M. K. Shen
------------------------------
From: "ScottD" <[EMAIL PROTECTED]>
Subject: Re: Hardware RNGs
Date: Wed, 20 Sep 2000 07:05:21 -0500
Correct, it is in the firmware hub:
http://developer.intel.com/design/chipsets/datashts/290658.htm?iid=PCG+810bl
ue&
"Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Paul Rubin wrote:
> > Isn't the Pentium III supposed to come with an RNG built into the
> > chip set?
>
> Last I heard, it was in one of the support chips, not the processor.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Parity Checking in DES
Date: Wed, 20 Sep 2000 14:22:52 +0200
Brian Boorman wrote:
>
> Does anyone know what the parity checking algorithm is that is used on
> hardware implementations?
>
> The basic information I have is that the parity bits are stored in a
> register, and fed into a parity tree along with bits from the C register
> during rounds 10 & 11 and bits from the D register during rounds 12 &
> 13. Somehow this ends up in a parity register that reads "0111" if the
> parity is ok, any other pattern is an error. I have not been able to
> find any other details. It is not in the FIPS pubs other than a listing
> of interface lines for the NIST hardware module that shows a parity
> error output.
Maybe I misunderstood, since I barely have hardware
knowldege. But isn't it that the parity bits consist
of one bit from each byte of the key? That is, the
8th bit is the parity of bits 1 through 7, etc.
As long as your hardware gets that right, isn't it o.k.?
(Note that DES counts bits from left to right, starting
from 1.)
M. K. Shen
------------------------------
From: Brian Boorman <[EMAIL PROTECTED]>
Subject: Re: Parity Checking in DES
Date: Wed, 20 Sep 2000 12:49:28 GMT
In article <[EMAIL PROTECTED]>,
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
>
>
> Brian Boorman wrote:
> >
> > Does anyone know what the parity checking algorithm is that is used
on
> > hardware implementations?
> >
> > The basic information I have is that the parity bits are stored in a
> > register, and fed into a parity tree along with bits from the C
register
> > during rounds 10 & 11 and bits from the D register during rounds 12
&
> > 13. Somehow this ends up in a parity register that reads "0111" if
the
> > parity is ok, any other pattern is an error. I have not been able to
> > find any other details. It is not in the FIPS pubs other than a
listing
> > of interface lines for the NIST hardware module that shows a parity
> > error output.
>
> Maybe I misunderstood, since I barely have hardware
> knowldege. But isn't it that the parity bits consist
> of one bit from each byte of the key? That is, the
> 8th bit is the parity of bits 1 through 7, etc.
> As long as your hardware gets that right, isn't it o.k.?
> (Note that DES counts bits from left to right, starting
> from 1.)
>
> M. K. Shen
>
That is what the parity bits are. A certain LSI chip used in a certain
Multi-Chip Module used in certain US Government equipment has an
algorithm that checks the parity during each run to verify the key was
not corrupted. Remember that radiation in certain enviroments (space
orbit for example) can cause the little electrons that represent bits to
get confused.
I am looking for someone who has details of the parity checking
algorithm used in these hardware modules, as I only have the above
information and need to duplicate this circuit.
--
Brian C. Boorman
Senior Engineer
Harris RF Communications
Rochester, NY 14610
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED]
Crossposted-To: sci.military.naval,alt.conspiracy,sci.geo.earthquakes
Subject: SUN SPOT 6.51 BILLION square kilometers in size
Date: Wed, 20 Sep 2000 14:04:11 GMT
WARNING:
[to satellite operators, submarines, polar explorers, underwater
expeditions, airports]
>===== Original Message From Cary Oler <[EMAIL PROTECTED]> =====
A s t r o A l e r t
Sun-Earth Alert
Solar Terrestrial Dispatch
http://www.spacew.com
20 September 2000
* One of the Largest Sunspot Groups so far comes into View *
* Potential Major Solar Flare Warning *
POTENTIAL NAKED-EYE SUNSPOT
On 20 September, one of the largest sunspot groups to be observed
so far
this solar cycle began rotating into view around the eastern limb of
the Sun.
The enormity of this region was never fully realized until today. This
sunspot group currently measures 6.51 BILLION square kilometers in
size. That
is large enough to map the entire surface area of the Earth within the
space
occupied by the sunspot complex almost 13 times over! In fact, this
sunspot
group is so large that people equipped with eye protection may be able
to
spot the sunspot complex with their naked eyes.
DO NOT ATTEMPT TO VIEW THIS SUNSPOT WITHOUT ADEQUATE EYE
PROTECTION! YOU
COULD PERMANENTLY DAMAGE YOUR EYES!
This sunspot will gradually rotate across the face of the visible
Sun
over the next 11 to 12 days. It will be optimally placed for spotting
with
the naked eyes between approximately 21 through 26 September.
This sunspot complex has the size and the magnetic complexity to
produce very energetic solar flare activity.
Major class M and even large X-class solar x-ray flares are often
observed
from sunspot groups that are as large as this region is.
The potential exists for major levels of solar flare
activity from this spot complex over the next several days to perhaps
throughout much of the next 12 days if the region maintains its size and
complexity.
http://www.spacew.com/astroalert.html
In article <[EMAIL PROTECTED]>,
[EMAIL PROTECTED] (Brian Allardice) wrote:
> In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED]
says...
> >
> >
> >
> >[EMAIL PROTECTED] wrote:
> >>
> >[snip]
> >
> >Please kindly don't cross-post to sci.crypt stuffs
> >that have nothing to do with cryptology. Thanks.
>
> For shame! You have failed to correctly decrypt a very important
message!
> You must try harder!
>
> Cheers,
> dba
>
>
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Craig Paul)
Subject: Re: CDMA tracking (was Re: GSM tracking)
Date: 20 Sep 2000 09:18:29 CST
In article <[EMAIL PROTECTED]>, Roger Schlafly
<[EMAIL PROTECTED]> writes:
> Jerry Coffin wrote:
>> IIRC, it receives, but does not normally transmit.
>
> Suppose I live in Calif, and I drive to Vegas and back with
> my CDMA phone in the car. With live batteries but turned off
> the entire time.
>
> Is there any electronic evidence that I left Calif?
Nope.
> You say
> the phone doesn't transmit while off, but conceivably it
> could keep a record of where I have been and report it the
> next time the phone is turned on or there is a live connection.
I think there're too many assumptions that the phone is even active,
at all. If it's off, it should really be "dead".
The thread started out with some inaccuracies.
If the phone is on, but nobody's making a call, but the phone needs to
change base stations, there will be traffic between the phone, the
base station it is on, and the base station that is a candidate for it
to switch to.
So, in a course manner, you could be tracked (to within the footprint
of the base station's coverage area).
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Tying Up Loose Ends - Correction
Reply-To: [EMAIL PROTECTED]
Date: Wed, 20 Sep 2000 14:44:13 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
: "SCOTT19U.ZIP_GUY" wrote:
:> I guess you just don't seem have the ability to understand
:> your method sucks. Having a EOF is just plain waste. It is added
:> info that is not needed. [...]
: If my message is over one hundred bytes, do you think
: that I need to care about wasting 5 bits?? [...]
At worst, this can reduce the size of keyspace by a factor of 32.
It might make the difference between an analyst looking at 32 different
possible messages, and one unique one.
Of course, whether you consider this sort of thing to be potentially
important is up to you.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Namaste.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Tying Up Loose Ends - Correction
Reply-To: [EMAIL PROTECTED]
Date: Wed, 20 Sep 2000 15:03:10 GMT
John Savard <[EMAIL PROTECTED]> wrote:
: I think that trying to remove redundancy as far as possible is a good
: idea. While I disagree with Mr. Scott on one detail on his 1-1 scheme []
It seems that any technique which takes a bitstreams and converts them
reversibly to files of 8-bit bytes will exhibit some statistical
anomolies, of the type I believe you're objecting to.
Any system which attempts to avoid such artefacts completely seems
obliged to use some sort of random padding.
John's scheme proposes adding such padding after coompressing, and before
encryption.
An alternative - which I've not seen discussed on this forum - would be
to use an encryption device which is capable of encrypting variable length
bitstrings, and is not confined to multiples of 8 bits. I attribute this
idea to David Scott.
Indeed - if dealing with the output of an arithmetic compressor, files
of a fractional number of bits in length are also possible - i.e. a
message may be 10.5 bits long.
After the compresssed file is encrypted, it can be safely padded out with
zeros, to a byte boundary without any security concerns. If you want to
obscure the length of the file from your adversary, as much random padding
as you like can be used at this stage.
It seems that this would removes concerns of known plaintext occurring as
a result of padding with zeros (or padding with less-than-random "random"
data).
The downside, appears to be that most modern block cyphers can't easily
handle arbitrary-length files (unless you use them as stream cyphers
in OFB mode, or something).
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
From: [EMAIL PROTECTED] (Mark Carroll)
Subject: Re: Hardware RNGs
Date: 20 Sep 2000 15:20:50 GMT
In article <[EMAIL PROTECTED]>,
Paul Rubin <[EMAIL PROTECTED]> wrote:
>[EMAIL PROTECTED] (Mark Carroll) writes:
>
>> Can anyone recommend any relatively cheap RNG cards for Intel boxes?
>
>Isn't the Pentium III supposed to come with an RNG built into the chip set?
Unfortunately, this increases the cost a lot for me - something I can
just plug into an ISA or PCI slot in my current machine would be
perfect.
>Failing that, I believe the Java iButton has an RNG available.
>See http://www.ibutton.com/ibuttons/java.html.
That seems to do an awful lot of on-board processing, though. ):
Maybe I should have been clearer: I'm looking for something that plugs
in as a card, and from Linux lets me access reasonably raw data
regarding some random physical process that's going on in the device.
Perhaps I'm wanting something that doesn't exist, though?
-- Mark
------------------------------
From: John Myre <[EMAIL PROTECTED]>
Subject: Re: RC4: Tradeoff key/initialization vector size?
Date: Wed, 20 Sep 2000 09:31:25 -0600
"David A. Wagner" wrote:
>
> In article <8q8dao$85j$[EMAIL PROTECTED]>, <[EMAIL PROTECTED]> wrote:
> > It is far from clear that hashing the user key improves the security of RC4.
>
> It's pretty clear to me! Look, for instance, at Andrew Roos'
> weak-key and related-key attacks on RC4 for examples of why you should
> feel concerned about applications that don't pre-hash their RC4 keys.
Do those attacks work on ASCII keys? IIRC there was something
about needing a pair of key bytes summing to 256, and Ciphersaber
uses (assumes?) ASCII keys because of this.
JM
------------------------------
From: [EMAIL PROTECTED]
Subject: Re: RSA Questions
Date: 20 Sep 2000 11:46:55 -0400
Bryan Olson <[EMAIL PROTECTED]> wrote:
> The modulus must be the product of distinct primes for
> encryption to be invertible.
That is, when e is relatively prime to phi(n), for the map:
y=x^e mod n
To be 1-1 from the integers from 0 to n-1.
HOWEVER:
For x relatively prime to n, the map will be 1-1 even if n is not square
free.
IF THERE IS ANYTHING EXCEPT A NEGLIGIBLE/INFINITESIMAL PROBABILITY THAT
THIS COULD OCCUR (i.e. one might pick an x which is not relatively prime
to n: say, once out of 100 billion times) THEN THE MODULUS IS (at least
partially) INSECURE AND YOU SHOULD USE A DIFFERENT ONE.
Why? Well, just randomly generate x's until GCD(x,n)>1 (generating and
testing a billion cases is not "much work"). Then GCD(x,n) is a factor of
n and you have partially factored n.
(if n is the product of primes, p1, p2, etc ... to various
powers: n=p1^a1*p2^2*... then the percentage of numbers from 0 to n-1
which are NOT relatively prime to n is 1-(1-1/p1)(1-1/p2)...
If there are, say, six primes, each at least as large as, say 256 bits
(2^256) - even with powers larger than one - the percentage of numbers
not relatively prime to n is no larger than 1-(1-2^-256)^6 (that is,
about 6/2^256 that is, on the order of 10^(-76). This is negligible. That
is, don't worry about it. But ... repeated prime factors may lead to
other weaknesses in factoring the modulus...)
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: Known Plain Text Attack
Reply-To: [EMAIL PROTECTED]
Date: Wed, 20 Sep 2000 15:40:44 GMT
Terry Ritter <[EMAIL PROTECTED]> wrote:
: sci.crypt [EMAIL PROTECTED] (Mark Wooding) wrote:
:>Terry's put together a great deal of really useful information. He also
:>explains clearly which techniques he's patented, which lets you avoid
:>them. [...]
: Patents support the business of research. If someone imagines that
: academic research is all we need, I guess they must support the
: limitations on crypto possibilities that academia enforces.
It's not very clear which limitations you're talking about. That research
is only done by qualified individuals, who can put togerther budget
proposals?
: Somebody has to pay for work, or that work cannot continue. If one
: could just walk out of a store without paying for a can of beans,
: there soon would be no beans, or no store, which is exactly what NSA
: wants. [...]
Financing is important - but patents are not the /only/ way to make
money from cryptography. If you develop well-known algorithms, I'm
sure the demand for your services as a security consultant increases.
: Cryptography is not about sharing; we can call it privacy, but
: whatever we call it, the basis of cryptography is the exact opposite
: of free sharing with everyone. Cryptography is about keeping from
: others; cryptography is conflict; cryptography is war.
Well put.
: And AES is not about making cryptography free for users; it is instead
: a way to give manufacturers a component without which they would have
: had to support independent cryptographic research.
You can see why the manufacturers will like it. Cryptography is
practically free for users anyway. You can't make much money by
selling cryptographic algorithms these days anyway, AES, or no AES.
There are too many good free ones available.
: What is really embarrassing to me about all this is the lack of
: academic research which would place my work in a proper context.
There does seem to be a lack in this area - I don't see your work
discussed much in academic papers - and the material seems to me to merit
discussion. Perhaps this is partly because you've patented much of the
material - and academics often hate patents.
: That lack is nothing less than an inherent and appalling criticism of
: academia itself. The lack of action reveals what academic goals
: really are, as opposed to what society might like them to be.
Perhaps it does reflect badly on academia. Perhaps people hesitate to
refernece your work because of the publishing medium.
However, there are probably other interpretations. Perhaps cryptography's
a big field, with plenty of areas to work on, so the fact that nobody's
treading on your toes doesn't mean much. Perhaps they think you've
already covered the areas in question fully. Or perhaps they think your
work is worthless :-(
I expect patent fear comes into it. Researchers' choice of area is
no-doubt influenced by the possibility of publishing new material in the
area that comes to have commercial significance. If publications in the
area lead to designs components of which have been previously patented,
and might incur royalties/lawsuits, that's a concrete, financial
discouragement.
: Our goal ought to be to have a competitive industry of cryptography
: which can support its own research out of profits. But that would mean
: somebody actually would have to pay for a cipher.
I think cryptography's such an interesting area that people will work in
it anyway. After all, there is plenty of money to be made in related
fields: if you make famous contributions to the field, you can consult for
security firms, or even write your autobiography and expect some sales.
The field is a little like the field of making pop music. Lots of people
want to do it, and few wind up making much money at doing it. The
competition is fierce - and people aren't afraid to give things away
in order to become well known.
: I suppose it is only to be expected that there would be oh-so-much
: concern about patents, and relatively little concern about the real
: issues before us. Presumably our opponents appreciate the irony.
AFAIK, none of the material you've published about cypher stacks
is yet the subject of patents.
I would agree that issues relating to changing one's cypher system in the
face of active attackers is of great significance. Congratulations for
identifying the issue clearly, and promoting its discussion.
--
__________ Lotus Artificial Life http://alife.co.uk/ [EMAIL PROTECTED]
|im |yler The Mandala Centre http://mandala.co.uk/ Breast is best.
------------------------------
From: Tim Tyler <[EMAIL PROTECTED]>
Subject: Re: One-way encryption
Reply-To: [EMAIL PROTECTED]
Date: Wed, 20 Sep 2000 15:57:12 GMT
[EMAIL PROTECTED] wrote:
: On the other hand, MD5 and SHA-1 are both standard portions of the
: Java 2 platform, so the task of encrypting passwords with either of
: them is even easier.
SHA-1 is included in the JCE - but not in the JDK, or in the JRE, AFAIK.
According to http://java.sun.com/products/jce/jce12_faq.html
``JCE 1.2 is export-restricted, meaning that it can be downloaded only
from within the U.S. or Canada.''
--
__________ http://alife.co.uk/ http://mandala.co.uk/
|im |yler [EMAIL PROTECTED] http://hex.org.uk/ http://atoms.org.uk/
------------------------------
** 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
******************************
