Cryptography-Digest Digest #974, Volume #11 Thu, 8 Jun 00 07:13:00 EDT
Contents:
Re: testing non linearity of arithmetic-logic combinations (Mok-Kong Shen)
Re: Primitive element (Mark Wooding)
Re: Thoughts on an encryption protocol? (Volker Hetzer)
Re: Primitive element (Mok-Kong Shen)
Re: Primitive element (Mok-Kong Shen)
Re: testing non linearity of arithmetic-logic combinations (Mark Wooding)
PK analogue for passwords (=?iso-8859-1?Q?Tom=E1s?= Perlines Hormann)
Re: Comfort csybrandy ! (Was: Attack on SC6a (sci.crypt cipher)) (Runu Knips)
Re: Primitive element (Mok-Kong Shen)
Re: software protection schemes (Vernon Schryver)
Re: Primitive element ("Jesper Stocholm")
Re: Cryptographic voting (Mok-Kong Shen)
Re: testing non linearity of arithmetic-logic combinations (Mok-Kong Shen)
Re: Some dumb questions (Volker Hetzer)
Re: Comfort csybrandy ! (Was: Attack on SC6a (sci.crypt cipher)) (tomstd)
Re: Arithmetic Coding (tomstd)
Re: Primitive element (Eric Hambuch)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: testing non linearity of arithmetic-logic combinations
Date: Thu, 08 Jun 2000 11:24:17 +0200
Terry Ritter wrote:
> With respect to nonlinearity, a completely random table is likely to
> be more nonlinear than an invertible substitution table which is
> necessarily restricted to be a permutation, but a random table is not
> guaranteed to be balanced, and is unlikely to be invertible.
> Similarly, a substitution table is likely to be more nonlinear than a
> similar-sized row or column of a Latin square which is more than just
> an arbitrary permutation: each row or column also must be a
> permutation in a set which will make a Latin square. Of course, a
> Latin square will have multiple of such permutations, each guaranteed
> different, so simply taking the minimum nonlinearity of all these
> measured one-by-one can be deceptive.
'a random table ... is unlikely to be invertible' seems to suggest in
the present context that a Latin square is invertible. In which sense
is that? Since Latin square is used, as you said, as a 2-in 1-out function,
it could by nature not be invertible, i.e. one can't from the output
compute the input, if I don't err. Thanks in advance.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Primitive element
Date: 8 Jun 2000 09:26:36 GMT
Jesper Stocholm <[EMAIL PROTECTED]> wrote:
> I have a finite group Z(p), where p is prime. I need to find a
> generator/primitive element alpha s.t. alpha^b mod p = 1
>
> How do I do this ? The order b is not known.
If a is a primitive element, then its order is known to be p - 1.
Unfortunately, x^{p-1} = 1 (mod p) for any element x of Z^*_p (Fermat's
Little Theorem): you need to verify that there is no smaller n such that
a^n = 1 (mod p), and to do that efficiently I believe you need to know
the factors of p - 1. You *do* know the factors of p - 1 don't you? ;-)
Alternatively, find just one `large' prime factor q (such that sqrt(q)
represents too much work) of p - 1, find h such that g = h^{(p-1)/q} !=
1 (mod p), and use g as a generator of the order-q subgroup of Z^*_p.
This is probably a better idea anyway if you're doing cryptography based
on the difficulty of computing discrete logarithms.
-- [mdw]
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Thoughts on an encryption protocol?
Date: Thu, 08 Jun 2000 09:31:32 +0000
Dido Sevilla wrote:
>
> John Myre wrote:
> >
> > First, the technique of creating the session key based on
> > the prior key seems prone to problems. Not security problems,
> > but communication problems. If you ever lose "sync", you need
> > to design a way to recover. You need to consider lost messages,
> > reboots (on either end), and so forth.
> >
>
> I have been thinking about the resynchronization problem a lot
> actually. Sometimes, I'm actually tempted to completely abandon that
> system and make use of a noisy semiconductor diode in my client
> terminals, hash the results from reading its random noise to generate a
> key, and transmit the new key using a long-term secret, rather than
> performing all this synchronous fiddling. Use one key for all
> transactions in one day only, so that the long-term secret need not be
> reprogrammed too much...
You can use a real random number generator? Lucky guy.
Collect bits from it, hash enough of them together until you get
enough to initialize a secure prng. You can re-initialise the prng
daily. That pretty much guarantees that even badly skewed bits
from the real rng result in high quality random output for your
communications protocol.
You can reuse your bulk cipher as prng.
> Cracking the client machines would be nearly impossible, because they
> only know how to communicate with the server.
Is it worthwile for an attacker to try to duplicate a device?
I.e. has the server to know whom it's talking to?
> The only way to get any
> of the secret information in the clients would be to actually open one
> up and try to read the nonvolatile memory inside, and this would
> purposefully be made extremely difficult (e.g. opening up a case using
> the designed access port would cut power to the NVRAM), as we don't
> really trust the people who do have access to the clients.
Is the data valuable enough to try kinky things (like buying a couple of
spare devices and sawing them open in the lab in order to discover how
to open it "properly")?
> We really
> would have to trust those on the server end, as it's their job to make
> use of the data that the server receives from the clients anyhow.
Just out of compleeteness, do you also have to trust your clients not
to spill the information before it enters the device?
> Probably, it is overkill, and I'm actually thinking of changing the
> algorithm to something simpler.
AFAIK you might want to consider your block cipher as hash function.
With a 128Bit block cipher (like the AES) this is reasonable.
> I've considered PK systems and most of them seem to be a bit complicated
> when I think about my time and space constraints.
SPEKE requires five communications, a constrained version four.
You'd want to stay away from SSL or somesuch because you don't want to
negotiate a cipher suite. This simplyfies things greatly.
> I am going to try to
> fit everything (which includes an Ethernet driver, UDP, and code to push
> a few peripherals as well) into only 32 kbytes of ROM, using an
> 80186-based microcontroller. If I can make it fit in something even
> smaller, so much the better...we can save money on hardware costs. I
> have only one year or so from now to build and deploy this system...
Have you considered flash controllers? They can have up to 2MB flash and
usually cost less than 20 USD. At least it would enable you to compile
C-reference code for encryption stuff thereby saving you time and your
company costs.
Greetings!
Volker
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Primitive element
Date: Thu, 08 Jun 2000 11:43:52 +0200
David Blackman wrote:
> Also the question seems quite confused. When someone says Z(p), they
> usually mean integers modulo a prime number. In that case, b=p-1
> (assuming you mean a group under multiply?) Although, there are a few
Are you saying that the order b of any element in Z(p) is b=p-1?
That's invalid, I believe.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Primitive element
Date: Thu, 08 Jun 2000 11:43:40 +0200
Eric Hambuch wrote:
> It's not easy to find a generator! For more details check out:
Since primitve roots are commonly rather abundant, here phi(p-1)
in number, it's a good stategy simply to pick a random element and
test with the criterion given in Knuth, vol.2, p.21.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: testing non linearity of arithmetic-logic combinations
Date: 8 Jun 2000 09:41:03 GMT
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> 'a random table ... is unlikely to be invertible' seems to suggest in
> the present context that a Latin square is invertible. In which sense
> is that? Since Latin square is used, as you said, as a 2-in 1-out
> function, it could by nature not be invertible, i.e. one can't from
> the output compute the input, if I don't err. Thanks in advance.
Think about it for a moment not as a function which, given two inputs
gives you an output, where inversion would imply going from the output
to the inputs, but as a set of triples (a, b, c), where L(a, b) = c for
Latin square L. Then think of inversion as finding the remaining
element of a triple given the other two. Under this, slightly
different, reformulation of invertibility for multi-argument functions,
Latin squares are invertible, and in a useful way.
-- [mdw]
------------------------------
From: =?iso-8859-1?Q?Tom=E1s?= Perlines Hormann <[EMAIL PROTECTED]>
Crossposted-To: comp.security.misc
Subject: PK analogue for passwords
Date: Thu, 08 Jun 2000 11:41:47 +0200
Hi folks!
A year ago or so, somebody published here an approach for users of many
passwords (>2) which made use of a public part which was supposed to
contain lots of difficult letters and several private parts which were
supposed to be easy to remember.
Does anybody remember this article and can it re-post here? I remember
to find it really attractive and now I want to study it a bit deeper as
most passwords are being written down somewhere and this approach may
ensure a better handling of password, especially when having to use lots
of them for different purposes.
Thanks in advance and I hope to get some feedback!
--
Quick answering: mailto:[EMAIL PROTECTED]
Check it out: http://www.weh.rwth-aachen.de/~tomas
Do it Now!
:o) Tom�s Perlines (o:
------------------------------
Date: Thu, 08 Jun 2000 11:42:22 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Comfort csybrandy ! (Was: Attack on SC6a (sci.crypt cipher))
[EMAIL PROTECTED] wrote:
> Well, I tried. I guess I should have analyzed it more, however I
> simply do not have the time to learn. Since my algorithm has been
> declared as crap in it's current version, does anyone have suggestions
> on how to fix it? Also, what aspects of it do people like?
Hmm.
It looks mainly like a design by confusion. Make it confusing enough,
then nobody will find an attack against it. Bad idea :) but popular
design principle.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Primitive element
Date: Thu, 08 Jun 2000 12:05:25 +0200
Mok-Kong Shen wrote:
> David Blackman wrote:
>
> > Also the question seems quite confused. When someone says Z(p), they
> > usually mean integers modulo a prime number. In that case, b=p-1
> > (assuming you mean a group under multiply?) Although, there are a few
>
> Are you saying that the order b of any element in Z(p) is b=p-1?
> That's invalid, I believe.
Sorry, I misinterpreted your sentence.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Vernon Schryver)
Subject: Re: software protection schemes
Date: 7 Jun 2000 14:55:36 -0600
In article <[EMAIL PROTECTED]>,
Mike Rosing <[EMAIL PROTECTED]> wrote:
>maxim 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
>
>Look at Embedded Systems Programming. A month or 2 ago they had an
>article describing a few. They all have problems, they can be defeated
>by anyone determined enough. But it will give you an overview of what's
>out there.
As I thought we agreed the last time someone asked that question and was
pointed at that trade rag, DO NOT look at "Embedded Systems Programming"
unless you what you need is at best superficial. That magazine is suitable
only if you've never before thought about the subject or cannot think very
well.
In the last year or two I've had professional reasons to care about
dongles, software protection, node-locking, licensing, copy-protection,
and the other stuff that's been floating around the commercial software
world for more than 20 years. So I read the article that can now be found
at http://www.embedded.com/2000/0002/0002feat1.htm with interest. It
left me shaking my head and wondering if all trade rags articles seem as
lame to anyone who is not pointy-haired. Do people with other sets of
clues think likewise about the articles I find interesting in other trade
rags? It's not that this article is wrong, but that has almost as much
information about its subject as the typical "Popular Mechanics" or
"Popular Science" article has about how to actually build or use one of
its enthusiasm. The "Embedded Systems Programming" article includes no
real clues about the implementation time or debugging, code size, system
speed costs nor the strengths against which kinds of attacks and attackers
of its suggestions, and it certainly does not cover the spectrum in any
meaningful or useful way.
In looking again for that article on software protection schemes,
I was reminded of just how bad that trade rag is. If you have
the faintest clue about CIDR, IP address allocations, and RARP,
http://www.embedded.com/internet/0004/0004ia2.htm will make you groan.
(Or am I confused and it was some other "Embedded System Programming"
article that was my excuse for ridicule?)
--
Vernon Schryver [EMAIL PROTECTED]
------------------------------
From: "Jesper Stocholm" <[EMAIL PROTECTED]>
Subject: Re: Primitive element
Date: Thu, 8 Jun 2000 12:15:57 +0200
"David Blackman" <[EMAIL PROTECTED]> wrote in message
news:[EMAIL PROTECTED]...
> Jesper Stocholm wrote:
> >
> > I have a finite group Z(p), where p is prime. I need to find a
> > generator/primitive element alpha s.t. alpha^b mod p = 1
> >
> > How do I do this ? The order b is not known.
> >
> > thanks
> >
> > Jesper
> >
> > --
> > http://stocholm.dk
> > MSN Messenger: [EMAIL PROTECTED]
>
> More homework from school or university? Otherwise i can't imagine
> anyone who would wnat to know this and would not know the answer, or
at
> least how to ask the question better.
Well ... you caught me ... although I wouldn't call it 'homework' - more
a project in the math behind attacking cryptosystems based on DLP.
> Also the question seems quite confused. When someone says Z(p), they
> usually mean integers modulo a prime number. In that case, b=p-1
> (assuming you mean a group under multiply?) Although, there are a few
> interesting cases where you don't know p, such as some factoring
> algorithms.
This is exactly what I mean - what I was confused about was how to set
up the initial discrete logarithm-problem.
>
> What is more, alpha^b mod p = 1 is true for any alpha from 1 to p-1,
so
> that part is fairly redundent. You're just looking for a generator.
>
you might have a point here. The material I have with me (HAC +
Stinson) does not describe the selection of the generator of the group -
at least as far as I can see. The generator alpha of the multiplicative
group Z(p) has order (p-1), so the question is how to find this - as you
correctly say. I was not aware of the test in Knuth - even though I
browsed thru it to find some help ... but I'll give it another shot
later.
And yes ... I do know p
Jesper
PS: and your point has been noted - I'll be more specific next time :o)
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Crossposted-To: sci.math
Subject: Re: Cryptographic voting
Date: Thu, 08 Jun 2000 12:29:07 +0200
Greg wrote:
> A person cannot be compelled to identify himself (according to the
> SCOTUS) but we must have a mechanism in place to ensure that each
> person casts only one vote and no more. This is one of the easiest and
This sounds like demanding a perpetum mobil. The only way to ensure
absolutely correct voting seems to require at the minimum nonforgeable
ID cards or their equivalents that uniquely map to the physical persons,
I conjecture. BTW, I am surprised to learn that the US voting system is
so vulnerable at its foundation.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: testing non linearity of arithmetic-logic combinations
Date: Thu, 08 Jun 2000 12:41:37 +0200
I have another dumb questiion: Is there an efficient
method to compute an n*n Latin square for arbitrary n?
Thanks in advance.
M. K. Shen
------------------------------
From: Volker Hetzer <[EMAIL PROTECTED]>
Subject: Re: Some dumb questions
Date: Thu, 08 Jun 2000 10:32:19 +0000
Mok-Kong Shen wrote:
> Yes. But one should note that, after picking a pair, it is yet fairly 'difficult'
> to determine whether they belong to the same segment of OTP. Thus
> the resource required in the whole undertaking is going to be extremely
> huge in my view.
Depends on how you define "fairly". If I had to try it I would write
a program that takes a pair, tries to break it and checks success by
examining the character distribution of the decrypted messages.
There may be many different possible decryptions.
Then I'd try to compute a number indicating the degree of conformance
to the character distribution.
Given n messages (i.e. (n(n-1))/2 pairs) I'd rank the decryption results
according to that value. Then I'd do a manual inspection of the top
messages.
The shorter the messages the harder this gets.
Greetings!
Volker
--
The early bird gets the worm. If you want something else for
breakfast, get up later.
------------------------------
Subject: Re: Comfort csybrandy ! (Was: Attack on SC6a (sci.crypt cipher))
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 08 Jun 2000 03:45:49 -0700
In article <8hj6hd$573$[EMAIL PROTECTED]>, [EMAIL PROTECTED]
wrote:
>Well, I tried. I guess I should have analyzed it more, however
I
>simply do not have the time to learn. Since my algorithm has
been
>declared as crap in it's current version, does anyone have
suggestions
>on how to fix it? Also, what aspects of it do people like?
Well don't mix the inputs to your 'non-linear F' by xoring
them. Look at IDEA for hints on making ciphers like that.
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!
------------------------------
Subject: Re: Arithmetic Coding
From: tomstd <[EMAIL PROTECTED]>
Date: Thu, 08 Jun 2000 03:48:10 -0700
In article <8hnjhv$oq6$[EMAIL PROTECTED]>, "steffen
markert" <[EMAIL PROTECTED]> wrote:
>Does anybody know about an implementation in C
>or a book or a paper with informations about adaptiv
>arithmetic coding?
Hmm that's a compression method, but yes, in "The Data
Compression Book" there are implementations of it. Try asking
in comp.compression
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: Eric Hambuch <[EMAIL PROTECTED]>
Subject: Re: Primitive element
Date: Thu, 08 Jun 2000 12:54:46 +0200
Jesper Stocholm wrote:
>
> you might have a point here. The material I have with me (HAC +
> Stinson) does not describe the selection of the generator of the group -
> at least as far as I can see. The generator alpha of the multiplicative
> group Z(p) has order (p-1), so the question is how to find this - as you
> correctly say. I was not aware of the test in Knuth - even though I
> browsed thru it to find some help ... but I'll give it another shot
> later.
The "Handbook of Applied Crytography" contains an algorithm to find a
prime p and a generator g: try algorithm 4.86.
Eric
------------------------------
** 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
******************************
