Cryptography-Digest Digest #483, Volume #13 Wed, 17 Jan 01 16:13:01 EST
Contents:
Why Microsoft's Product Activation Stinks (zapzing)
Re: Q: split keys (Mike Rosing)
Re: rubik's cube (Tony L. Svanstrom)
Re: Why Microsoft's Product Activation Stinks ("Mysterion")
Re: Why Microsoft's Product Activation Stinks ("Kristopher Johnson")
Re: RC5 on 16 word? (Simon Johnson)
Re: RC5 on 16 word? ("N. Weicher")
NTRU Public Key System as a knapsack cryptosystem (John Bailey)
Re: RC5 on 16 word? (Tom St Denis)
Re: SAC question (Tom St Denis)
Re: future trends in asymmetric cryptography (Dido Sevilla)
Re: A Small Challnge (fred weigel)
Re: block algorithm on variable length without padding? ("Joseph Ashwood")
Re: RC5 on 16 word? ("Joseph Ashwood")
----------------------------------------------------------------------------
From: zapzing <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,misc.survivalism
Subject: Why Microsoft's Product Activation Stinks
Date: Wed, 17 Jan 2001 18:23:52 GMT
Upcoming versions of windows may have, I
read, something called "product activation".
This means that you must call up microsoft
so that the OS can have permission to run.
I have a few questions about this. First of
all, under what conditions will MS
*refuse* to activate the product. It seems
to me that if they never refuse activation,
then putting in product activation code is
pretty useless. And if they do, they may
deny legitimate users who reconfigure their
systems frequently.
Also, what about the possibility of a major
computer virus that requires many machines
to restore. This would of course require
that the OS be reactivated, but in that case
the product reactivation lines could be
jammed. This would make me think about it
very carefully before I bought an OS that
included product reactivation code.
I understand MS's desire to protect their
intellectual property, but please try to think
of something that will not cause the collapse
of civilization.
--
Void where prohibited by law.
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Mike Rosing <[EMAIL PROTECTED]>
Subject: Re: Q: split keys
Date: Wed, 17 Jan 2001 12:24:57 -0600
Andy Resnick wrote:
>
> As many of you may know, Newsweek had an article about the history of
> cryptograpy, and had (for me, anyways) an unusually clear explanation of
> how public/private key encryption works. I'm no expert. My question
> is, does the use of two keys imply that there is more than one
> transformation to properly decode an encrypted signal? That is, I
> recieve an signal encoded with (for example) PGP. Now, I'm too lazy to
> get the public key but I have infinite computing power (hey, this is a
> thought experiment!). It seems that I will find *two* keys to decrypt
> the message, and I have a hunch that they will be based on the two
> primes that factor a large number.
>
> Am I somewhat on the right track here?
Not quite. There are really 2 levels of encryption in real world settings
like PGP. The outer level uses public keys. The inner level uses regular
symmetric key, like IDEA or the new AES. The outer level encrypts the
session key and the session key encrypts the message (inner level).
For you to decrypt a message you only need your own private key. Other
people have to find your public key to send you a message. They use
a session key (some random garbage) to encrypt the message, then use
your public key to encrypt the session key.
The outer level uses "hard" problems to hide the inner level key. The
inner level uses non-linear bit banging, and has nothing to do with
factoring. One could in principle solve a set of equations to find a
session key, but it would probably take longer than a brute force trial
and error method.
Patience, persistence, truth,
Dr. mike
------------------------------
Crossposted-To: comp.security.pgp.discuss
Subject: Re: rubik's cube
From: [EMAIL PROTECTED] (Tony L. Svanstrom)
Date: Wed, 17 Jan 2001 18:35:51 GMT
[Followup-To: sci.crypt]
Gateway #3 <[EMAIL PROTECTED]> wrote:
> Do you know of works that consider encryption based on the Rubik's Cube ?
> (I mean in terms of evaluation). I am by no means a crypto expert
This doesn't really belong in comp.security.pgp.discuss, try sci.crypt
instead.
> but i would like to know the state of the art regarding this technique of
> permutation as an encrypting device:
>
> * broken
> * weak
> * probably weak
> * unknown
>
> Of course, cube size and key size may influence it.
>
> It APPEARS to be interesting, given the extraordinary number of combos you
> can generate with SHORT KEYS. Besides, it's also very FAST, much faster than
> DES-like algos for instance.
>
> But all this may be deceitful if papers report that it's easy to break.
>
> And intuitively, i think that cryptanalysis is harder when you "move from 2d
> to 3d"
> (operations are perfomed accross 3 axes, whereas DES-like is pure 2d).
> In the field of computational geometry for instance, there is a big gap
> between
> 2d and 3d in complexity analysis, algorithm design.
>
> It is not that easy to think in higher dimensions, thus dimension elevation
> can make differential (maybe linear also) cryptanalysis more difficult.
>
> Of course, a cube of sufficient size sould be used and cleartext not be "put
> on
> the faces centers" (if cube is of size k, 6*(k^2-1) squares are available
> for text
> and 6*k elementary moves can be done) ...
>
> Related to the key choice problem, I don't know whether the following
> problem of "minimizing the number of moves" is intractable, polynomial in
> time/space
> or so ...
> What i mean above is that if you have:
> position A (clear) => key (= moves) => position B (ciphered)
> How hard is it to compute the shortest key that performs the same operation
> ?
>
> Regards,
> George
/Tony
--
/\___/\ Who would you like to read your messages today? /\___/\
\_@ @_/ Protect your privacy: <http://www.pgpi.com/> \_@ @_/
--oOO-(_)-OOo---------------------------------------------oOO-(_)-OOo--
on the verge of frenzy - i think my mask of sanity is about to slip
---ôôô---ôôô-----------------------------------------------ôôô---ôôô---
\O/ \O/ ©99-00 <http://www.svanstrom.com/?ref=news> \O/ \O/
------------------------------
From: "Mysterion" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,misc.survivalism
Subject: Re: Why Microsoft's Product Activation Stinks
Date: Wed, 17 Jan 2001 13:46:49 -0500
Sounds like Microsoft is determined to shoot themselves in the foot.
"zapzing" <[EMAIL PROTECTED]> wrote in message
news:944nvc$9t9$[EMAIL PROTECTED]...
> Upcoming versions of windows may have, I
> read, something called "product activation".
> This means that you must call up microsoft
> so that the OS can have permission to run.
> I have a few questions about this. First of
> all, under what conditions will MS
> *refuse* to activate the product. It seems
> to me that if they never refuse activation,
> then putting in product activation code is
> pretty useless. And if they do, they may
> deny legitimate users who reconfigure their
> systems frequently.
>
> Also, what about the possibility of a major
> computer virus that requires many machines
> to restore. This would of course require
> that the OS be reactivated, but in that case
> the product reactivation lines could be
> jammed. This would make me think about it
> very carefully before I bought an OS that
> included product reactivation code.
>
> I understand MS's desire to protect their
> intellectual property, but please try to think
> of something that will not cause the collapse
> of civilization.
>
> --
> Void where prohibited by law.
>
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: "Kristopher Johnson" <[EMAIL PROTECTED]>
Crossposted-To: talk.politics.crypto,misc.survivalism
Subject: Re: Why Microsoft's Product Activation Stinks
Date: Wed, 17 Jan 2001 18:43:32 GMT
Office 2000 already has something like this built in. When we installed it
from the CD-ROM, the first time it ran it asked for registration
information, which we supplied and which it (I assume) then sent to
Microsoft via the Internet.
We then installed it on a second computer, using the same CD. When it first
ran, we gave registration info and it responded with a message box saying
"This software is already installed on another computer." Office will run a
certain number of times (about 50, I think), and after that point it will
not run. The message box does provide a phone number you can call to get
someone to fix the problem.
BTW, we have an enterprise-wide license for Office 2000, so we weren't
trying to break any laws here. And eventually we got our enterprise license
key to work. But it was annoying.
My opinion on this is that software companies have a right to put annoying
features in their software. And the rest of us have the right to stop using
annoying software.
-- Kris
"zapzing" <[EMAIL PROTECTED]> wrote in message
news:944nvc$9t9$[EMAIL PROTECTED]...
> Upcoming versions of windows may have, I
> read, something called "product activation".
> This means that you must call up microsoft
> so that the OS can have permission to run.
> I have a few questions about this. First of
> all, under what conditions will MS
> *refuse* to activate the product. It seems
> to me that if they never refuse activation,
> then putting in product activation code is
> pretty useless. And if they do, they may
> deny legitimate users who reconfigure their
> systems frequently.
------------------------------
From: Simon Johnson <[EMAIL PROTECTED]>
Subject: Re: RC5 on 16 word?
Date: Wed, 17 Jan 2001 19:14:46 GMT
In article <4fk96.59889$[EMAIL PROTECTED]>,
"N. Weicher" <[EMAIL PROTECTED]> wrote:
> Can RC5 be used on a 16-bit word? If so, how would that affect the
> security?
>
> Thanks.
>
>
With a sixteen bit word, the security isn't much good. The reason is
not a fault in the algorithm, but simply that the word size is too
small. As soon as you exceed 65536 blocks of encrypted data the cipher
becomes solvable by simple frequency analysis (like a monoalphabetic
substitution)
Simon.
--
Hi, i'm the signuture virus,
help me spread by copying me into Signiture File
Sent via Deja.com
http://www.deja.com/
------------------------------
Reply-To: "N. Weicher" <[EMAIL PROTECTED]>
From: "N. Weicher" <[EMAIL PROTECTED]>
Subject: Re: RC5 on 16 word?
Date: Wed, 17 Jan 2001 19:43:21 GMT
Thanks. Makes sense.
On a related note, in "Applied Cryptography" Schneier makes reference to "an
array, L, of c 32-bit words". However, there is no reference to what "c"
is. Do you know what the value of c is or how it is computed?
___________________________
> With a sixteen bit word, the security isn't much good. The reason is
> not a fault in the algorithm, but simply that the word size is too
> small. As soon as you exceed 65536 blocks of encrypted data the cipher
> becomes solvable by simple frequency analysis (like a monoalphabetic
> substitution)
>
> Simon.
> --
> Hi, i'm the signuture virus,
> help me spread by copying me into Signiture File
>
>
> Sent via Deja.com
> http://www.deja.com/
------------------------------
From: [EMAIL PROTECTED] (John Bailey)
Subject: NTRU Public Key System as a knapsack cryptosystem
Date: Wed, 17 Jan 2001 19:47:03 GMT
Simplified knapsack systems are easily implemented and would provide
a nice means for simple public key tasks such as symmetric key
exchange except they have a history of being ultimately breakable.
Examples:
A Comsat patent:
Simple and effective public-key cryptosystem
http://www.delphion.com/details?&pn=US04306111__
and
Diophantine encryption for public key encoding
http://www.frontiernet.net/~jmb184/interests/sci.crypt/numerical_encryption.html
In this last one, an encrypted message e = r*h + m*k where e is the
encrypted message, r is a random number, h and k are public key
values, and m is the encrypted message (number) m is recovered by
computing m = e*g mod p mod q where g, p, and q are calculated from
the private keys.
However, quoting A. M. Odlyzko of Bell Labs:
The rise and fall of knapsack cryptosystems,
http://www.research.att.com/~amo/doc/crypto.html
Abstract:
Cryptosystems based on the knapsack problem were among the first
public key systems to be invented, and for a while were considered to
be among the most promising. However, essentially all of the knapsack
cryptosystems that have been proposed so far have been broken. These
notes outline the basic constructions of these cryptosystems and
attacks that have been developed on them. (end quote)
I was amazed to realize that the NTRU Public Key method:
(reference)
Public key cryptosystem method and apparatus
http://www.delphion.com/details?pn=US06081597__
is formally equivalent to a knapsack system as well..
Referencing the last section of the NTRU tutorial
http://www.ntru.com/technology/tutorials/pkcstutorial.htm
e = r*h + m, where e is the encrypted message, h is a public key, r is
randomly chosen and m is the message.
The message m is recovered by finding f*e mod q mod p = m.
In the NTRU case, e, r, h, m, and f are truncated polynomials
whereas, in the cases mentioned at the beginning of this post, they
would simply be large numbers. In either case, essentially the same
modulo algebra applies, showing the recoverability of encrypted
plaintext using private keys.
This leads to an interesting question:
Presuming knapsack cryptoanalytic methods have been applied to the
NTRU system--
Are their other unexploited avenues in which the formalism for simple
modulo knapsacks might lead to interesting public key systems? An
example of such a system would be using digital Fourier Transforms
(FFT) to form knapsacks, along lines paralleling NTRU's use of
truncated polynomials.
John Bailey
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: RC5 on 16 word?
Date: Wed, 17 Jan 2001 19:49:47 GMT
In article <944qut$cou$[EMAIL PROTECTED]>,
Simon Johnson <[EMAIL PROTECTED]> wrote:
> In article <4fk96.59889$[EMAIL PROTECTED]>,
> "N. Weicher" <[EMAIL PROTECTED]> wrote:
> > Can RC5 be used on a 16-bit word? If so, how would that affect the
> > security?
> >
> > Thanks.
> >
> >
>
> With a sixteen bit word, the security isn't much good. The reason is
> not a fault in the algorithm, but simply that the word size is too
> small. As soon as you exceed 65536 blocks of encrypted data the cipher
> becomes solvable by simple frequency analysis (like a monoalphabetic
> substitution)
How often do you send 128kb encrypted messages?
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Tom St Denis <[EMAIL PROTECTED]>
Subject: Re: SAC question
Date: Wed, 17 Jan 2001 19:54:59 GMT
In article <[EMAIL PROTECTED]>,
Benjamin Goldberg <[EMAIL PROTECTED]> wrote:
> In the normal definition of the Strict Avalanche Criterion (SAC), changing any input
>bit, or selection of input bits, should change each output bit with probability of
>1/2.
>
> However, for an invertable function, there *must* be some bias. In the entry
>for SAC in Terry Ritter's glossary, he gives the example that for a 2 bit table, if
>one entry is the original value, there are only 3 "changed" values, so an input
>difference can cause each output bit to change with probability 2/3, not 1/2.
For a function to fulfill SAC it doesn't have to always have 1/2 of the
output bits affected, just on average (i.e with probability 1/2). So it is
possible that a single bit toggle causes four bits difference and still
fulfill SAC.
> If I were to consider an N bit table, the probability of an output bit
>changing when the input changes, should, if the table is as close to SAC as possible,
>change with probability of 1-(2^(N-1)-1)/(2^N-1).
Generally you count (over all the inputs) the number of times you flip one
bit of input the output bit (specific input/output bits) togle. If the count
is 2^(n-1) then it's SAC for those particular bits. If it's not then it's
not SAC. simple as that.
> Is there any particular term for this type of "Almost SAC?"
Not SAC.
> For instance, if a 128 bit cipher fulfills the property that if an input bit
>changes, then each of the output bits change with probability 1-(2^127-1)/(2^128-1),
>what do you call that property?
>
> Also, is there any term for calculating SAC on larger units than single bits?
>Maybe "bytewise SAC," or "wordwise SAC?"
Stochastically random? If you are talking binary, bytewise is
'seventh-order' so you would say "seventh-order SAC" i.e changing any eight
bits will change any other unit of eight bits with prob 1/256 (all bits flip
simulataneously).
To be honest I have never viewed SAC this way since it really deals with
bits. (or linear combos of bits).
When you move away from single bits you touch on the Bit Independence
Criterion (BIC) which states that any linear combination of output bits forms
a nonlinear n x 1 function.
Tom
Sent via Deja.com
http://www.deja.com/
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Re: future trends in asymmetric cryptography
Date: Thu, 18 Jan 2001 04:01:07 +0800
DJohn37050 wrote:
>
> IBM DID have a patent on DES and they do file the MOST patents of any company,
> for quite a few years.
The difference here is that IBM only patented DES. They didn't patent
the ideas that went into the construction of DES, presumably because
much of these were based on classified information. On the other hand,
RSA claimed that their patents on DH effectively covered the entire
concept of public key cryptography, though that certainly wasn't
true...but nobody was willing to fight it out in court to prove them
wrong. IBM never attempted to say that their DES patent covered all of
symmetric key cryptography, or even any vital element of modern
symmetric key crypto, such as Feistel structures or SP-networks, so
nobody was afraid of patent litigation from Big Blue if they tried to
duplicate structures within DES to make their own symmetric key block
cipher.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
ICSM-F Development Team, UP Diliman +63 (917) 4458925
OpenPGP Key ID: 0x0E8CE481
------------------------------
From: fred weigel <[EMAIL PROTECTED]>
Crossposted-To: sci.math,comp.theory
Subject: Re: A Small Challnge
Date: Wed, 17 Jan 2001 14:56:05 -0500
.rosi wrote:
.>
.> Mok-Kong Shen wrote in message <[EMAIL PROTECTED]>...
.> >
.> >
.> >rosi wrote:
.> >>
.> >[snip]
.> >> Having said this, I encourage you to read carefully the formal
.part.
.> >
.> >Sorry for posing some questions of ignorance, for I have
.>
.> No. The questions are some of the most intelligent ones you can
.> ever see in sci.crypt.
.>
.> >some essential difficulty to understand your scheme.
.> >
.> >(1) Suppose A is the receiver (he distributes all encryption
.> > keys, while keeping the decryption keys) and B and C are
.> > the intended senders and R is the rest of the world.
.> > Do B and C each obtain a single and distinct encryption
.> > key? How many decryption keys does A have (for receiving
.> > messages from whom)? Does R get anything?
.>
.> I believe you already got it!
.>
.> Since it does not matter which of the (possibly INFINITE)
.> encryption keys is used to encrypt, the decryption key has
.> no discrimination. In addition, poor A has only ONE dekey. :(
.> You let A, B, C, R or whatever you would like to have ONE
.> of the billions upon billions of encryption keys. Repeat, they
.> all can have it. Anyone who wants to have it, can. And anyone
.> who does not want to have it, can have it as well.
.>
.> To save another round, I ask the next possible question
.> for you: Can A publish more than one such encryption keys?
.> That is the implicit part which I think you all can answer with
.> no difficulty. Forgive me for not making it explicit. (Making
.> it explicit matters little as far as a working secure scheme
.> is concerned).
See below -- Interestingly, A doesn't have to publish any encryption
keys for this system...
.>
.> >
.> >(2) Are you sure that some practically useful D and E[i] and
.> > E[j] with E[i]!=E[j] could satisfy your following requirement
.> > for arbitrary m in a sufficiently large set?
.> >
.> > D(E[i](m)) = D(E[j](m)) = m
.> >
Given that you desire an arbitarily large i and j,
the encryption key becomes irrelevant. Unless each encryption
key produces the same encrypted result. Or a variant, where the
encryption key itself is only fluff that can be removed from the
message. Probably the best approach to doing this is to hide
the message using the encryption key. A problem is that the hiding
algorithm itself must be published to multiple parties, and once
someone knows what is going on, it will be remarkably easy to crack.
Of course any such scheme results in very fast encryption -- why not?
Because effectively no encryption can be done. The larger i and j
become, the weaker the system becomes.
Anyway - some simple proofs for you to think about:
Assume a message size smaller than the sender pool size in bits.
Assume that each encoding from the sender pool generates a unique
message. If the encrypted message is the same size as the message
size, the receiver could not decode the message.
So - either (1) sender information is encoded into the message
or (2) one of the assumptions is incorrect.
There is only one decryption key, and so sender shouldn't matter.
Lets ignore that case.
Case (2) -- we only made two assumptions - message size (which
is NOT under the receivers control) and uniqueness. Since message
size is not under reciever control, the uniqueness of the encoded
message cannot be guaranteed. QED. It won't work.
/>
/> Yes. Absolutely! That gives 'the' security I want but can not
/> find ANYWHERE else. I do not know about R (rest of the world)
/> and what that want and I should not care. :)
/>
/> To put this little piece of your doubt to ease, I can tell you
that
/> it is very practical. In fact, it is one of the fastest, if not THE
/> fastest, asymmetric encryption systems of today! Forgive me
/> for reading between the lines sometimes. You sounded like
/> asking 'possible?' instead of 'practical?'.
[snip]
--
Fred Weigel
[EMAIL PROTECTED]
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: block algorithm on variable length without padding?
Date: Wed, 17 Jan 2001 12:16:01 -0800
For some cases, yes it is possible, that case is if the data to be encrypted
is at least one block long. The easiest method to express is:
(assuming a block length of K bits
encrypt normally except the last partial block (if it lands on a block
boundary you got lucky)
encrypt the last K bits of the (partially) encrypted stream
for decryption
decrypt the last K bits of the stream
decrypt the entire stream except the last partial block
If you're lazy on your checks you lose a small amount of performance in the
on block boundary case base you double encrypt it. You can use various
chaining modes insides the system provided you aren't lazy about the
boundary check. If you are lazy about the boundary check the last block has
to be ECB encrypted instead of chained. Alternately you could apply an AONT
to the data and encrypt the first block.
If the data to be encrypted is shorter than a full block, your easiest
option is to use a stream mode (e.g. counter mode).
Joe
"N. Weicher" <[EMAIL PROTECTED]> wrote in message
news:kAj96.59822$[EMAIL PROTECTED]...
> Is it possible to use a block algorithm (such as Blowfish or DES) to
encrypt
> plaintext where the length is not a multiple of eight bytes? I know about
> padding, but what if padding is not an option, ie, the encrypted data must
> be the exact same length as the plaintext data? Is this feasible? If so,
> how is it done?
>
> Thanks for any feedback.
>
> Neil
>
> PS, if responding by email remove REMOVE
>
>
>
------------------------------
From: "Joseph Ashwood" <[EMAIL PROTECTED]>
Subject: Re: RC5 on 16 word?
Date: Wed, 17 Jan 2001 12:17:55 -0800
"Tom St Denis" <[EMAIL PROTECTED]> wrote in message
news:944t0n$eog$[EMAIL PROTECTED]...
> How often do you send 128kb encrypted messages?
I sent one in excess of 5 Megabytes 5 days a week, so actually quite often.
Joe
------------------------------
** 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 by posting to sci.crypt.
End of Cryptography-Digest Digest
******************************
