Cryptography-Digest Digest #857, Volume #11 Thu, 25 May 00 06:13:01 EDT
Contents:
Re: pentium timings and RC5 code (Greg)
Re: pentium timings (Greg)
Re: pentium timings (Greg)
Re: More on Pi and randomness (Jonathan Thornburg)
A Family of Algorithms, Base78Ct (wtshaw)
Please ignore (Paul Rubin)
Re: HTML encryption (Niklas Frykholm)
Re: Observation of Matsui's Sboxes (Mark Wooding)
Re: Crypto patentability (Runu Knips)
Re: Modulu arithmetic additive stripping? (Mok-Kong Shen)
Re: Base Encryption: Revolutionary Cypher (Mok-Kong Shen)
Re: bamburismus (Mok-Kong Shen)
Re: More on Pi and randomness (Mok-Kong Shen)
Re: Yet another block cipher: Storin (Mark Wooding)
Re: Modulu arithmetic additive stripping? (Runu Knips)
Re: Patent busting for AES usage (Runu Knips)
Re: pentium timings ("Brian Gladman")
Re: pentium timings ("Brian Gladman")
Re: safer style sboxes (Mark Wooding)
----------------------------------------------------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: pentium timings and RC5 code
Date: Thu, 25 May 2000 06:06:32 GMT
> Well since my code sucks, could someone with a K6-2 or PII time
> my code (http://www.tomstdenis.com/rc5asm.zip) and tell me the
> clocks per block they get?
I think what people have been trying to say is that you cannot
do this.
Go to the intel web site and download the cpu
docs to understand the features of the PII to see
how to maximize cache hits, how to keep the dual pipeline
filled to capacity as often as possible, etc., then don't
worry about how the OS interferes with the cache or pipeline.
You did the best you could in the design and today that is all
one can expect.
Publish what you designed and the numbers from Intel to back it up
and we will give you Kudos for that.
--
There is only one gun law on the books- the second amendment.
The only vote that you waste is the one you never wanted to make.
RICO- we were told it was a necessary surrender of our civil liberties.
Asset Forfeiture- the latest inevitable result of RICO.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Thu, 25 May 2000 06:11:23 GMT
> rdtsc
> push eax
> push edx
> times 512 call [temp]
> rdtsc
> pop ebx
> pop ecx
> sub eax,ebx ; cpu must finish rdtsc here
> sbb edx,ecx
Do you believe that this code can never be interrupted, thus the
rdtsc can never include timings of code not related to your own?
Also, you should look into replacing calls with jumps or other
designs to prevent flushing the pipeline and messing the cache.
If you are looking for bleeding edge code speed design, this is
not it.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: Greg <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Thu, 25 May 2000 06:20:43 GMT
> Removing the effect of interrupts is relatively easy
No you cannot (you have no idea as an application programmer
how many you still have in your minimum). Besides, trying to
eliminate them is simply pointless. You do not measure code
performance, you design it. You go to the intel docs and see
what the features of the chip includes and design your software
to keep the performance to a max. Even if you had your own OS
that NEVER interrupted your code, what good is measuring the
performance of your own code in that environment? It is not
realistic. The best you can do is publish your timings as calculated
by the intel docs, and account for interrupts flushing parts or all
of the onboard cache, the off board cache, and the pipeline.
The only thing you measure is the results to see how close you
came to the theoritical values and try to account for why you
did not meet them.
Sent via Deja.com http://www.deja.com/
Before you buy.
------------------------------
From: [EMAIL PROTECTED] (Jonathan Thornburg)
Subject: Re: More on Pi and randomness
Date: 25 May 2000 09:10:33 +0200
In article <[EMAIL PROTECTED]>,
Douglas A. Gwyn <[EMAIL PROTECTED]> wrote:
>The trouble with interval arithmetic as it is usually applied
>is that the intervals rapidly grow as operations are combined.
>A better (not perfect) approach is to perform arithmetic with
>distributions replacing values. (The simplest useful method
>would be to approximate every distribution as a Gaussian.)
>This still tends to degenerate into total noise after a while,
>but retains significance longer than does worst-case interval
>arithmetic.
Such "probabilistic" is *very* dangerous, because it almost invariably
neglects correlations between the errors in different variables. Many
practical algorithms generate such correlations in their intermediate
variables (and some even _rely_ on them).
Conclusion: You can't trust "probabalistic error analysis", i.e.
occasionally the true errors may be much *larger* than it suggests.
For details, see the following excellent papers by Kahan:
@unpublished
{
Kahan-1996-probabilistic-error-analysis-x,
author = "William Kahan",
title = "The Improbability of Probabilistic Error Analyses
for Numerical Computations",
year = 1996, month = "March 4",
X-note = "Available from
http://www.cs.berkeley.edu/~wkahan/improber.ps
or http://www.cs.berkeley.edu/~wkahan/improber.pdf",
note = "Available from
\hbox{\tt http://www.cs.berkeley.edu/$\sim$wkahan/improber.ps}
or
\hbox{\tt http://www.cs.berkeley.edu/$\sim$wkahan/improber.pdf}",
snote = "floating-point roundoff errors are often highly
discrete and correlated, so naive statistical
analyses based on based on modelling them as
uncorrelated continuous random variables
(a.k.a. ``Probabilistic Error Analysis'') can
be highly misleading",
}
@unpublished
{
Kahan-1999-correlation-vs-low-probability-events,
author = "William Kahan",
title = "The Fragility of Improbability",
year = 1999, month = "June 9",
X-note = "Available from
http://www.cs.berkeley.edu/~wkahan/Math55/correln.ps
or http://www.cs.berkeley.edu/~wkahan/Math55/correln.pdf",
note = "Available from
\hbox{\tt http://www.cs.berkeley.edu/$\sim$wkahan/Math55/correln.ps}
or
\hbox{\tt http://www.cs.berkeley.edu/$\sim$wkahan/Math55/correln.pdf}",
snote = "tiny correlations in random variables can make
a huge difference to the probability of rare events
way out on the tails of probability distributions",
}
--
-- Jonathan Thornburg <[EMAIL PROTECTED]>
http://www.thp.univie.ac.at/~jthorn/home.html
Universitaet Wien (Vienna, Austria) / Institut fuer Theoretische Physik
Q: Which countries [only 5 of them] have the death penalty for children?
A: Iran, Nigeria, Pakistan, Saudi Arabia, United States
------------------------------
From: [EMAIL PROTECTED] (wtshaw)
Subject: A Family of Algorithms, Base78Ct
Date: Thu, 25 May 2000 00:23:54 -0600
Here is a summary list of base translation algorithms which all have the
same form of base-78 Ciphertext, characters in the form of letters a-z:
within diamonds, <a>; circles, (a); and, squares, [a].
Hopefully there are few errors in the list, but some of the data may still
appear somewhat cryptic. My choice of key options are listed, but
plaintext sets are not. Because I am multiplexing plaintext characters in
some of these, in them is a potential for having many unusual characters.
My choices are just that, as the idea of base translation is a generic
one, and can be implemented in a number of ways.
The essence of the mathematical relationships, the inequalities in most
cases, is at the heart of the concept. By studying the mathematical
relationships involving an associated set of bases in a given algorithm,
you should come to learn pretty much all that you need. If you have
addition questions, ask.
To talk of algorithms without having them implemented is risky. All of
these are fully functional.
Base Translation Ct78 Algorithms by WTShaw, May 24, 2000
Amos T12/24b26 Subs26t,26ct Pt10/20 Ct9/18
49/26/78:(49^5)<(26^6) 91.4%; (26^4)<(78^3) 96.3%
Balkhash T24Penits Subs26ct,26ib Pt10 Ct9
47/5/26/78:(47^5)<(5^12) 93.9%; (5^4)<(26^2) 92.5%; (26^4)<(78^3) 96.2%
Banas T(3)6-18b26 Sub26pt,26ct PtCt4-24
77/26/78:(77^3)<(26^4)<(78^3) 99.9% 99.0%
Chakrata T50bits Sub26ct,31pt Pt10 Ct8
31/2/78:(31^2)<(2^10) 93.8%; (2^25)<(78^4) 90.6%
Dankhar T25bits Sub26ct Pt5 Ct4
32/2/78:(32^5)=(2^25) 100%; (2^25)<(78^4) 90.7%
Frederik T8-24Penits Subs26ct,26ib PtCt3-9
73/5/26/78:(73^3)<(5^8) 99.6%; (5^4)<(26^2) 92.4%; (26^4)<(78^3) 96.2%
Jamaica T6-24b18 Sub26ct PtCt4-16
76/18/78:(76^4)<(18^6)<78^4) 98.0% 91.9%
Lima T7/14/21 Subs26pt,26ct PtCt4-12
77/12/78:(77^4)<(12^7)<(78^4) 98.1% 97.7%
Luitpold T5-25b32(32=5bits) Sub32ib PtCt4-20
76/32/78:(76^4)<(32^4)<78^4) 99.3% 90.7%
MontegoBay T(3)6-24Pt Sub26ct Pt(3)6-24 Ct(2)4-16
18/78:(18^3)<(78^2) 95.9%
Nottoway T15b18 Sub26ct Pt12 Ct10
37/18/78:(37^4)<(18^5) 99.2%; (18^3)<(78^2) 95.9%
Providence T7/14/21ptct Subs26pt,26ct Pt4-12, Ct3-9
26/78:(26^4)<(78^3) 96.3%
Standards T20hepits Subs26ib,26ct Pt8 Pt9
129/7/26/78:(129^2)<(7^5)<(26^3) 99.0% 95.6%; (26^4)>(78^3) 96.3%
--
--
Secrets that are told or available are not secrets any more, surely
not trade secrets. Security of secrets is no dependant on someone
else's stupidy, only in your making them available in any form.
------------------------------
From: [EMAIL PROTECTED] (Paul Rubin)
Subject: Please ignore
Date: 25 May 2000 08:03:18 GMT
d80e9e8d3f419b5442c53cb2b554fbaf924889f9
------------------------------
From: [EMAIL PROTECTED] (Niklas Frykholm)
Subject: Re: HTML encryption
Date: 25 May 2000 08:19:09 GMT
In article <8gh09j$ia5$[EMAIL PROTECTED]>, DigiboyCiPHER wrote:
>Is there any easy way to encrypt HTML source but retain use amongst
>non-javascript browsers?
Encryption is impossible in this case. JavaScript doesn't help.
Since the page must be decrypted to be viewed in the browser,
an attacker can simply capture the decrypted data.
The best you can hope to achieve is obscurity. This will probably
stop some people, but noone who is serious about stealing your
source.
Example (which will probably not pass a validator but looks OK
in NS and IE):
<!--- <tiTlE 8scuobscure&#> scure&
</tITlE>--><tITLe 8scur
 1d p& <!-- >
An obscured page </TiTlE <!--
98scur> <!-- ITLe 8scur
 1&#bscured
ur&TITLE 8s	 --> <p <!--->Obs<!-- 98s p cur&TITLE 8scur

1ded  -->cure</p scur <!-- -->
// Niklas
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Observation of Matsui's Sboxes
Date: 25 May 2000 08:03:25 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> No I get what you are saying, I am just pointing out neither A or I
> follow SAC. My question is does S follow sac? I will test it later
> tonight.
Good-oh. <phew> I think we finally achieved a point where we
understood each other. It was touch and go for a bit... ;-)
-- [mdw]
------------------------------
Date: Thu, 25 May 2000 10:50:36 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Crypto patentability
Jerry Coffin wrote:
> In article <[EMAIL PROTECTED]>,
> [EMAIL PROTECTED] says...
> > Well I don't like patents, too. They are only a way for the
> > rich people to keep their richness. They are a way for the
> > big companies to stay big by destroying small companies
> > without much effort.
>
> _Precisely_ the opposite is actually true: patents are one of the few
> ways for a small company, or even one smart person, to level the
> playing field and be competitive against a big company.
So you have the 60.000 deutschmarks to buy an european patent ?
Even if I'll find something nifty tomorrow I'll hardly be able
to patent it. Its just too expensive for me. Its also too
expensive for small companies.
Too, the big companies have masses of patents, valid or not.
They know that many of them are problematic, and it is hard to
detect which of them are valid and which aren't. So they just
make pacts to share their patents with the other big companies
in that business. This way they can suppress the newcomers,
which don't have the money to fight against these masses of
patents, even if many of them are not real inventions.
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Modulu arithmetic additive stripping?
Date: Thu, 25 May 2000 11:04:22 +0200
"Douglas A. Gwyn" wrote:
> Mok-Kong Shen wrote:
> > (Unfortunately I don't have the literature you mentioned.)
>
> That's like a computer programmer not having Knuth's TAOCP.
Thank you very much for a nice and detailed example. I have long
time realized that the availability of scientific literatures (in general,
not specific to crypto) can be quite different in different countries. I
conjecture that the one you mentioned can be found on the shelves
of all big book stores in the US but this is certainly not the case
overseas. Foreign libraries also naturally tend to be less complete in
their collection of US books in comparison to US libraries. On the
other hand, once in discussion in our group I learned with some
surprise that Menezes' HAC (or maybe it was Journal of Cryptology
-- my memory is no longer good about that) was not (yet) available in
the library of a big US university at a time the same was long before
available in a couple of public libraries here in Munich.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: Base Encryption: Revolutionary Cypher
Date: Thu, 25 May 2000 11:04:29 +0200
Tim Tyler wrote:
> ...but you can't see a failure to get avalanche in *any* base and have
> good overall diffusion properties. If your system exhibits good
> avalanche properties, it should not be possible to transform it into
> another base, and watch the avalanche disappear. If you can do this, the
> system has undesirable cheracteristics in that base.
>
> This is the case Eric was describing. He wasn't seeing avalanche, and
> erroneously concluding that therefore, the effect would happen in all
> bases. He was seeing a /lack/ of avalanche - and concluding that the
> system was broken.
Pardon, I haven't yet fully understood you. The first paragraph seems
to says that avalanche, if present in one base, should manifest in another.
I guess that it logically follows that if avalanche is not observable at all in
one base, then it shouldn't manifest in another. But this seems to
contradict the content of the second paragraph.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: bamburismus
Date: Thu, 25 May 2000 11:04:34 +0200
"Douglas A. Gwyn" wrote:
> The fraction that is crackable depends on the mix of systems as
> well as on the security of protocols, key management, etc. The
> last I heard, 3DES was one of the systems that *no*body was
> reading with any method substantially better than a brute-force
> key search, but (a) it's not the only system being used and (b)
> it's among the family of systems I suspect *can* be cracked
> along the lines of my now-defunct research project of a couple
> of years ago. Anyone who trusts that the core 3DES algorithm
> is forever immune to (e.g.) known-plaintext cryptanalysis is
> assuming more than is warranted.
I conjecture from the tenor of what you wrote that there is a
probability that you are free to publish part of your ideas (maybe
through doing something like circumventing patents). In that case
it would possibly be a very valuable contribution to the science,
since attacking 3DES is yet considered to be pretty hard, as far as
I am aware. Your last sentence seems also to be in conformity with
the golden rule of never be over-confident and underestimate the
capabilities of the opponent (he may even have manifold
capabilities, cryptanalysis being only one of them). On the other
hand, quite a number of people apparently yet believe that one
(holy) encryption algorithm fits ALL.
M. K. Shen
------------------------------
From: Mok-Kong Shen <[EMAIL PROTECTED]>
Subject: Re: More on Pi and randomness
Date: Thu, 25 May 2000 11:04:40 +0200
"Douglas A. Gwyn" wrote:
> Mok-Kong Shen wrote:
> > I am a complete outsider. But I conjecture that interval arithmetics
> > might be useful in the present issue.
>
> The trouble with interval arithmetic as it is usually applied
> is that the intervals rapidly grow as operations are combined.
> A better (not perfect) approach is to perform arithmetic with
> distributions replacing values. (The simplest useful method
> would be to approximate every distribution as a Gaussian.)
> This still tends to degenerate into total noise after a while,
> but retains significance longer than does worst-case interval
> arithmetic.
Question: Is this idea of your own or could you give pointers to
literature? As far as I know, interval arithmetics continues to be
a field of active research in applied mathematics today. Some
time back, I happened to have a chat with one of the research
scientists. I didn't have the impression that he knew of any new
directions of the kind you described.
M. K. Shen
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: Yet another block cipher: Storin
Date: 25 May 2000 09:19:58 GMT
[EMAIL PROTECTED] <[EMAIL PROTECTED]> wrote:
> Also, Storin does not have the secret sboxes. The weak key is easy to
> identify in Storin.
I'm not entirely convinced it's a `weak' key. One plaintext is
unconcealed, although that can happen anyway. You can detect that it's
(likely) to have been used with one chosen plaintext, but you can do
that anyway. It's a bit like saying that the key 04b915ba43feb5b6 is
weak in Blowfish, because if I encrypt 42fd443059577fa2 with it then I
get 353882b109ce8f1a.
In any case, I've amended my version of the paper to require a key of 28
words or less, mainly to fix the situation I described elsewhere of the
second round key not depending on the first. I'm not submitting a
`tweak', because I want to see how well the original actually lasts.
-- [mdw]
------------------------------
Date: Thu, 25 May 2000 11:16:00 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Modulu arithmetic additive stripping?
"Douglas A. Gwyn" wrote:
> Mok-Kong Shen wrote:
> > (Unfortunately I don't have the literature you mentioned.)
> That's like a computer programmer not having Knuth's TAOCP.
Hu ? I don't have one ? Old book, quite big and expensive,
with a strange and hard to read pseudo assembly language.
------------------------------
Date: Thu, 25 May 2000 11:20:13 +0200
From: Runu Knips <[EMAIL PROTECTED]>
Subject: Re: Patent busting for AES usage
Runu Knips wrote:
> Ouch. When did you have understand crypto ?
Ooops, sorry, replace 'did you' with 'does one'. I
was not talking about anyone special :-) I just
wanted to note that crypto is a field which is
really hard to understand.
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Thu, 25 May 2000 10:20:47 +0100
"Greg" <[EMAIL PROTECTED]> wrote in message
news:8gignj$l4j$[EMAIL PROTECTED]...
>
> > Removing the effect of interrupts is relatively easy
>
>
> No you cannot (you have no idea as an application programmer
> how many you still have in your minimum). Besides, trying to
> eliminate them is simply pointless. You do not measure code
> performance, you design it. You go to the intel docs and see
> what the features of the chip includes and design your software
> to keep the performance to a max. Even if you had your own OS
> that NEVER interrupted your code, what good is measuring the
> performance of your own code in that environment? It is not
> realistic. The best you can do is publish your timings as calculated
> by the intel docs, and account for interrupts flushing parts or all
> of the onboard cache, the off board cache, and the pipeline.
I made it clear that I was timing low cycle count encryption algorithms -
code that typically takes only 200-1000 cycles to execute - and in this
situation it is easy to eliminate the effects of interrupts because any that
do occur make a significant difference to the measured cycle counts.
It is not hard to estimate the average frequency of interrupts in a single
user 'standalone' PC and this allows an estimate of the probability of an
interrrupt in a code fragment of 200-1000 cycles. In my system the
probability of an interrupt in a 1000 cycle code fragment is very low (in
fact this is still true for a 10,000 cycle code fragment). If this
probability is low (and some other reasonable assumptions are made) I can
make the probability that my minimum timing measurement includes an
interrupt very low indeed by taking a sufficient number of independent
timing measurements. Although I can never be completely certain that this
minumum does not include an interrupt, I can be close enough to certainty
for all practical purposes.
For example, if it is assumed that the probability of one or more interrupts
in a 1000 cycle code fragment is 0.1 (much too high in practice) and a block
of code of this length is timed 100 times, the the probability that all of
these 100 timings will include an interrupt (and hence that the minimum is
not interrupt free) is 10^-100. For you this level of uncertainty may
equate to "you have no idea how many you still have in your minimum" but for
most people this is close enough to certainty that the answer is 0 for all
practical purposes.
Turning to your concern about this being pointless, it might be so in a
large program but for a short algorithm it is important to understand how
long it takes at a primitive level since this provides the information that
a higher level application programmer needs to estimate timings in the
context of a real application. There will be an enormous difference in the
timing issues involved in, say, a standalone PC doing a single encryption
once in a while and a large switch where the cipher context is being
switched 1000's times per second. Basic algorithm timings, without
interrupts, provide a sound basis for estimating the cost of encryption
operations in these higher level applications contexts.
Brian Gladman
------------------------------
From: "Brian Gladman" <[EMAIL PROTECTED]>
Subject: Re: pentium timings
Date: Thu, 25 May 2000 10:24:05 +0100
"Greg" <[EMAIL PROTECTED]> wrote in message
news:8gignj$l4j$[EMAIL PROTECTED]...
>
> > Removing the effect of interrupts is relatively easy
>
>
> No you cannot (you have no idea as an application programmer
> how many you still have in your minimum). Besides, trying to
> eliminate them is simply pointless. You do not measure code
> performance, you design it. You go to the intel docs and see
> what the features of the chip includes and design your software
> to keep the performance to a max. Even if you had your own OS
> that NEVER interrupted your code, what good is measuring the
> performance of your own code in that environment? It is not
> realistic. The best you can do is publish your timings as calculated
> by the intel docs, and account for interrupts flushing parts or all
> of the onboard cache, the off board cache, and the pipeline.
I made it clear that I was timing low cycle count encryption algorithms -
code that typically takes only 200-1000 cycles to execute - and in this
situation it is easy to eliminate the effects of interrupts because any that
do occur make a significant difference to the measured cycle counts.
It is not hard to estimate the average frequency of interrupts in a single
user 'standalone' PC and this allows an estimate of the probability of an
interrrupt in a code fragment of 200-1000 cycles. In my system the
probability of an interrupt in a 1000 cycle code fragment is very low (in
fact this is still true for a 10,000 cycle code fragment). If this
probability is low (and some other reasonable assumptions are made) I can
make the probability that my minimum timing measurement includes an
interrupt very low indeed by taking a sufficient number of independent
timing measurements. Although I can never be completely certain that this
minumum does not include an interrupt, I can be close enough to certainty
for all practical purposes.
For example, if it is assumed that the probability of one or more interrupts
in a 1000 cycle code fragment is 0.1 (much too high in practice) and a block
of code of this length is timed 100 times, the the probability that all of
these 100 timings will include an interrupt (and hence that the minimum is
not interrupt free) is 10^-100. For you this level of uncertainty may
equate to "you have no idea how many you still have in your minimum" but for
most people this is close enough to certainty that the answer is 0 for all
practical purposes.
Turning to your concern about this being pointless, it might be so in a
large program but for a short algorithm it is important to understand how
long it takes at a primitive level since this provides the information that
a higher level application programmer needs to estimate timings in the
context of a real application. There will be an enormous difference in the
timing issues involved in, say, a standalone PC doing a single encryption
once in a while and a large switch where the cipher context is being
switched 1000's times per second. Basic algorithm timings, without
interrupts, provide a sound basis for estimating the cost of encryption
operations in these higher level applications contexts.
Brian Gladman
------------------------------
From: [EMAIL PROTECTED] (Mark Wooding)
Subject: Re: safer style sboxes
Date: 25 May 2000 09:40:16 GMT
tomstd <[EMAIL PROTECTED]> wrote:
> That's is if I do S2(S1(delta_x)) = delta_y?
In this case, there's no independence. You have to combine the two
substitutions as one and analyze that.
-- [mdw]
------------------------------
** 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
******************************
