Cryptography-Digest Digest #346, Volume #13 Sat, 16 Dec 00 22:13:00 EST
Contents:
Re: Q: Result of an old thread? (Chris Monico)
Re: Encryption detail added to cipher page ("r.e.s.")
Re: Encryption detail added to cipher page ("r.e.s.")
Re: Encryption detail added to cipher page (Jim Gillogly)
Re: weten we die PIN? (z0ne)
Discrete log problems in F-Functions. ("Simon Johnson")
Re: A challenge (daniel mcgrath)
Re: Encryption detail added to cipher page ("r.e.s.")
----------------------------------------------------------------------------
From: [EMAIL PROTECTED] (Chris Monico)
Subject: Re: Q: Result of an old thread?
Date: Sat, 16 Dec 2000 22:57:33 GMT
On Fri, 15 Dec 2000 19:59:51 +0000, Simon Best
<[EMAIL PROTECTED]> wrote:
>Mok-Kong Shen wrote:
>>
>> Quite a time ago someone posted a scheme of transmission of
>> message without using a shared secret key as follows (all
>> matrices are of the same size):
>>
>> The message is in a singular matrix S (e.g. one with a zero
>> column). Alice chooses an arbitrary non-singluar matrix A
>> and sends AS to Bob.
>
>And, unbeknownst to Alice and Bob, AS is intercepted by me...
>
>> Bob chooses an arbitrary non-singular matrix B and sends ASB
>> to Alice.
>
>And, again, I intercept ASB...
>
>> Alice multiplies it with A^(-1) and sends SB to Bob, who can
>> multiply it with B^(-1) to obtain S.
>
>While I intercept SB, too...
>
>> If my memory is correct, nobody has commented at that time
>> whether the scheme is secure or not (or how secure it is).
>> Does anyone know more about the issue or can say something
>> concrete about the security of the scheme? Thanks.
>>
>> M. K. Shen
>
>Correct me if I am making a basic blunder with basic matrix arithmetic
>here, but now that I have AS, ASB, and SB, can't I just get the
>multiplicative inverse of AS, multiply that by ASB, and end up with B?
This is the first message in this thread (or on this topic, for that
matter) that I've read, but it seems to me you have overlooked a small
detail: If $S$ is singular, $AS$ is not invertible. That's pretty much
the point of the _supposed_ security. However, I don't believe that it
is secure.
Consider the following approach:
Given: F:= AS, G := ASB and H := SB, all n x n matrices (presumably
over a [finite] field)
Find: S
Step 1) Find an invertible matrix, Y, such that YH=G. Notice that such
a 'Y' is not unique. In particular, it is possible that Y != A. I will
explain in a moment how to do this, but let me first show why it works
even if Y != A.
Step 2) Compute Y^{-1}F. I claim that this is S. Why?
Y^{-1}F = Y^{-1}AS
= Y^{-1}AS(BB^{-1})
= Y^{-1}(ASB)B^{-1}
= Y^{-1}GB^{-1}
= HB^{-1}
= S
Thus, we need not find A (or B) to get the secret. It suffices to find
_any_ invertible matrix Y such that YH=G.
Note: This is precisely because 'S' doesn't have full rank. If S had
full rank, the solution would be unique and trivial to find. The
smaller the rank becomes, the more solutions of Y there are. Let me
now describe how to find a Y:
Let Y=(y_{ij}). That is, let Y be a variable matrix whose entries are
each assigned variable names. Since H is known, one may symbolically
compute the product YH. Now, equating each entry of this symbolic
product to each corresponding entry of G
(y_{ij})H = G
One obtains a system of n^2 linear equations in the n^2 unknowns
y_{ij}. That is, if H=(h_{ij}) and G=(g_{ij}) we get the system
g_{11} = \sum_{k=1}^{n} y_{1k}h_{k1}
g_{12} = \sum_{k=1}^{n} y_{1k}h_{k2}
...
g_{nn} = \sum_{k=1}^{n} y_{nk}h_{kn}
Since G does not have full rank, this system doesn't have full rank
either. In fact, if rank(H) = s<n, the rank of this system of
equations is s^2 < n^2.
Then one may perform elementary operations on the system to get it
into row-reduced echelon form, and thus obtain an equivalent system of
s^2 equations in the n^2 unknowns.
Note: This system is necessarily has a solution, since we know apriori
that 'A' is a solution.
The naive thing to do at this point is to make arbitrary choices for
n^2-s^2 of the variables y_{ij} and use the system of eqs to determine
the rest. However, it may be the case that the resulting solution is
not invertible. So we need to insure invertibility. I haven't worked
out the details at this point, but I believe that one can show the
following:
Choose n^2-s^2 of the variables y_{ij} that form an s x s submatrix of
Y (i.e., they are all in the same 's' rows and the same 's' columns)
and values of these y_{ij} that make the submatrix invertible. Then
solve for the remaining varaibles to obtain a solution, Y, which is
invertible.
I have an idea of how to show this (assuming it's true) but it's
rather tedious. If you're really interested, drop me an email and I'll
see if I can work out the details.
Cheers,
Chris
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Encryption detail added to cipher page
Date: Sat, 16 Dec 2000 15:58:15 -0800
"Jim Gillogly" <[EMAIL PROTECTED]> wrote ...
| Gianna Stefani wrote:
| >
| > Xi has now added encryption details, and some clues, to its cipher
| > challenge page
| >
| > http://www.xarabungha.btinternet.co.uk/xicrypt/xichallenge.htm
| >
| > All attacks welcomed I think . . .
|
| The page says it's encrypted with a mixed-alphabet (26 different
| random alphabets) Vigenere-type cipher with a repeating key shorter
| than the length of the plaintext, followed by a keyed transposition
| cipher of unspecified type with a relatively short key.
That page says:
" 1) The text was encrypted using a Vigenère type cipher
" in which each of the 26 possible cipher alphabets was
" randomly generated then fixed into the square. This means
" that none of the cipher alphabets is the same as the plain
" alphabet, and none are simple Caesar Shift as they would
" be in the original Vigenère Square. A key word of a certain
" length was used.
"
" 2) The text output from step (1) was then further encrypted
" using an irregular Transposition process. A key number was
" used to determine the size of the text blocks to be moved.
Q1:
Isn't it quite ambiguous just how "A key word of a certain
length was used." ? How do we know it was a repeating key?
Q2:
Couldn't "an irregular Transposition process" be a at least
a double transposition?
| Sounds potentially solvable if the transposition type were known.
| The transposition can be solved independent of the polyalphabetic
| using a scoring function that rewards good IC peaks or repeated
| strings. The resulting mixed-alphabet Vig could then be solved
| using standard methods given enough ciphertext or cribs -- this
| is like the "Fuer GOD" cipher of World War I. I think I've
| eliminated simple incomplete columnar transposition as the
| transposition type.
If the key mentioned in (1) were not "repeating", but instead
seeds a PRNG to produce 26 pseudo-randomly permuted alphabets,
and the key mentioned in (2) were used to perform an irregular
double transposition, how would this affect your assessment of
"solvability" (given only the plaintext provided)?
| The IC of the ciphertext is 0.042, which is high for random text.
| This suggests the Vig keyword is relatively short. With a long
| keyword the IC approaches 0.038, and with keyword 1 it's about
| 0.066. Sinkov suggets period 5 typically has an IC of about 0.044
| and period 10 about 0.041, so a period between 5 and 10 would be
| credible for the Vigenere key. A thrice-repeated trigraph (YRO)
| appears at intervals divisible by 7, so I'll guess the Vig has
| period 7. This could result from three repeated chunks in the
| plaintext encrypted by the same part of the key that are
| significantly longer than the chunk size of the transposition.
Don't those remarks apply only if the cipher is really of the
"repeating keyword" variety?
--r.e.s.
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Encryption detail added to cipher page
Date: Sat, 16 Dec 2000 17:02:23 -0800
oops ...correction:
"r.e.s." wrote ...
| If the key mentioned in (1) were not "repeating", but instead
| seeds a PRNG to produce 26 pseudo-randomly permuted alphabets,
| and the key mentioned in (2) were used to perform an irregular
| double transposition, how would this affect your assessment of
| "solvability" (given only the plaintext provided)?
^^^^^^^^^
ciphertext
------------------------------
From: Jim Gillogly <[EMAIL PROTECTED]>
Subject: Re: Encryption detail added to cipher page
Date: Sat, 16 Dec 2000 17:18:24 -0800
"r.e.s." wrote:
>
> "Jim Gillogly" <[EMAIL PROTECTED]> wrote ...
> | Gianna Stefani wrote:
> | >
> | > Xi has now added encryption details, and some clues, to its cipher
> | > challenge page
> | >
> | > http://www.xarabungha.btinternet.co.uk/xicrypt/xichallenge.htm
> | >
> | > All attacks welcomed I think . . .
> |
> | The page says it's encrypted with a mixed-alphabet (26 different
> | random alphabets) Vigenere-type cipher with a repeating key shorter
> | than the length of the plaintext, followed by a keyed transposition
> | cipher of unspecified type with a relatively short key.
>
> That page says:
>
> " 1) The text was encrypted using a Vigenère type cipher
> " in which each of the 26 possible cipher alphabets was
> " randomly generated then fixed into the square. This means
> " that none of the cipher alphabets is the same as the plain
> " alphabet, and none are simple Caesar Shift as they would
> " be in the original Vigenère Square. A key word of a certain
> " length was used.
> "
> " 2) The text output from step (1) was then further encrypted
> " using an irregular Transposition process. A key number was
> " used to determine the size of the text blocks to be moved.
>
> Q1:
> Isn't it quite ambiguous just how "A key word of a certain
> length was used." ? How do we know it was a repeating key?
The page also says the key is considerably smaller (in length)
than the plaintext. That means the key is re-used, which by
my usage means "repeating". It could be interrupted key, progressive
key, or something else, but in any case it must be re-used in some
way. Most likely it's periodic, as in normal Vig-like usage.
> Q2:
> Couldn't "an irregular Transposition process" be a at least
> a double transposition?
Yes. What's your point? Double transpositions are also
potentially solvable. He also said the transposition key
is smaller than the substitution key, for what it's worth.
> If the key mentioned in (1) were not "repeating", but instead
> seeds a PRNG to produce 26 pseudo-randomly permuted alphabets,
You haven't said how a plaintext letter is encrypted in your
model. If, after the 26 alphabets were selected, the PRNG was
continued to pick each letter of them in turn, then the IC would
be closer to 0.038 given this much ciphertext. That means not
all of the alphabets are used in the encryption.
> and the key mentioned in (2) were used to perform an irregular
> double transposition, how would this affect your assessment of
> "solvability" (given only the plaintext provided)?
> | The IC of the ciphertext is 0.042, which is high for random text.
> | This suggests the Vig keyword is relatively short. With a long
> | keyword the IC approaches 0.038, and with keyword 1 it's about
> | 0.066. Sinkov suggets period 5 typically has an IC of about 0.044
> | and period 10 about 0.041, so a period between 5 and 10 would be
> | credible for the Vigenere key. A thrice-repeated trigraph (YRO)
> | appears at intervals divisible by 7, so I'll guess the Vig has
> | period 7. This could result from three repeated chunks in the
> | plaintext encrypted by the same part of the key that are
> | significantly longer than the chunk size of the transposition.
>
> Don't those remarks apply only if the cipher is really of the
> "repeating keyword" variety?
No. The too-high IC is an observed phenomenon that should have some
explanation. It means that a relatively small number of alphabets
was used before the transposition step. The repeated trigraph
observation is speculative, and could be the result of pure chance,
but it seems a reasonable guess if you're looking for an entry, and
suggests a relatively small chunk size for the transposition, whatever
kind it happens to be.
--
Jim Gillogly
27 Foreyule S.R. 2000, 01:05
12.19.7.14.10, 8 Oc 13 Mac, Second Lord of Night
------------------------------
From: z0ne <[EMAIL PROTECTED]>
Subject: Re: weten we die PIN?
Date: Sun, 17 Dec 2000 02:33:28 +0100
Crossposted-To:
alt.cracks.nl,alt.nl.telebankieren,nl.comp.crypt,nl.financieel.bankieren,nl.juridisch
On Fri, 15 Dec 2000 14:44:30 +0100, "Erwin Graumans" <me@home> wrote:
>> 300 Baud zou ik niet snel willen noemen.......... en de meeste PIN
>> automaten en apparaten hebben een 300 Baud modem + een veredelde
>> telefoonlijn naar de bank.
>300 Baud?? Dat is allang achterhaald: het gaat via huurlijnen met een grote
>bandbreedte.
Woah?? Mijn kapper heeft een huurlijn met een grote bandbreedte?? Dan
zet ik mijn 31337 warez server daar neer!! Veel goedkoper dan zelf
ADSL nemen! ;-)))
Ik denk dat die PIN automaten tegenwoordig op ISDN lijnen zitten..
Maar ik heb er ook wel eens staan wachten dat je in gedachten de
handshake hoorde... prii-prii-priiiiii grrrgtrrrr... ;-)
--
z0ne / [EMAIL PROTECTED]
'All my life I wanted to be some-one.
I guess I should have been more specific.. ' - Jane Wagner
------------------------------
From: "Simon Johnson" <[EMAIL PROTECTED]>
Subject: Discrete log problems in F-Functions.
Date: Sun, 17 Dec 2000 01:40:42 -0000
Lets say we have a Feistel network, where the f-function is defined as:
F(X,K) {
X^K mod p
}
where p is a very large prime, is the resultant cipher as hard to break as
taking a discrete logrithm to find k?(presuming K is generated in a
statically random fashion from some K)
Clearly a cipher based on such methodology would be slow and therefore
unusable. Though, for really high security applications, a provably secure
algorithm would be nice. I'm just wondering if my reasoning is correct?
Simon.
------------------------------
From: [EMAIL PROTECTED] (daniel mcgrath)
Subject: Re: A challenge
Date: Sun, 17 Dec 2000 01:52:01 GMT
On Thu, 07 Dec 2000 02:51:35 GMT, [EMAIL PROTECTED] wrote:
>I'm developing a cypher for a game and would like the encoded message
>to be breakable without extensive use of a computer. Since I know the
>cypher I am hardly a good judge of how difficult it is to crack.
>Therefore, I am putting out the challenge to any of you to break the
>encoded text that follows.
>
>And no, this has nothing to do with school.
>
>Thanks!
>
>E panumfhhna fa obk sngei oqbo hhuqvxajf md lnwlx. N ekav hud ayhhm wm
>ghcgxcdb paqnh wjcah xn pa lipa. O megu uffc uaq thrtpf. Ylu ocmoka
>uk Ftfjlkai yaeawqj nh ome jrkk. Tgpm sie wm kaswq pkdbf zlo libbr
>obkrw rrerfvdjfwpv, maaaak owq yii rl mxx, mgkk ive qbufaxl nd ivelq
>zvrhpj.
>
>L paa quqshdcy prmpadth njog ncfwjrfy ums xkfsn rliofend hmaollh kxgns
>dntplib. M qbb ivep lvhs. B mpeuq naju jwajtv wjsae abwwwfspeesl. W
>itt eral lyclvx hludt lvigpfqjp. P bmm cpyfk jvmgp; c eqhbk wjoo fvvnr
>bjqp.
>
>T hixlm yiqq wessydr ko d wkiojbbt zmvs doff rxrf xr dvsdpddjps, tn ubo
>fsb nde nojrxkdhpvfxa nd Ftfjlkai gsv gmgu lyhe wycsrme im cpy
>tufgefwxlhyr pf sudse.
>
>B hss najqv kwnhq tvuuxxnxl xxe...
>
>
>Pendergarth
I would like to know the solution to this and the encryption system
used. I tried working on it for a while and gave up, read the thread
on my news server and on Deja.com, and still can't get it. Can you
give me any further hints, Bramaen? I'll then take it from there.
==================================================
daniel g. mcgrath
a subscriber to _word ways: the journal of recreational linguistics_
http://www.wordways.com/
------------------------------
From: "r.e.s." <[EMAIL PROTECTED]>
Subject: Re: Encryption detail added to cipher page
Date: Sat, 16 Dec 2000 18:12:43 -0800
"Jim Gillogly" <[EMAIL PROTECTED]> wrote ...
| "r.e.s." wrote:
| > "Jim Gillogly" <[EMAIL PROTECTED]> wrote ...
| > | Gianna Stefani wrote:
| > | >
| > | > Xi has now added encryption details, and some clues, to its
cipher
| > | > challenge page
| > | >
| > | > http://www.xarabungha.btinternet.co.uk/xicrypt/xichallenge.htm
| > | >
| > | > All attacks welcomed I think . . .
| > |
| > | The page says it's encrypted with a mixed-alphabet (26 different
| > | random alphabets) Vigenere-type cipher with a repeating key
shorter
| > | than the length of the plaintext, followed by a keyed
transposition
| > | cipher of unspecified type with a relatively short key.
| >
| > That page says:
| >
| > " 1) The text was encrypted using a Vigenère type cipher
| > " in which each of the 26 possible cipher alphabets was
| > " randomly generated then fixed into the square. This means
| > " that none of the cipher alphabets is the same as the plain
| > " alphabet, and none are simple Caesar Shift as they would
| > " be in the original Vigenère Square. A key word of a certain
| > " length was used.
| > "
| > " 2) The text output from step (1) was then further encrypted
| > " using an irregular Transposition process. A key number was
| > " used to determine the size of the text blocks to be moved.
| >
| > Q1:
| > Isn't it quite ambiguous just how "A key word of a certain
| > length was used." ? How do we know it was a repeating key?
|
| The page also says the key is considerably smaller (in length)
| than the plaintext. That means the key is re-used, which by
| my usage means "repeating". It could be interrupted key,
progressive
| key, or something else, but in any case it must be re-used in some
| way. Most likely it's periodic, as in normal Vig-like usage.
It's the "something else" that I was wondering about,
e.g., a pseudo-random "running key".
Wouldn't it be reasonable to suppose the OP wants to
minimize periodicity?
| > Q2:
| > Couldn't "an irregular Transposition process" be a at least
| > a double transposition?
|
| Yes. What's your point? Double transpositions are also
| potentially solvable. He also said the transposition key
| is smaller than the substitution key, for what it's worth.
I was only thinking that if each stage were considerably
less solvable than you'd seemed to allow, then the
combination may be much less so, especially with only
the one given sample of ciphertext.
| > If the key mentioned in (1) were not "repeating", but instead
| > seeds a PRNG to produce 26 pseudo-randomly permuted alphabets,
|
| You haven't said how a plaintext letter is encrypted in your
| model. If, after the 26 alphabets were selected, the PRNG was
| continued to pick each letter of them in turn, then the IC would
| be closer to 0.038 given this much ciphertext. That means not
| all of the alphabets are used in the encryption.
What I had in mind was encrypting successive plaintext
letters using pseudo-randomly selected alphabets, e.g.,
with a "running key".
| > and the key mentioned in (2) were used to perform an irregular
| > double transposition, how would this affect your assessment of
| > "solvability" (given only the plaintext provided)?
|
| > | The IC of the ciphertext is 0.042, which is high for random
text.
| > | This suggests the Vig keyword is relatively short. With a long
| > | keyword the IC approaches 0.038, and with keyword 1 it's about
| > | 0.066. Sinkov suggets period 5 typically has an IC of about
0.044
| > | and period 10 about 0.041, so a period between 5 and 10 would be
| > | credible for the Vigenere key. A thrice-repeated trigraph (YRO)
| > | appears at intervals divisible by 7, so I'll guess the Vig has
| > | period 7. This could result from three repeated chunks in the
| > | plaintext encrypted by the same part of the key that are
| > | significantly longer than the chunk size of the transposition.
| >
| > Don't those remarks apply only if the cipher is really of the
| > "repeating keyword" variety?
|
| No. The too-high IC is an observed phenomenon that should have some
| explanation. It means that a relatively small number of alphabets
| was used before the transposition step. The repeated trigraph
| observation is speculative, and could be the result of pure chance,
| but it seems a reasonable guess if you're looking for an entry, and
| suggests a relatively small chunk size for the transposition,
whatever
| kind it happens to be.
I was questioning the interpretation of IC in terms of keyword
length, if the keyword were not being used periodically.
--r.e.s.
------------------------------
** 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
******************************
