Cryptography-Digest Digest #395, Volume #14 Sun, 20 May 01 10:13:00 EDT
Contents:
Re: CIA Kryptos last 97 characters ("Ferdinando Stehle")
Re: Single-cycle sbox question (David Wagner)
Re: Single-cycle sbox question (David Wagner)
Strengthened TC15 against the SAC bias ("Tom St Denis")
Re: Single-cycle sbox question (SCOTT19U.ZIP_GUY)
Re: Help with a message ("Amethyste")
Draft of TC15a paper ("Tom St Denis")
Re: CIA Kryptos last 97 characters (Gary Warzin)
Re: Apology to Cloakware (open letter) ("Brian Hetrick")
Re: What about SDD? ("Harris Georgiou")
----------------------------------------------------------------------------
From: "Ferdinando Stehle" <[EMAIL PROTECTED]>
Subject: Re: CIA Kryptos last 97 characters
Date: Sun, 20 May 2001 11:16:48 GMT
Gary Warzin ha scritto nel messaggio
<2uxN6.2372$[EMAIL PROTECTED]>...
>I had a chance to see Kryptos up close a couple of weeks ago. Since then
I've
>been working on the remaining 97 characters. I've noticed something
>"interesting" that may indicate that there is an underlying table "hidden"
>under the message. Anyone else working on this?
>
>I've posted some notes at www.iquest.net/~gwarzin.
>
Hi Gary,
i've been working on Kryptos since 1999.
I've visited your site and, sorry, but i don't agree with you, for the
following reasons:
- the solution of the first part (PALIMPSEST) gave NO cribs to the second
one;
and the method used was a "linear" Vigenere table.
- the solution of the second one (ABSCISSA) gave absolutely NO cribs to the
solution of the third;
and the method used was the same "linear" Vigenere table.
- the solution of the third part was a "simple" transposition:
let's say P(x) the letter of plaintext at position X=0..337
C(y) the letter of the ciphertext ta position Y=0..337
the transposition is: C(y) = P((y*191 + 192) mod 337)
...so, WHY the first+second+third parts should give cribs to the solution of
the fourth one ?
...and, WHY should be the method of the fourth part so complex ? (a hidden
text, a broken Vigenere table,
such an obscure mechanism of encryption) ?
may be i'm wrong, but, for the moment, you've not convinced me.
best wishes
Ferdinando
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Single-cycle sbox question
Date: 20 May 2001 11:22:16 GMT
Benjamin Goldberg wrote:
>temp = random_permutation
>for( i = 0 to N-2 ) {
> sbox[ temp[i] ] = sbox[ temp[i+1] ];
>sbox[ temp[N-1] ] = sbox[ temp[0] ];
>
>Now, while I know that method two is of course much, much, faster than
>method one, I *don't* know whether or not it can produce all possible
>single-cycle sboxes, or whether it is biased.
Yes, this can produce all possible single-cycle sboxes,
and no, it is not biased. See the analysis below.
Let S,T be the permutations represented by sbox[], temp[]
after the above completes. Then this algorithm ensures
S(T(i)) = T(i+1) for all i,
i.e.,
S o T = T o C
where C is the cyclic permutation C(i) = i+1. From the above,
S = T o C o T^{-1}.
Now suppose S = S' (where S was produced from T, S' from T').
Then we have
T o C o T^{-1} = S = S' = T' o C o T'^{-1}.
This implies that
C o T^{-1} o T' = T^{-1} o T' o C,
so letting U = T^{-1} o T', we have that
C o U = U o C.
There are N solutions to this equation, call them U_1,..,U_N,
and the list of solutions does not depend on T or T'. (The
solution U_i is given by C^i.) Thus we see that if S = S',
then T' = T o U_i for some i. In other words, for any given
S, there are exactly N choices of T that lead to S, and of
course this number does not depend on the choice of S.
Moreover, there are exactly (N-1)! possible values of S and
N! possible values of T, as may be readily checked. Since
T is uniformly distributed, this means that S is, too. So
there are no biases in S.
------------------------------
From: [EMAIL PROTECTED] (David Wagner)
Subject: Re: Single-cycle sbox question
Date: 20 May 2001 11:31:21 GMT
Bryan Olson wrote:
> For any single-cycle permutation c(x) on set S,
> if P(x) is selected at random from the uniform
> distribution of all permutations on S, then
> P(c(P^-1(x))) is uniformly distributed over all
> single-cycle permutations on S.
Right. By the way, if you're interested in this, you
might be interested in recent work on a generalization:
Moni Naor and Omer Reingold: ``Constructing Pseudo-Random Permutations
with a Prescribed Structure'', J. Cryptology, 2001.
http://www.wisdom.weizmann.ac.il/~naor/PAPERS/cycle_abs.html
http://link.springer-ny.com/link/service/journals/00145/contents/01/0008/
Their work shows how to construct a single-cycle
permutation S so that S(i) may be computed in O(1) time,
with no precomputation required, and so that S need not
be generated or stored explicitly (only O(1) storage needed).
Compare to the method under discussion, which requires
an O(N) precomputation and O(N) storage to be able to
compute S(i) in O(1) time.
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Strengthened TC15 against the SAC bias
Date: Sun, 20 May 2001 12:10:55 GMT
As Scott pointed out there were nasty SAC biases in the original TC15. I
modified the linear transform to rotate D as well. In my trials it appears
there are no good SAC biases in common (i.e not a fixed bias).
New source and asm code and speed binary are on the website.
http://tomstdenis.home.dhs.org/tc15a.c
http://tomstdenis.home.dhs.org/tc15a_asm.zip
http://tomstdenis.home.dhs.org/tc15a_spd.exe
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
From: [EMAIL PROTECTED] (SCOTT19U.ZIP_GUY)
Subject: Re: Single-cycle sbox question
Date: 20 May 2001 12:14:09 GMT
[EMAIL PROTECTED] (David Wagner) wrote in
<9e89u9$57f$[EMAIL PROTECTED]>:
>Bryan Olson wrote:
>> For any single-cycle permutation c(x) on set S,
>> if P(x) is selected at random from the uniform
>> distribution of all permutations on S, then
>> P(c(P^-1(x))) is uniformly distributed over all
>> single-cycle permutations on S.
>
>Right. By the way, if you're interested in this, you
>might be interested in recent work on a generalization:
>
>Moni Naor and Omer Reingold: ``Constructing Pseudo-Random Permutations
>with a Prescribed Structure'', J. Cryptology, 2001.
>http://www.wisdom.weizmann.ac.il/~naor/PAPERS/cycle_abs.html
>http://link.springer-ny.com/link/service/journals/00145/contents/01/0008/
>
The first link Mr Wagner gives goes nowhere. OR else site looking
for those in a closed club. The second one is definitely for the
closed club. Maybe they have finally looked at scott16u and scott19u.
The point is you should be able to construct your single cycle permuatation
quite rapidly using snippets from my C code. THe scott19u for example
is over half a million entries. And quickly allows any such table
to be built or used.
David A. Scott
--
SCOTT19U.ZIP NOW AVAILABLE WORLD WIDE "OLD VERSIOM"
http://www.jim.com/jamesd/Kong/scott19u.zip
My website http://members.nbci.com/ecil/index.htm
My crypto code http://radiusnet.net/crypto/archive/scott/
MY Compression Page http://members.nbci.com/ecil/compress.htm
**NOTE FOR EMAIL drop the roman "five" ***
Disclaimer:I am in no way responsible for any of the statements
made in the above text. For all I know I might be drugged or
something..
No I'm not paranoid. You all think I'm paranoid, don't you!
------------------------------
From: "Amethyste" <[EMAIL PROTECTED]>
Subject: Re: Help with a message
Date: Sun, 20 May 2001 12:56:35 GMT
Letter Z seems a good candidate for <space>, giving the following
cryptogram:
YMAUV Z TPF Z IPC Z KDX Z XNUXJIPUTKE Z IX Z ALSQS
NU Z JPJ Z UMPOBADV Z FX Z MADAMQ Z HAXE Z YJZYPDSQH Z B
MYKAE Z LAKXF Z SMA Z JPJ Z UMPOBADV Z UJK Z YXYDQFXS
BQH Z SPYVMOBA Z IX Z YSS Z K Z RXLC Z IMBPJX Z AGJPUI Z NA Z
JEA Z IWPFVKQU Z YMMAX Z UMBNY Z DAI Z EAMKT Z Q
TOMI Z NO Z UMAYFY Z SK Z GSQ Z PR Z IPFM Z DFEHCFH Z SE
H Z RNCIT Z OTEVKF Z YCAUYAXINPQ Z OKL Z KDCFA Z M
PUEMAE Z TPFM Z QXKYXMO Z NFJX Z JMEFQH Z MASU Z E
JPJ Z QPGOFJ Z TV Z UJK Z UJJ Z OXYLCF Z YM
F Z NCXXXVO Z JI Z NCXHFYMQC Z XSMHY Z JMKB Z KFKPDAY
TYKKBE Z TVOFF Z K Z QPGOFJ Z TIZEJP Z FTVD Z IX Z OFSNK
T Z PQF Z EJP Z GFVY Z EFBTVA Z S Z VAGPJX Z OAIWPE Z X
C Z TECJMGTEV Z FV Z KQU Z YMNO Z NNQK Z MAPPMCF Z K EU
MINPQAQ Z NXJV Z AUE Z A Z XJEOXDLXEY Z EFQST Z CJM
Z OXYLCNYH Z SLCSPYFO Z NF Z UXFH Z IX Z KWXME Z KDX
Z OMYPOX Z XC Z GAJEV Z MQ Z YMCYLKAYTXU Z OT Z NXMO
JEO Z JKPXM Z YMAU Z HXLCVAKI Z YMFJXIPCF Z PQBE Z RN
JYK Z CTRA Z NNQK Z JPCHZYMF Z JXVY Z NNQK
Z LA Z WXME Z NY Z NXLKU Z RX Z FKYNAC Z IPC Z LPI
W Z PR Z PO Z IX Z HCXNZHXLC Z MAPPMCFGX
EY Z SK Z K Z UBKGF Z PR Z TPFM Z XMXPYNUB Z EP Z MAUEXBX
MO Z NXLKU Z RX Z NUWXQWFH Z NXJVNUB Z
WKCU Z PQ Z TPFM Z NCXTXYY Z UBASVA Z GXURN
JD Z TPFM Z HTMAGKMJEO Z IX Z JXVPKRA Z JPJ Z UMPOBADV
Some words appear but IC becomes 0.047 which is rather low ...
------------------------------
From: "Tom St Denis" <[EMAIL PROTECTED]>
Subject: Draft of TC15a paper
Date: Sun, 20 May 2001 13:06:34 GMT
I decided to start the paper. I am not done the analysis yet (have to break
it somehow...arrg) this paper describes TC15 with the change I made to avoid
Scotts attack.
Please have a read and comment. It's not done yet so all comments are
welcomed (as to the English and math of the paper).
http://tomstdenis.home.dhs.org/tc15.pdf
http://tomstdenis.home.dhs.org/tc15.ps.gz
--
Tom St Denis
---
http://tomstdenis.home.dhs.org
------------------------------
Subject: Re: CIA Kryptos last 97 characters
From: [EMAIL PROTECTED] (Gary Warzin)
Date: Sun, 20 May 2001 13:27:41 GMT
Ferdinando,
If you looked at my site yesterday, look again now. I put some new info up
there just after midnight. Look under update #1. It's starting to look much
more like a Quagmire III or IV, which is in keeping with your thinking that
Sanborn probably wouldn't do something nonstandard like use a "broken" table.
I do disagree with you when you say he gives no cribs. For part 1 and part 2
Sanborn gave us the table. That told us both the type of cipher and KRYPTOS as
one of the keywords. And, while it was Sanborn that designed the sculpture,
and he's been quoted as saying he thought it would never be solved, it was
really Ed Scheidt that designed the code. I believe that he's quoted somewhere
as saying that he wanted Kryptos to teach. So, I don't think it would be a
unusual for him to have built in a clue or two.
What I like about the hidden table idea is that is fits PALIMPSEST (a very
unusual word to have selected), it gives a reason for the other "errors" in the
messages, and it fits with some statements of both Scheidt and Sanborn that
part four is, in someway, different. I believe Scheidt said he made it harder
to solve than the other parts, and Sanborn indicated that there was something
visual to it. I can't remember the exact source of the interview, but he was
talking about coding systems that used light.
For the moment I'm working with the idea that the message is really 93
characters long:
OBUOX OGHUL BSOLI FBBWF LRVQQ PRNGK SSOTW TQSJQ SSEKZ ZWATJ KLUDI AWINF BNVTT
MZFPK WGDKZ XTJCD IGKUH UAUEK CAR
which leaves out the KR and YP. And, that the period might be 13, fitting in
with a key phrase that looks like Y---T--------.
Do let me know if you turn up anything interesting.
In article <AINN6.12367$[EMAIL PROTECTED]>,
[EMAIL PROTECTED] says...
>
>
>Gary Warzin ha scritto nel messaggio
><2uxN6.2372$[EMAIL PROTECTED]>...
>>I had a chance to see Kryptos up close a couple of weeks ago. Since then
>I've
>>been working on the remaining 97 characters. I've noticed something
>>"interesting" that may indicate that there is an underlying table "hidden"
>>under the message. Anyone else working on this?
>>
>>I've posted some notes at www.iquest.net/~gwarzin.
>>
>Hi Gary,
>i've been working on Kryptos since 1999.
>
>I've visited your site and, sorry, but i don't agree with you, for the
>following reasons:
>- the solution of the first part (PALIMPSEST) gave NO cribs to the second
>one;
> and the method used was a "linear" Vigenere table.
>- the solution of the second one (ABSCISSA) gave absolutely NO cribs to the
>solution of the third;
> and the method used was the same "linear" Vigenere table.
>- the solution of the third part was a "simple" transposition:
> let's say P(x) the letter of plaintext at position X=0..337
> C(y) the letter of the ciphertext ta position Y=0..337
> the transposition is: C(y) = P((y*191 + 192) mod 337)
>
>...so, WHY the first+second+third parts should give cribs to the solution of
>the fourth one ?
>...and, WHY should be the method of the fourth part so complex ? (a hidden
>text, a broken Vigenere table,
>such an obscure mechanism of encryption) ?
>
>may be i'm wrong, but, for the moment, you've not convinced me.
>
>best wishes
> Ferdinando
>
------------------------------
From: "Brian Hetrick" <[EMAIL PROTECTED]>
Subject: Re: Apology to Cloakware (open letter)
Date: Sun, 20 May 2001 13:56:00 GMT
"Matt Timmermans" wrote...
> Has anyone heard of a reasonably successful algorithmic method for
> identifying people by writing style?
Algorithmic? No, not that I know of. On the other hand, the point of
poetry criticism (in particular, although this is also true of
literature criticism as a whole, to an extent) is identifying and
recovering information sidebands in written text, particularly
sidebands about the identity and outlook of the speaker. For all
except very good poets, speaker = author.
Unfortunately, I don't follow the group closely enough to be familiar
with personalities. And even were I to do so, I would not expect to be
able to coherently argue a poster's identity in lay person's terms:
the field of forensic poetry criticism is woefully underdeveloped. I
can, however, say my bozo detector meter pegged while reading the
subject post. I suspect most everyone's did.
------------------------------
From: "Harris Georgiou" <[EMAIL PROTECTED]>
Subject: Re: What about SDD?
Date: Sun, 20 May 2001 16:56:49 +0300
� David Wagner <[EMAIL PROTECTED]> ������ ��� ������ ���������:
9e7bb3$2f3$[EMAIL PROTECTED]
> Harris Georgiou wrote:
> >Given the exponentially
> >growing capacity in storage and communications over time, I think gives a
> >whole new area of interest in secure storage and exchange of sensitive
data.
> >Using certification and authentication techniques, or huge PRNG-based
> >distributions, it is possible to ensure confidentiality by means of
> >information distribution (SDD) rather than hiding (stego) or sealing
> >(crypto).
>
> That sounds like a pretty persuasive argument. Yes, I believe
> that in the radiocommunications world, there are well-known techniques
> for using information dispersal to conceal information. A simple
> version goes like this: At time t, use the t-th output of a keystream
> generator to pick an unpredictable frequency f_t, and transmit the t-th
> chunk of data on f_t. Probably one would want to pre-encrypt the data
> for best assurance of confidentiality.
It's not necessary to have frequency-skipping model. Using small bursts of
pulse sequences the actual signal spectrum gets so wide that eventually
covers all the available bands. If we ensure that it's power is low enough,
then the signal should appear as low-power white noise, which is cut-off by
other radio systems.
> One benefit this technique provides is low probability of intercept.
> An attacker who cannot predict the keystream generator output is in a
> very difficult position: she cannot follow the frequency hops; storing
> data from all possible frequency slots at each possible time position
> for later analysis is very expensive (if there are enough frequency
> slots); and even if one could do this, there are exponentially many
> possible ways to piece together the data samples.
UWB communications require ultra-wide band receivers, that is specialized
and sensitive hardware. And that is only for message tracking - if the
message is encrypted or randomly padded with noise then the analysis is just
beginning.
> Another benefit this provides is resistance to jamming. Although I
> don't know much about radiofrequency engineering, it would appear on
> the surface that an attacker who cannot predict the keystream generator
> must transmit at high power on a large fraction of the possible
> frequency slots to have a reasonable chance of preventing the message
> from getting through, and this seems likely to be expensive if the
> number of frequency slots is much larger than typical message lengths.
The resistance of UWB to jamming comes mainly due to the ultra-wide
spectrum. If someone wants to jam say FM radio, powerful noise bursts in the
FM band should cripple all radio signals within these bands.
Multi-frequency, poly-phase or other variable signal modulation techniques
can always be tracked down and narrowed to specific band areas, so
band-jamming is still being used. However, when someone wants to jam a UWB
signal then the whole spectrum should be jammed. Even if this is
cost-afforted, jamming the whole spectrum will affect the allied comms too.
If the UWB spectrum is low-powered then the jamming covers it with a
slightly higher power noise (adaptive or static). But if the UWB spectrum is
high enough then the opponent's comms are flooded with the UWB spectrum and
the only way to deny comms is jamming all spectrum with power noise and thus
deny all radio comms for both ends!
> I believe this technique, and others like it, are described a little
> bit in Ross Anderson's excellent textbook, _Security Engineering_.
> Note that I am not an expert in this area, so I might have gotten some
> of the details above wrong, but I believe the sense of it is probably
> roughly correct.
Thanks for the tip - will look for it.
> It is not quite as clear how to apply this to, say, Internet
> communications, but maybe there is something that could be done.
> For instance, if there is sufficient diversity in the routes available
> on the net, one could try to send each packet on a different route,
> selected randomly using a keystream generator (note that in this
> case, the receiver need not know the key the sender uses); this
> would appear to raise the cost of certain classes of eavesdropping
> attacks. If you've already got cryptographic protection of your
> Internet communications, I'm not sure whether there's much value
> in such an approach (although maybe it helps to increase the cost
> of traffic analysis?), but if for some reason crypto is hard to deploy,
> this approach might serve as a partial measure to help manage the
> risk of eavesdropping for such communications.
I think the routing structures of TCP/IP networks are very hard to change or
manipulated in such way, at least not without causing major traffic
problems. My guess is that a secure comms layers can be constructed much
like the SSL, in order to achieve (according to R.Rivest) confidentiality
though message authentication between multiplexed, chaffed and noisy
channels. Furthermore, if the bandwidth permits, one can always use PRNG
sparse data distribution inside vast amounts of noise so that none can
pinpoint the location or even confirm the existance of them in the noise
flood. However, I think the most likely application of such techniques are
sensitive data storage. Encryption can keep away and intruder from keyrings
and files, but the intruder always knows the exact location of them. On the
other hand, if someone burries a 4096-bit key randomly inside a full CD of
junk data then the intruder will definately have a much harder time
retrieving the whole pack and then try to pinpoint the exact location of the
512 bytes inside 650M, before even trying to decrypt the key.
Sounds interesting doesn't it?
--
Harris
- 'Malo e lelei ki he pongipongi!'
------------------------------
** 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
******************************
