Cryptography-Digest Digest #966, Volume #11 Wed, 7 Jun 00 05:13:01 EDT
Contents:
Re: software protection schemes ("RecilS")
Re: XTR independent benchmarks (Roger Schlafly)
Re: XTR independent benchmarks (Wei Dai)
Re: Could RC4 used to generate S-Boxes? (David Hopwood)
Thoughts on an encryption protocol? (Dido Sevilla)
Re: Some dumb questions (Jim Gillogly)
testing non linearity of arithmetic-logic combinations ("cranky cransky")
Re: Solution for file encryption / expiration? (Anders Thulin)
Re: Cipher design a fading field? (wtshaw)
Re: An interesting page on the Rabin-Miller PP test (Andrew John Walker)
Re: Thoughts on an encryption protocol? (Volker Hetzer)
Re: Could RC4 used to generate S-Boxes? (Mark Wooding)
Re: Some dumb questions (Volker Hetzer)
----------------------------------------------------------------------------
From: "RecilS" <[EMAIL PROTECTED]>
Subject: Re: software protection schemes
Date: Tue, 6 Jun 2000 23:20:41 -0400
They don't all currently suck. All mass-market schemes suck simply because
they do not have the time to tailor computer-specific protection. An actual
recompilation of source (not a key-code algorithm) which relies upon the
processor's ID to decrypt necissary code seems to work for me.
Remember though, nothing is completely secure and if someone wants it bad
enough there will always be a way to take it.
- RecilS
tomstd <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> In article <aef%4.112$_l.9008@bgtnsc06-
> news.ops.worldnet.att.net>, "maxim" <[EMAIL PROTECTED]> wrote:
> >Does anyone know where I can find some ratings on software
> protection
> >schemes (particularly the ones that do not rely on a dongle)
> >thanx,
> >max
>
> Simple. They all currently suck. They are all based on
> security-via-obscurity which rarely works for a prolonged
> ammount of time.
>
> Tom
>
>
> * Sent from RemarQ http://www.remarq.com The Internet's Discussion Network
*
> The fastest and easiest way to search and participate in Usenet - Free!
>
------------------------------
From: Roger Schlafly <[EMAIL PROTECTED]>
Subject: Re: XTR independent benchmarks
Date: Tue, 06 Jun 2000 20:37:43 -0700
Wei Dai wrote:
> That structure is already present in GF(p^6) and is not imposed by XTR.
> The reason it can represent a field element by only 2 subfield elements
> is because it works in a multiplicative subgroup of size p^2-p+1, which
> every GF(p^6) has. The question is whether discrete log in GF(p^6) is
> really as difficult as in a prime field (when the two fields have about
> the same order)? I think there is definitely room for doubt.
There is also the possibility that discrete logs in the subgroup
of GF(p^6) is much easier that in the entire GF(p^6).
------------------------------
From: Wei Dai <[EMAIL PROTECTED]>
Subject: Re: XTR independent benchmarks
Date: Tue, 6 Jun 2000 21:31:39 -0700
In article <[EMAIL PROTECTED]>, [EMAIL PROTECTED] says...
> Wei Dai wrote:
> > That structure is already present in GF(p^6) and is not imposed by XTR.
> > The reason it can represent a field element by only 2 subfield elements
> > is because it works in a multiplicative subgroup of size p^2-p+1, which
> > every GF(p^6) has. The question is whether discrete log in GF(p^6) is
> > really as difficult as in a prime field (when the two fields have about
> > the same order)? I think there is definitely room for doubt.
>
> There is also the possibility that discrete logs in the subgroup
> of GF(p^6) is much easier that in the entire GF(p^6).
If that's true then DL in the entire GF(p^6) must also be relatively
easy, because you can do a DL in GF(p^2) to get the DL mod p-1 and p+1,
then in GF(p^3) to get it mod p^2+p+1, then in the XTR subgroup to get
it mod p^2-p+1, and finally use the Chinese Remainder Theorem to
recovery the full DL.
--
cryptopp.com - a free C++ class library of cryptographic schemes
------------------------------
Date: Wed, 07 Jun 2000 03:40:54 +0100
From: David Hopwood <[EMAIL PROTECTED]>
Reply-To: [EMAIL PROTECTED]
Subject: Re: Could RC4 used to generate S-Boxes?
=====BEGIN PGP SIGNED MESSAGE=====
Mark Wooding wrote:
> Bijectivity isn't actually a necessary feature [for S-boxes];
> it helps security, though. For example, Blowfish's S-boxes aren't
> necessarily bijective -- these are the 'weak keys' that Vaudenay found.
An 8x32 S-box cannot be bijective. The Blowfish 'weak keys' occur when
not all of the S-boxes are one-to-one.
- --
David Hopwood <[EMAIL PROTECTED]>
PGP public key: http://www.users.zetnet.co.uk/hopwood/public.asc
RSA 2048-bit; fingerprint 71 8E A6 23 0E D3 4C E5 0F 69 8C D4 FA 66 15 01
=====BEGIN PGP SIGNATURE=====
Version: 2.6.3i
Charset: noconv
iQEVAwUBOT22DTkCAxeYt5gVAQG9tAgAsQsrR1Ig92mG3HRS5uOei72K8kFdfThg
X0beTxFbPlsFBGJ36Yr1eTQAJwSB2It/R7ZTALTSiuqaEyCmi0cTr+KWiLCIFol1
FGx894H7a/meInk5yDQDbXzcPDgbUVcGG8QrKTwiNrq3Yq6iFaz/alV3uXaSDVn0
nqLAKR+qDgYkNCRS6JrXRf/zNvQjDoAqnLk8s9rNj1JZh2LNEn5FtYSHZH0B+48k
XqyVySNzkrIzXKciD78CLfm5Abs9mPQwHbvP5omO+Ul5qllnDcFYyzEuDIfTDt8I
LkKAxFeYOaBYcK/Y4pOdSl2tdTcuac3IrxvA5/XMzkFqta6OwZIaXg==
=g3KB
=====END PGP SIGNATURE=====
------------------------------
From: Dido Sevilla <[EMAIL PROTECTED]>
Subject: Thoughts on an encryption protocol?
Date: Wed, 07 Jun 2000 12:53:23 +0800
As part of an embedded system design project I have, I have to come up
with a secure protocol for data transmission for a client/server
system. The basic idea is as follows: every client carries with it two
256-bit master keys which are known only to itself and to the server.
The first key is used to encrypt data transmissions from the client to
the server, the second is used to decrypt data transmissions from the
server to the client.
Data transfer between client and server takes place in transactions.
Each transaction is made using a new key based on the key used in the
previous transaction. The master key is used to generate the keys for
the first transaction in the same way. New keys are generated from the
old one by applying the MD5 hash to the first 128 bits of the old key to
get the first 128 bits of the new key, and again to the second 128 bits
of the old key to get the second 128 bits of the new key. Under this
system, no key information is ever transmitted across the network.
The 256-bit keys are used for a product cipher, tentatively Serpent, but
any algorithm that uses 256-bit keys and 128-bit blocks (such as all
other candidates for the AES) may be substituted. Data is transmitted
in CBC mode. At the end of the data transmission, the MD5 hash
associated with the plaintext of the sent data is sent to the receiver
to ensure that the data transmitted was correctly decrypted.
Are there any flaws in this "secure" protocol which I have described?
Can clever manipulation of the protocol recover key information or any
such sensitive variables? Are there any suggestions for improving the
security of this protocol? Is there a better cryptographic hash than
MD5 out there? Thank you very much for all your input.
--
Rafael R. Sevilla <[EMAIL PROTECTED]> +63 (2) 4342217
Mobile Robotics Laboratory +63 (917) 4458925
University of the Philippines Diliman
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Wed, 07 Jun 2000 06:42:01 +0000
Mok-Kong Shen wrote:
>
> Jim Gillogly wrote:
> > 79:v#foffm#b#
> > 7a:u eleen a
> > 7b:t!dmddo!`!
> > Of these, 0x7a is the obvious winner; and it still would be
> > with fewer than 10 samples. With n large enough, the obvious
> > winner would be correct in enough cases to allow the attacker
> > to unwind a simple transposition layered under this.
>
> Thanks for the valuable results of your investigation. With increasing
> values of n, the position of the opponent will understandably be
> increasingly better. So we seem to need to consider some better
> techniques for combination with OTP. I admit I don't have a very
> good idea at the moment. But perhaps doing in addition such stuffs
> as polyalphabetic substitutions or random rotations of 32 bit words
> would sufficiently pushed the level of complexity above the
> threshold that the opponent can manage to overcome.
In fact, the best "technique for combination with OTP" is to make it
a OTP, not a 2TP or a 9TP. Once you allow n > 1, you open the door
to potential analysis, so you may as well step back and take advantage
instead of the modern ciphers available for which there's no known
practical break.
--
Jim Gillogly
Sterday, 18 Forelithe S.R. 2000, 06:37
12.19.7.4.18, 11 Edznab 1 Zotz, Eighth Lord of Night
------------------------------
From: "cranky cransky" <[EMAIL PROTECTED]>
Subject: testing non linearity of arithmetic-logic combinations
Date: Wed, 7 Jun 2000 16:46:37 +1000
could somebody point me towards some research, if there is any, on non
linearity or linearity of certain chip level operations (addition,
subtraction, xor, shift, etc..) i was thinking of coding something to try
different combinations of these operands on integers and examine the
results for the combinations that produce the most non linearity. is such an
extensive test necessary? is this a well worn path? is it possible to
examine the nature of the function itself ( like boolean logic, or addition
axioms or whatever ) and work it out, instead of testing????!?!?!
aaargh...anywho, help appreciated.
------------------------------
From: Anders Thulin <[EMAIL PROTECTED]>
Subject: Re: Solution for file encryption / expiration?
Date: Wed, 7 Jun 2000 07:01:59 GMT
Will Dormann wrote:
> I work for a web site that provides books for free in PDF format on the
> internet. Most of our material is public domain, but in order to attract new
> authors, my boss is wanting to look into some sort of "protected" format.
> (Which cannot be displayed after a certain amount of time, and I guess
> encrypted to prevent copying too)
You may want to check http://www.ebxwg.org/ for some related information.
www.glassbook.com has a PDF reader which uses the EBX security handler.
My impression is that it won't stop someone who is *very* determined to
get at your books, but it will stop those 80% of computer users who
never try anything out of the ordinary.
So it's more a question of what you really want to protect yourself against,
and for what time. Take a look at www.pwcrack.com for the downside of password
protection.
> 1) Is this practical? I would assume that this would require a speical
> software viewer? (which he would want me to program myself). This would
> make it a platform-specific item, too, I would assume. Currently books are
> in PDF format, which just about anybody can view.
You probably could base it on the Adobe Reader, but use your own
security handler which provides the special functionality you want.
However, as I said, I'm fairly certain that it wouldn't stop any serious
attack.
For more details, you might try comp.text.pdf -- I'm not up-to-date about
the SDK's and other things available from Adobe.
--
Anders Thulin [EMAIL PROTECTED] 040-10 50 63
Telia Prosoft AB, Hj�lmaregatan 3B, 212 19 Malm�, Sweden
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: Re: Cipher design a fading field?
Date: Wed, 07 Jun 2000 00:32:07 -0600
In article <[EMAIL PROTECTED]>, "Douglas A. Gwyn" <[EMAIL PROTECTED]> wrote:
> wtshaw wrote:
> > Due to the sheer multiplicative nature of algorithm possibilities
> > involving design parameters, who dares say that anyone, much less me, will
> > envision them all, nor, much less, be able to attack them all?
>
> If that is meant to be in response to my initial posting in this thread,
> you're arguing against a straw man. *I* never said that the amateurs
> should attack *all* existing systems. I do decry the fact that many
> amateur cryptosystem designers don't know enough about methods of
> attack to do a good job of protecting against them.
It is obvious to me that there is a great need for more cipers of all
strengths and designs in order to train flexibility in analysis. Having a
few dozen ciphers for this purpose is simply not enough. There is a big
difference between knowing how to attack a cipher and having the means to
do so. This applies to amateurs as well as professionals, if there
sometimes is not a difference.
Attacking may be for that purpose alone, and not leading to new
constructions, and constructing might be for that purpose alone, and not
leading to new attacks. Certain flaws may be purposefully built into
ciphers that might aid in building a strategy of attack.
There are those people who delight in attacking something new, and there
are those that limit what they will attack. There is nothing wrong is
liking to be one way than the other, or being a switch hitter.
The same is true for those that attack by hand and/or computer. Some
marginal hashes are probably best does by hand anyway, since computer
attack may lack needed fine judgement if clear results are at all
possible: Keyphrase, Tridigital, Running Key, and hashed keys of Morbut,
Myszkowski, Gromark, etc.
To better develop computer attacks means having come ciphers that require
it, making them weaker or stronger for reason.
I'm all for better understanding of what makes a simple cipher strong, but
making it too clever may not be the goal. It can be that a trick is
necessary to help solving, and the trick is esoteric until found, like the
CIA sculpture.
Now, consider Slidefair, which was designed by someone who was proud of it
at the time. It is likely by some, cursed by others, ignored by others,
but nevertheless somewhat popular. Upon analysis, it is not a purely
substitutional cipher as it may seem but has a transposition of every two
ciphertext letters, which might be a good place to start solving it.
Thereafter, it is merely like a subset of my 3-way cipher with a simple
alternation of modes. With Slidefair, there are only 3 basic
constructions with two modes; with 3-way, six with two modes. I would
consider 3-way a better cipher, because the trivial transposition imply
does not count for much at all, and the mode picture can be rather
complicated as a key, at least in a hand solving sense.
I would suggest that an analytical approach to what a cipher actually is
doing, best done for me by programming it from scratch. You either have
the program right or you don't. Do not underestimat what using and
abusing an algorithm can lead to, but having it implemented makes such
tests easier.
I will slowly add to my classic implementations as I pick each of such
algorithms into its raw components. Results are sometimes interesting;
For instance, that the only real difference to a columnar and incomplete
columnar is whether you cut the number of sequences search for by teling
whether things come out even or not; the program is the same for
constructing either.
--
If you wonder worry about the future enough to adversely limit
yourself in the present, you are a slave to those who sell security.
------------------------------
Crossposted-To: sci.math
Subject: Re: An interesting page on the Rabin-Miller PP test
From: [EMAIL PROTECTED] (Andrew John Walker)
Date: 7 Jun 2000 12:20:42 +1000
Robin Chapman <[EMAIL PROTECTED]> writes:
>In article <393b2fa0$[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] (Andrew John Walker) wrote:
>> Recently I stumbled across an interesting page at
>> http://www.geocities.com/SiliconValley/Network/2811/primes/higgins.htm
>>
>> This paper deals with the number of non-witnesses to a composite
>number
>> n using the Rabin-Miller test.
>>
>> For a number n=p*q, p and q distinct primes, they conjecture
>> that the number of non-witnesses is a function of
>> d=gcd(p-1,q-1)
>> and that if d=2^t*r (r odd)
>> then the number of non-witnesses is equal to
>> r^2*(2+(4^t-4)/3)
>>
>> Does anyone know
>> a) if these results have been proved
>> b) if they have been extended to other forms of composite numbers?
>I don't know if this has been proved in the literature, but it's
>very easy to prove, so I expect it has.
>If a is a non-witness then a^{pq-1} = 1 (mod p), but as a^p = a
>(mod p) this gives a^{q-1} = 1 (mod p). Since a^{p-1} = 1 (mod p)
>we conclude that a^d = 1 (mod p). Similarly a^d = 1 (mod q).
>Thus a^d = 1 (mod pq). The solutions to this congruence
>form, by the Chinese remainder theorem, a group G isomorphic
>to (Z/dZ)^2.
>Now G is isomorphic to (Z/rZ)^2 x (Z/2^t Z)^2. The Miller-Rabin test
>uses the largest odd factor s of pq - 1, it calcuates a^s then
>repeatedly squares this modulo pq. Now t is a factor of s so the
>first step essentially projects G onto its subgroup G_1 of elements
>b with b^{2^t} = 1 (mod pq). That is for each element b of G_1
>there are r^2 elements b with a^s = b (mod pq). Consider b in G_1.
>Then b is a non-witness if b has the same order modulo p and modulo q.
>There is 1 element of order 1 mod p and mod q,
>there is 1 element of order 2 mod p and mod q,
>there are 2^2 elements of order 2^2 mod p and mod q, (if 2^2 divides d)
>there are 2^4 elements of order 2^3 mod p and mod q, (if 2^3 divides d)
>etc.
>The number of b giving non-witnesses is thus
>1 + 1 + 4 + 4^2 + ... + 4^{t-1} = 1 + (4^t - 1)/3 = (4^t + 2)/3
>and so the number of non-witnesses is r^2 (4^t + 2)/3.
Thanks, I don't fully understand the maths yet but it's good to
see a result! Would this line of reasoning work with forms such as p^2*q
or p*q*r?
If eventually a general result could be found it would allow for much more
accurate estimates of how often this test produces non-witnesses for
a particular sized composite, forinstance by taking 100 50d numbers
and factoring them.
Andrew Walker
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Thoughts on an encryption protocol?
Date: Wed, 07 Jun 2000 08:32:48 +0000
Dido Sevilla wrote:
>
> As part of an embedded system design project I have, I have to come up
> with a secure protocol for data transmission for a client/server
> system. The basic idea is as follows: every client carries with it two
> 256-bit master keys which are known only to itself and to the server.
> The first key is used to encrypt data transmissions from the client to
> the server, the second is used to decrypt data transmissions from the
> server to the client.
So it's a secret key protocol. Are there any constraints that forbid
the use of public key stuff?
How do you change keys over the lifetime of your devices?
> Data transfer between client and server takes place in transactions.
> Each transaction is made using a new key based on the key used in the
> previous transaction. The master key is used to generate the keys for
> the first transaction in the same way. New keys are generated from the
> old one by applying the MD5 hash to the first 128 bits of the old key to
> get the first 128 bits of the new key, and again to the second 128 bits
> of the old key to get the second 128 bits of the new key. Under this
> system, no key information is ever transmitted across the network.
Well, the problem is thatas soon as an attacker gets hold of *any*
of the thus generated keys he can create all keys after that.
Why not use a stream cipher or cryptographically secure PRNG to
generate the session keys?
> The 256-bit keys are used for a product cipher, tentatively Serpent, but
> any algorithm that uses 256-bit keys and 128-bit blocks (such as all
> other candidates for the AES) may be substituted. Data is transmitted
> in CBC mode. At the end of the data transmission, the MD5 hash
> associated with the plaintext of the sent data is sent to the receiver
> to ensure that the data transmitted was correctly decrypted.
Should work as long as the number of messages desn't get too large.
> Are there any flaws in this "secure" protocol which I have described?
You don't solve the key distribution problem and old keys are
valuable in your protocol.
> Can clever manipulation of the protocol recover key information or any
> such sensitive variables?
Probably not. If yes, the key generation mechanism is IMHO your
weakest point. If a number of succeeding messages are known to the
attacker he might try to exploit MD5 artifacts in thesuccession of keys.
But I've no idea about how feasible that is.
> Are there any suggestions for improving the
> security of this protocol?
See above.
> Is there a better cryptographic hash than
> MD5 out there?
SHA-1.
Greetings!
Volker
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Could RC4 used to generate S-Boxes?
Date: 7 Jun 2000 08:45:11 GMT
David Hopwood <[EMAIL PROTECTED]> wrote:
> An 8x32 S-box cannot be bijective. The Blowfish 'weak keys' occur when
> not all of the S-boxes are one-to-one.
It depends on how you look at the range of the S-box function.
-- [mdw]
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Wed, 07 Jun 2000 08:51:50 +0000
Mok-Kong Shen wrote:
>
> Volker Hetzer wrote:
> > As to "concreteness", what exactly do you want?
> I like instructions that are practical enough for doing the work of
> analysis.
For the simple case (two messages of known character distribution
xored together) you attack it like a book cipher.
You compute the distribution of the xor-results based on the
distribution of the characters going into the xor.
Then you count the distribution of the ciphertext (the xored messages)
and look for matches of probability.
At least that's what I'd do.
> If you have header informations, then you have 'some' knowledge
> about the plaintext.
In what way does this differ from the knowledge of he language?
> I assume that this leakage of information can
> be prevented by suitable means, e.g. thru transposition or some better
> techniques.
Example: a M$-word document has presumably a lot of \000 chars
in it. This affects the character distribution and is therefore
valuable knowledge for an attacker.
> On the other hand, I assume that the opponent knows the
> language of the plaintext and he has the frequency distribution of the
> single characters but has no digram frequencies etc. My question is
> then how to proceed precisely to do that step by step, i.e. I need
> a functioning recipe.
See above.
> > > Note also that, if the
> > > OTP is used exactly twice, then (1) the xor of different pairs of
> > > messages (each pair has the same OTP segment, but different pairs
> > > have different segements) are essentailly unrelated to each other and
We are assuming that we are xoring messages with a known character distribution
and that we are sure we've got the correct pieces to xor together.
Furthermore, in academic analysis ae operate on the assumtion that the
"algorithm" is known to the attacker. It's arguable that details of key-scheduling
are part of the algorithm and therefore assumed to be known.
> > > (2) if there is a number of messages intercepted, one has to correctly
> > > pair the messages according to the OTP segment used (how is that
> > > going to be done?).
>
> > Just like the whole idea of re-using an OTP keystream, it relies on the
> > stupidity of the people communicating. You test different variants
> > of reuse.
>
> I am afraid I don't quite understand what you mean by testing different
> variants of reuse. Assuming that each segment is used twice, one has
> to find from a large number of messages the corresponding messages
> (in pairs) that use the same segments. It is not apparent how one is
> going to do that.
Variant 1: every message uses the same pad.
Variant 2: a pad of fixed length is rolled over at the end.
Variand 3: <fill in with your own ideas> :-)
Greetings!
Volker
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
** 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
******************************
