Cryptography-Digest Digest #121, Volume #14 Tue, 10 Apr 01 18:13:00 EDT
Contents:
Re: Dynamic Substitution Question (Mok-Kong Shen)
SHA256 VB Implementation ("Phil Fresle")
Re: Dynamic Substitution Question (newbie)
Re: Would dictionary-based data compression violate DynSub? (David Formosa (aka ?
the Platypus))
Re: Would dictionary-based data compression violate DynSub? (Mok-Kong Shen)
Bleichenbacher Attack on DSA ("vert")
Re: Delta patching of encrypted data (those who know me have no need of my name)
Re: Steganography with natural texts (Joe H Acker)
Re: Steganography with natural texts (John Bailey)
Re: Current best complexity for factoring? (=?iso-8859-1?Q?Claus_N=E4veke?=)
Frobenius map over q-adic integers (Ian Goldberg)
Re: Is this a block cipher? (John Savard)
2001 USENIX Annual Technical Conference (Becca Sibrack)
AES Inverse trick (alex)
----------------------------------------------------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Dynamic Substitution Question
Date: Tue, 10 Apr 2001 21:14:40 +0200
John Savard wrote:
>
> So I don't think anything involving a "virtual" table - unless the
> virtual table is a subterfuge for something that can be achieved by
> manipulating individual entries - can be considered novel. And if you
> manipulate individual entries directly, the normal result is that you
> can reach any state of the table - this is nowhere said in his patent,
> but it is a useful litmus test to determine if individual entries are
> really involved or not.
If the table is a substitution table (each column being
a permutation), dynamic change of the content of the
table is presumably the proper scope of DS. It could not
cover cases of other 'kinds' of tables (also dynamically
changed) and cases where there is no table at all, e.g.
xoring or adding two byte streams together (modulo 2^8)
to obtain a new stream or adding the outputs of a number
of PRNGs to get a combined stream (device of Wichmann
and Hill), which the text of the patent however seems
to claim to be within its scope.
M. K. Shen
------------------------------
From: "Phil Fresle" <[EMAIL PROTECTED]>
Subject: SHA256 VB Implementation
Date: Tue, 10 Apr 2001 20:36:06 +0100
Reply-To: "Phil Fresle" <[EMAIL PROTECTED]>
I have uploaded VB and VBScript implementations of SHA256 onto my web site
http://www.frez.co.uk
------------------------------
From: newbie <[EMAIL PROTECTED]>
Subject: Re: Dynamic Substitution Question
Date: Tue, 10 Apr 2001 15:33:20 -0300
It is not a good solution Dynamic Substitution as presented by Ritter.
It contains a very big hole.
You have just to analyze it carefully.
Using the combiner DS, reveal the sequence of the keystream.
Just try to analyze it before talking about claiming.
Claiming of what?
Something completely wrong.
Mok-Kong Shen wrote:
>
> John Savard wrote:
> >
>
> > So I don't think anything involving a "virtual" table - unless the
> > virtual table is a subterfuge for something that can be achieved by
> > manipulating individual entries - can be considered novel. And if you
> > manipulate individual entries directly, the normal result is that you
> > can reach any state of the table - this is nowhere said in his patent,
> > but it is a useful litmus test to determine if individual entries are
> > really involved or not.
>
> If the table is a substitution table (each column being
> a permutation), dynamic change of the content of the
> table is presumably the proper scope of DS. It could not
> cover cases of other 'kinds' of tables (also dynamically
> changed) and cases where there is no table at all, e.g.
> xoring or adding two byte streams together (modulo 2^8)
> to obtain a new stream or adding the outputs of a number
> of PRNGs to get a combined stream (device of Wichmann
> and Hill), which the text of the patent however seems
> to claim to be within its scope.
>
> M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (David Formosa (aka ? the Platypus))
Subject: Re: Would dictionary-based data compression violate DynSub?
Reply-To: [EMAIL PROTECTED]
Date: Tue, 10 Apr 2001 19:36:05 GMT
On Mon, 09 Apr 2001 12:08:45 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>
> "David Formosa (aka ? the Platypus)" wrote:
[...]
>> Ok that helps.
>
> For your information, Algorithm M is deterministic,
> so it can be undone/reversed, if wanted.
Just because it is deterministic doesn't mean it can be undone.
x^y mod p is almost impossable to undo for the correct x and p.
--
Please excuse my spelling as I suffer from agraphia. See
http://dformosa.zeta.org.au/~dformosa/Spelling.html to find out more.
Free the Memes.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Would dictionary-based data compression violate DynSub?
Date: Tue, 10 Apr 2001 22:04:37 +0200
"David Formosa (aka ? the Platypus)" schrieb:
>
> Mok-Kong Shen<[EMAIL PROTECTED]> wrote:
> >
> > "David Formosa (aka ? the Platypus)" wrote:
> [...]
> >> Ok that helps.
> >
> > For your information, Algorithm M is deterministic,
> > so it can be undone/reversed, if wanted.
>
> Just because it is deterministic doesn't mean it can be undone.
> x^y mod p is almost impossable to undo for the correct x and p.
For Algorithm M it is definitely possible to do so.
M. K. Shen
------------------------------
From: "vert" <[EMAIL PROTECTED]>
Subject: Bleichenbacher Attack on DSA
Date: Tue, 10 Apr 2001 16:05:28 -0700
I'm looking for a detailed description of this attack, beyond Bell Labs'
press
release and the CNN article. They only decent paper I've found online is
about
the Bleichenbacher PKCS attack, released in, I believe, 1998.
Thanks
------------------------------
From: [EMAIL PROTECTED] (those who know me have no need of my name)
Subject: Re: Delta patching of encrypted data
Date: Tue, 10 Apr 2001 20:24:59 -0000
<9aql2e$lv$[EMAIL PROTECTED]> divulged:
>Regrettably the diff program is third party....
my guess is that it requires plaintext, which means that you'll have to
decrypt your program, and at that point it will be snatched.
further, even if you didn't mind writing your own patching program,
using a diff or rsync/xdelta core, but with all input and output
consisting solely of ciphertext you'll be left with the problem of the
program having all the necessary keys (assuming asymmetric) embedded,
and that's yet another point of attack for the crackers.
--
okay, have a sig then
------------------------------
From: [EMAIL PROTECTED] (Joe H Acker)
Subject: Re: Steganography with natural texts
Date: Tue, 10 Apr 2001 22:22:21 +0200
Mok-Kong Shen <[EMAIL PROTECTED]> wrote:
> I failed to find the description of your optimal
> steganographic encoding. Could you give the reference
> of your article? Do you have details of that elsewhere
> that is available? Thanks.
I'm afraid that there's no good references for that available. My own
posts about it are rather imprecise and getting a clear
information-theoretic notion of optimal steganographic encoding is yet
work to be done. If I remember correctly, some former posts of Douglas A
Gwyn have pointed in a similar direction (but much more precisely, I'd
say). Please let me apologize if I've made the impression that this is a
well-established term in steganography.
Using an OTP and replacing random background noise with the ciphertext
to hide a message is an example of such an encoding. There is no way to
detect the hidden message without the key and offset.
Here are some points that imho are important when you want to get to a
general notion of optimal steganographic encoding (I'll abbreviate it
with OSE in the following):
1. Two sign systems and two different codes have to be related to each
other: (a) the carrier system/channel and (b) the steganographic
system/channel
2. The OSE is a code that maps the secret message into a sequence of
bits that (a) are redundant in the carrier signal (b) do not change any
observable statistical properties of the carrier system (i.e. of the
carrier system's signals in average or in principle---it seems that
choice leads to two different definitions)
Because of 2b, the OSE actually has to replace a redundant sequence of
bits of the carrier signal with another redundant sequence of bits of
the carrier signal and thereby encoding the secret message. For if it
would introduce new bits, the observable statistics might be changed
(this doesn't seem to hold in general and depends very much on the
definition of "observable statistical properties"). 2a is necessary
because if the bits were not redundant in the carrier signal, a new
source of error would be introduced into the carrier channel, violating
principle 2b.
One idealization and simplification could be to assume that the secret
message is a random sequence of bits. Later, one could see what happens
if it's pseudo-random output of a crypto algorithm. The OSE takes a
(pseudo) random sequence of bits and transforms it into a sequence of
bits that is a possible candidate for a sequence of redundant bits of
the carrier signal (and can transform it back). And in order to comply
to 2b, the OSE's output must produce steganographic signals that reflect
the probabilities of occurance (or frequencies observed so far in the
less idal case) of any alternative sequences of redundant bits that can
occur in carrier signals. In a last step that probably should have a
name by itself, a sequence of redundant bits of the carrier signal is
replaced by the output of the OSE. Additional diffusion over the carrier
signal's (larger) sequence of redundant bits based on a key seems to be
desirable but is an additional step.
That's the rough sketch of my ideas. If it sounds like bullshit, please
anyone feel free to tell me about it, but please also take some time to
explain to me why.
Regards,
Erich
------------------------------
From: [EMAIL PROTECTED] (John Bailey)
Subject: Re: Steganography with natural texts
Date: Tue, 10 Apr 2001 20:21:38 GMT
On Sun, 08 Apr 2001 22:47:30 +0200, Mok-Kong Shen
<[EMAIL PROTECTED]> wrote:
>
>Most modern stego schemes are based on embedding bits in
>pictures. A current thread in the group is discussing that.
>
>I suppose that a competitive way is to embed bits in natural
>language texts.
Combining thoughts inspired by your post with another current thread.
The other thread is the one which offered the challenge of dual
decryption, such that a key can be provided to authorities who demand
it without disclosing the real content of the message..
Use a simplistic subsitution encryption scheme a la the Captain
Midnight decoder ring in which each character in plaintext is paired
with one cyphertext character, but with the following modification.
Once the same substitution has been made twice, the
plaintext/cyphertext pairing list is advanced by 1. Because this
scheme reduces the opportunity to use letter frequency as a clue, this
offers a way to use simple substitution without the resulting
cryptoanalysis becoming quite as simple as solving a new york times
cryptogram. Such a scheme might be useful for hand encrypting. Now
for the stegano.
As each usage threshold is reached, the selection of the next
substitution symbol could be from multiple choices. In the simplest
case, suppose there are only two choices provided, the selection
embeds one bit. So, we have a means of hiding in superficially
encrypted material, one bit per every two characters of a
steganoverlay (on average)
This scheme also provides an answer to encryption where a totalitarian
authority can demand a key for decrytion. Only the choices used need
be disclosed.
John
------------------------------
From: =?iso-8859-1?Q?Claus_N=E4veke?= <[EMAIL PROTECTED]>
Subject: Re: Current best complexity for factoring?
Date: Tue, 10 Apr 2001 22:32:13 +0200
"Tim Gahnström /Bladerman" <[EMAIL PROTECTED]> schrieb im Newsbeitrag
news:Z%CA6.4065$[EMAIL PROTECTED]...
> Another thing. Are the numbers used in cryptografy usually so big
that I
> cannot assume that I know al the primes from 1 to the number I am
factoring?
> Or is that a "valid" asumption?
You only need the primes from 2 to sqrt(the number you are factoring)
Claus
------------------------------
From: [EMAIL PROTECTED] (Ian Goldberg)
Crossposted-To: sci.math
Subject: Frobenius map over q-adic integers
Date: 10 Apr 2001 20:51:41 GMT
[I've resubscribed to sci.math after a ~6 year absence... :-) ]
I've read a paper describing a new algorithm for counting points
on elliptic curves:
http://www.lix.polytechnique.fr/Labo/Mireille.Fouquet/FGH.ps.gz
"An Extension of Satoh's algorithm and it implementation" by
Fouquet, Gaudry, and Harley [FGH00].
I have a question, not about the algorithm itself, but merely about
one of the functions they define in the presentation of the algorithm.
If you've got the paper in front of you, my question is about section
2.3. If not, here's a summary:
p is a prime. q = p^d is a prime power.
F_p and F_q are the finite fields with p and q elements, respectively.
Z_p and Z_q are the rings of p-adic and q-adic integers, respectively
(these have respectively F_p and F_q as subrings; let \pi be the
projection map from Z_q to F_q).
Now they define the little Frobenius map \sigma: F_q -> F_q
in the usual way: \sigma(x) = x^p. It is straightforward that
\sigma is a ring automorphism:
\sigma(xy) = (xy)^p = x^p y^p = \sigma(x) \sigma(y)
\sigma(x+y) = (x+y)^p = x^p + y^p + p(stuff) = x^p + y^p
= \sigma(x) + \sigma(y)
[since the ring F_q we're working in has characteristic p]
OK, so far, so good. Then they go and define a function \Sigma
on the q-adic integers Z_q, in the following roundabout way:
Define the Teichmuller lift w : F_q -> Z_q as the function which
maps x in F_q to the unique element z of Z_q such that
\pi(z) = x, and z is a (q-1)th root of unity in Z_q.
w is clearly multiplicative [w(x)w(y) is certainly a (q-1)th root
of unity and \pi(w(x)w(y)) = xy, so w(x)w(y) = w(xy)]. w is *not*
additive.
Define the semi-Witt decomposition of x \in Z_q as the unique sequence
(x_0, x_1, ...) of elements of F_q such that
x = \sum_{i>=0} w(x_i)p^i
Semi-Witt decompositions are neither multiplicative nor additive.
It is straightforward to see that both these things are well-defined.
Now here's the Frobenius map \Sigma: Z_q -> Z_q :
Take x \in Z_q, and find its semi-Witt decomposition (x_0, x_1, ...).
Take the little Frobenius map of each element (in F_q):
({x_0}^p, {x_1}^p, ...)
\Sigma(x) is then the element of Z_q with *that* as its semi-Witt
decomposition; i.e.
\Sigma(x) = \sum_{i>=0} w({x_i}^p) p^i
= \sum_{i>=0} {w(x_i)}^p p^i
Alright, I believe it's well-defined, and straightforward to calculate.
I even coded it up in Maple.
[If you didn't get the definitions from my summary, you might check
the paper at the above URL; it's more detailed than I wanted to
put in a Usenet post.]
My question is: WHY is \Sigma a ring automorphism on Z_q? It's certainly
used that way in the paper, and calculating it on random values
with Maple certainly suggests it's both additive and multiplicative.
I'd greatly appreciate if anyone had a suggestion as to why \Sigma is
in fact a ring automorphism.
Thanks,
- Ian
------------------------------
From: [EMAIL PROTECTED] (John Savard)
Subject: Re: Is this a block cipher?
Date: Tue, 10 Apr 2001 20:32:02 GMT
On Mon, 09 Apr 2001 01:28:03 GMT, "Mr. Smith"
<[EMAIL PROTECTED]> wrote, in part:
>However, the block ciper is a bit confusing. Does it work like the example
>below?
Yes; your example is a polygraphic cipher on letters, transforming
trigraphs to trigraphs, but a block cipher transforms 64-bit blocks to
64-bit blocks, with the same principle.
And, as you also show, using a different key changes the substitution.
A key is something that changes the cipher, and is convenient to store
and change, and which causes enough difference in the substitution
that, even if the method is known, not knowing the key is enough to
prevent people from reading messages.
John Savard
http://home.ecn.ab.ca/~jsavard/crypto.htm
------------------------------
From: Becca Sibrack <[EMAIL PROTECTED]>
Subject: 2001 USENIX Annual Technical Conference
Date: Tue, 10 Apr 2001 14:17:28 -0700
2001 USENIX Annual Technical Conference
June 25-30, 2001
Marriott Copley Place Hotel
Boston, Massachusetts, USA
http://www.usenix.org/events/usenix01/
==============================================
REGISTER BY May 25, 2001 and Save up to $200!
==============================================
The USENIX Annual Technical Conference has always been the gathering
place for like minds in the computer industry. USENIX ¹01 provides
tutorials that help master new and important skills and opportunities,
and is a place to meet peers and experts to share solutions to common
problems.
USENIX ¹01 offers professional-level tutorials, three technical tracks,
an AFS workshop, a GNOME developers conference, an information-laden
vendor exhibition, Birds-of-a-Feather Sessions, Work-in-Progress
Reports, parties and get-togethers for sys admins, programmers, systems
engineers and researchers.
DON¹T MISS OUT! Thirty tutorials in all, seventeen brand-new. Here¹s a
sampling:
-Network Programming with Perl
-Solaris Administration
-Building Linux Applications
-Large Heterogeneous Networks
-Practice Wireless IP Security
-Running Secure Web Servers
-Network Security
-Advanced Solaris Administration
-Unix Network Programming
-LDAP
Keynote address by Daniel D. Frye, Director of IBM Linux Technology
Center.
Invited Talks on WAP, IP Wireless Networking, Security Aspects of
Napster and Gnutella, Security For E-voting in Public Elections, Virtual
Machines, Online Privacy, Active Content and Secure DNS.
The USENIX Annual Technical Conference Exhibition features ~100
companies, products and services. For more information, please contact
Dana Geffner at [EMAIL PROTECTED]
=====================================================================
The 2001 USENIX Annual Technical Conference is sponsored by
USENIX, the Advanced Computing Systems Association. www.usenix.org
=====================================================================
------------------------------
From: alex <[EMAIL PROTECTED]>
Subject: AES Inverse trick
Date: Tue, 10 Apr 2001 22:34:54 +0100
Hello.
I'm doing a project using Rijndael as the private key encryption
algo. I'm following the steps provided in the AES.
I've managed to create an algorithm capable of obtaining the
Multiplicative inverse on GF(2^8) by using a version of the Extended
euclidean algorithm.
The process is however very very slow since it implies translating
the number on GF(2^8) to a polynomial form and operating accordingly.
I've seen through some previous posts to the newsgrop and various
other papers, that they use a different and much easier process:
for values of i > than 0 and < than 256
log[pow[i] = j] = i
where j = j XOR (j << 1) if j < 0x80
j = j XOR (j <<1 ) ^ 0x11b if j > 0x80;
==================================
then:
for values of i > than 1 and < 256
j = pow[255 - log[i]]
....
(not complete)
I believe that the outcome of the previous operations does give out the
Inverse.
I've been unable to find a description of the previous process anywhere,
and it will take away the point of the project to use a mathematical
equation which i can't understand the base of.
Would someone be kind enough to either explain to me what is the base of
the previous or to give me some directions on where i can find the
description for the process described above?.
Thank you in advance.
Alex
------------------------------
** 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
******************************
