Use of simple schemes
Mok-Kong Shen
Thanks to Moore's law and other economic/technical factors, computing
speed always tends to increase and the cost of hardware as a rule
tends to decrease and consequently nowadays even a normal user is able
to do computations that decades ago were not easy jobs for the
supercomputing centres.
I suppose that in crypto computations, like in the general case of
numerical mathematical computations, there is always a trade-off
between computing cost and complexity of computing procedure employed.
I mean that, since now computing cost is often a minor issue, one
could, as an alternative to applying sophisticated algorithms that
require deep analysis in their design and much care in implementation,
employ certain simple primitive procedures, using a much higher number
of steps of operations to compensate for their inherent weakness with
respect to the complex procedures underlying the sophisticated
algorithms.
I remember that years ago Terry Ritter had the following suggestion:
Append to a given block of plaintext bits a number of bits such that
there are in total the same number of 0's and 1's and then perform
a random permutation of the bits to become the ciphertext block.
(Perhaps for sufficiently large block lengths one could for ease of
handling relax the requirement of exact equality of number of 0's and
1's to an approximate equality or even simply extend a given plaintext
block of length L with, say, three blocks of length L that contain
pseudo-random bits.) Recently Marsaglia has published a fast PRNG
with very good statistical qualities. I suppose that it could possibly
render Ritter's scheme to become viable in practical applications.
Are there other schemes that in similar manner could profit from the
permanent trend of ever cheaper and higher performance of computer
hardware?
Thanks,
M. K. Shen
Le Chaud Lapin
> Are there other schemes that in similar manner could profit from the
> permanent trend of ever cheaper and higher performance of computer
> hardware?
Well, I do not know of any clever algorithms that could become more
attractive due to massively-cheap computing power, but if someone were
to speed up modular reduction by a couple orders of magnitude, doing
whatever is necessary in conventional CPU's, ... sigh. :(
-Le Chaud Lapin-
Mok-Kong Shen
Another scheme that is also (theoretically) very simple but faï¿œrly
expensive in computing is, I suppose, Hill's scheme employing matrices.
Now the Hill cipher is said to be weak in textbooks because, if the
matrix is n*n and one has n^2 units of corresponding plain and cipher
text, then the matrix can be found and the whole thing broken. But one
could afford to use a good sufficiently fast PRNG to dynamically
generate as many matrices as needed, using even any one n*n matrix for
much less than n^2 units of plaintext, when the computing cost is low
and the speed is acceptable. This way, Hill's scheme would be
practically applicable (eventually as a component of a larger scheme)
in my humble view.
M. K. Shen
Maaartin
> Another scheme that is also (theoretically) very simple but faírly
> expensive in computing is, I suppose, Hill's scheme employing matrices.
> Now the Hill cipher is said to be weak in textbooks because, if the
> matrix is n*n and one has n^2 units of corresponding plain and cipher
> text, then the matrix can be found and the whole thing broken. But one
> could afford to use a good sufficiently fast PRNG to dynamically
> generate as many matrices as needed, using even any one n*n matrix for
> much less than n^2 units of plaintext, when the computing cost is low
> and the speed is acceptable. This way, Hill's scheme would be
> practically applicable (eventually as a component of a larger scheme)
> in my humble view.
But having a fast perfectly secure PRNG you could simply xor it's
output with the plaintext. Using an unsecure PRNG makes the Hill's
scheme vulnarable again. And again, you need an expensive analysis of
the cipher what is just what you wanted to avoid.
biject
A realitively easy scheme would be to use the XOR
program I wrote years ago where the two files do not
have to be the same length. One of the files could
be the first part of a long key.
When you XOR the two files then do some sort
of bijective binary BWT on the result file.
then do another XOR with a second different
key file.
Some day I will but a binary bijective BWT type of
program on web since it is the fist stage of a simple
bijective binary BWT type of compression program.
David A. Scott
--
My Crypto code
http://bijective.dogma.net/crypto/scott19u.zip
http://www.jim.com/jamesd/Kong/scott19u.zip old version
My Compression code http://bijective.dogma.net/
**TO EMAIL ME 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.
As a famous person once said "any cryptograhic
system is only as strong as its weakest link"
Mok-Kong Shen
> But having a fast perfectly secure PRNG you could simply xor it's
> output with the plaintext. Using an unsecure PRNG makes the Hill's
> scheme vulnarable again. And again, you need an expensive analysis of
> the cipher what is just what you wanted to avoid.
I don't yet understand your last sentence. If an n*n matrix is
used to process less than n^2 units (characters or computer words)
of text, there simply isn't possible to recover that matrix, if
the analyst has the plaintext and ciphertext available. Thus,
inferring the parameters of the PRNG would not be feasible in
my view.
M. K. Shen
Mok-Kong Shen
> A realitively easy scheme would be to use the XOR
> program I wrote years ago where the two files do not
> have to be the same length. One of the files could
> be the first part of a long key.
>
> When you XOR the two files then do some sort
> of bijective binary BWT on the result file.
> then do another XOR with a second different
> key file.
>
> Some day I will but a binary bijective BWT type of
> program on web since it is the fist stage of a simple
> bijective binary BWT type of compression program.
I am not intending to be negative, but you have been persuing
your 'bijective' project for a very very long time, if I don't
err, and I wonder that today you still write 'some day' above.
Since your program centers on compression, it would be fine
to first have it be carefully discussed by the compression
people in my view.
M. K. Shen
Mok-Kong Shen
> ...... as an alternative to applying sophisticated algorithms that
> require deep analysis in their design and much care in implementation,
> employ certain simple primitive procedures, using a much higher number
> of steps of operations to compensate for their inherent weakness with
> respect to the complex procedures underlying the sophisticated
> algorithms.
This includes also employing larger (than hitherto) block lengths
for the simple procedures and concatenations of them. (Concatenation
of a number of linear ones is obviously futile, since they are
equivalent to a single one. But I suppose one could profitably sandwich
a linear one of large block width between two layers of nonlinear ones
that consist of units of small block widths, if the linear one well
contributes to avalanche.)
M. K. Shen
Maaartin
Maybe you can't recover the matrix, but surely you can learn a lot of
about it. Using this information you can break the scheme if the PRNG
is insecure. Take as an example a totaly stupid PRNG generating the
sequence
seed, seed+1, seed+2, ...
and try yourself.
Mok-Kong Shen
Why should we make such an assumption? (One doesn't walk on the street
with a helmet just because some bolt possibly might fall down from
a helicopter flying over one's head, right?) We have nowadays, in
constrast to the time of classical crypto, good PRNGs like the recent
one by Marsaglia.
M. K. Shen
Maaartin
> > Maybe you can't recover the matrix, but surely you can learn a lot of
> > about it. Using this information you can break the scheme if the PRNG
> > is insecure. Take as an example a totaly stupid PRNG generating the
> > sequence
> > seed, seed+1, seed+2, ...
> > and try yourself.
>
> Why should we make such an assumption? (One doesn't walk on the street
> with a helmet just because some bolt possibly might fall down from
> a helicopter flying over one's head, right?) We have nowadays, in
> constrast to the time of classical crypto, good PRNGs like the recent
> one by Marsaglia.
So again:
- Either the PRNG is perfect and you need nothing more than xor it
with the plaintext.
- Or it is not and you have no "alternative to applying sophisticated
algorithms that require deep analysis in their design and much care in
implementation" since you need it all.
I proposed you to try with the extremelly stupid PRNG since using it
the analysis is simple. You can take KISS or SuperKISS if you want,
but than you must work harder. At the end you need either break it or
give a good reason why breaking it is hard. Or at least show it to be
more secure than simple xoring with the PRNG output.
And first you need to specify all the details: How large should the
matrix be, over what ring, how you ensure it to be regular, etc. You
also need to state on what plattforms it works (do smart cards have
enough power for it?), how to implement it efficiently, how to prevent
timing attacks, etc.
Mok-Kong Shen
Regarding "deep" analysis see my thread "Rendering prediction of
congruential random number generators hard". Yes, researchers have
done good analysis, but these could easily be defended. (compare also
my second post in the thread "Dynamic change of encryption keys".
However, please post direct comments to that post to that thread.)
M. K. Shen
Unruh
It is a logical procedure to demonstrate that your "proof" is wrong. Since it
should, according to the stated assumptions, also apply to that silly PRNG, and
since it clearly is wrong for the PRNG, your proof is wrong.
Ie, proof by counterexample. If you make some statement about the integers which
someone points out is wrong for the integer 5, your proof, or your assumptions are
wrong. You may be able to repair the proof, but doing so by saying that it is
valid for all integers except 5 is not convincing to anyone.
>M. K. Shen
Mok-Kong Shen
You ignored the other part of my post. Please make your argmentation
more effective by posting 'direct' critiques to the stuff I posted in
the other two threads mentioned: "Rendering prediction of congruential
random number generators hard" and "Dynamic change of encryption keys".
Thanks in advance,
M. K. Shen
Mok-Kong Shen
>
>> ...... as an alternative to applying sophisticated algorithms that
>> require deep analysis in their design and much care in implementation,
>> employ certain simple primitive procedures, using a much higher number
>> of steps of operations to compensate for their inherent weakness with
>> respect to the complex procedures underlying the sophisticated
>> algorithms.
A viable example of this in block encryption could be using sub-optimal
S-boxes but additional rounds to compensate for the less than
theoretically possible optimality, if for practical reasons (time,
resources) one couldn't arrive at an "ideal" design of the the S-boxes.
This is not suggesting that one could allow carelessness, blind
simplifications, laziness, etc. in design but simply indicating the
"reality" which as everywhere else in life forces one to be a realist
to choose and accept an economically best optimum in practice and not
be an idelist and behave pedantically to find the ideal but practically
not achievable theoretical optimum.
In fact, with the progress of computers many approximative/iterative
procedures have come up to practically "replace" the exact solutions
of a large number of computational problems. For example, while a
century ago one painfully searched for exact solutions of differential
equations (in terms of the known functions), nowadays differential
equations are commonly solved on computers with iterative methods
which were not practically doable without today's computing power.
Genetic algorithms, neural networks, simulation methods etc. etc.
wouldn't have come into being at all, if one hadn't relatively cheap
computing power at one's disposal.
M. K. Shen
Mok-Kong Shen
> I suppose that in crypto computations, like in the general case of
> numerical mathematical computations, there is always a trade-off
> between computing cost and complexity of computing procedure employed.
> I mean that, since now computing cost is often a minor issue, one
> could, as an alternative to applying sophisticated algorithms that
> require deep analysis in their design and much care in implementation,
> employ certain simple primitive procedures, using a much higher number
> of steps of operations to compensate for their inherent weakness with
> respect to the complex procedures underlying the sophisticated
> algorithms.
I like to mention two further schemes which could be viable candidates
for the above considerations.
The first goes back in my knowledge to a thesis done decades ago by
someone at MIT (I forgot his name, but his work was discussed in the
group), namely employing Hufman encoding but randomly assigning 0/1
to the branches emanating from each node of the tree. Since we here
assume that we could be quite generous in employing computing
resources (CPU, storage, transmission), we could generate a squence
of random Hufman trees (without consideration of the compression
efficiency, with random assignments of 0/1) and use each tree to
only encrypt a few (a chosen small fixed number, or else determined
pseudo-randomly) plaintext units.
The second is a humble scheme suggested by me years ago: Choose
a positive value p leas then 1. Output with probability p an (with an
pseudo-random bit xor) encrypted plaintext bit and with probability
1-p output a (dummy) pseudo-random bit. Under our current assumption
of sufficiently cheap computing resources, we could choose p to be
a very small value in order to correspond to a high level of desired
security.
Thanks,
M. K. Shen
Mok-Kong Shen
[snip]
> ....... Choose
> a positive value p leas then 1. Output with probability p an (with an
> pseudo-random bit xor) encrypted plaintext bit and with probability
I am afraid that wasn't very clear. Please read the 2nd sentence as
"With the help of a PRNG output pseudo-randomly with probability p ...."
M. K. Shen
Greg Rose
Mok-Kong Shen <mok-ko...@t-online.de> wrote:
>M. K. Shen
Mok-Kong is talking to himself again. This is a
good sign, soon he will get bored with the
conversation.
Greg.
--
Greg Rose
232B EC8F 44C6 C853 D68F E107 E6BF CD2F 1081 A37C
Mok-Kong Shen
> In article <hem96k$chq$00$1...@news.t-online.com>,
> Mok-Kong Shen <mok-ko...@t-online.de> wrote:
>> M. K. Shen
>
> Mok-Kong is talking to himself again. This is a
> good sign, soon he will get bored with the
> conversation.
Nice to know that you "did" respond to my post.
Spinner
Not true. Nobody is responding. You are making all of this up, and so
are we. Personally, I'm planning to wake up soon and the movie will be
over and i'll pick up my popcorn and coke and go home.
--
2+2!=5 even for extremely large values of 2
Mok-Kong Shen
> Mok-Kong Shen wrote:
>> Greg Rose wrote:
>>> Mok-Kong is talking to himself again. This is a
>>> good sign, soon he will get bored with the
>>> conversation.
>>
>> Nice to know that you "did" respond to my post.
>
> Not true. Nobody is responding. You are making all of this up, and so
> are we. Personally, I'm planning to wake up soon and the movie will be
> over and i'll pick up my popcorn and coke and go home.
If a post follows-up another, then "somebody" must have pushed
the answer button of his newsreader. For me this point is barely of
importance. What I like, however, to stress is that one should strive
to maintain a good atmosphere in discussions. In a newsgroup, there
are experts as well as laypeople, highly literate natives as well
as foreigners not having fully mastered the English language. Using
a phrase from a certain proverb collection, I plead that everyone
should use soft words and hard arguments in scientific discussions,
i.e. avoiding in particular personal attacks, which could lead to
nothing but unnecessary waste of bandwidth. See my thread "Hoping
for a good discussion atmosphere in this group" of 23.09.2009.
M. K. Shen
WTShaw
Good manners in good discussions are desirable but the most scientific
of posts are often treated with prejudice from the uninspired.
Cryptography is beyond single authorities as much as surgery is beyond
1850 techniques, some of which may even still be good. I am ready to
return to good discussions but also ready to beg for good evidence to
back up shallow claims of capability without demonstrating it. In a
scientific mode of consideration, bad ideas need to be fought but only
with good evidence against them and not just waves of hands with
selected fingers made prominent. All here should be open to knowing
more and not merely finding a set in the a-men section.
Mok-Kong Shen
> Good manners in good discussions are desirable but the most scientific
> of posts are often treated with prejudice from the uninspired.
> Cryptography is beyond single authorities as much as surgery is beyond
> 1850 techniques, some of which may even still be good. I am ready to
> return to good discussions but also ready to beg for good evidence to
> back up shallow claims of capability without demonstrating it. In a
> scientific mode of consideration, bad ideas need to be fought but only
> with good evidence against them and not just waves of hands with
> selected fingers made prominent. All here should be open to knowing
> more and not merely finding a set in the a-men section.
I am not sure of having fully understood you. But perhaps I could
say that the main point of mine in this thread is that in my view
some of the methodogies in classical crypto presumably could still
be profitably used (in forms adapted to modern computers), if these
are employed with (intended) more computing effort/costs, e.g.
multiple encryptions with different methods, to compensate for their
otherwise (in the original form) weakness in the computer age. BTW,
that the classical crypto even in the original form may not be very
easy to break may be seen in the case of the Chaocipher (see a
recent thread of moscherubin). Discussions on the individual
classical ciphers should perhaps be better done in their own threads,
I suppose.
Thanks,
M. K. Shen
WTShaw
One important fact is that given different ciphers, the amount of
ciphertext needed to solve a message varies. If only a few characters
are used, perhaps nothing conclusive can be solved. A good question
regards the level of possible, ambiguity with one threshold for
getting anything meaningful and another for being conclusive. This
refers to one concise algorithm systems.
Since the levels vary with algorithms, there would be a consideration
in finding multiple algorithms that did not lessen the strength of any
component level.
Mok-Kong Shen
> One important fact is that given different ciphers, the amount of
> ciphertext needed to solve a message varies. If only a few characters
> are used, perhaps nothing conclusive can be solved. A good question
> regards the level of possible, ambiguity with one threshold for
> getting anything meaningful and another for being conclusive. This
> refers to one concise algorithm systems.
>
> Since the levels vary with algorithms, there would be a consideration
> in finding multiple algorithms that did not lessen the strength of any
> component level.
If I don't err, a cascade of two encryption systems of different
nature wouldn't weaken any of them, e.g. cascading transposition and
substitution in classical crypto.
M. K. Shen
WTShaw
Right, a complementary arrangement of two primitives does exactly
that. This means that finding primitive elements that can add
strength to each other is the way to go.
If strength for an algorithm ideally is to be in the keys alone, then
this means using combinations of primitives that utilize stronger keys
is a good idea. That's pretty straight forward.
Mok-Kong Shen
> Mok-Kong Shen wrote:
>> WTShaw wrote:
>>> One important fact is that given different ciphers, the amount of
>>> ciphertext needed to solve a message varies. If only a few characters
>>> are used, perhaps nothing conclusive can be solved. A good question
>>> regards the level of possible, ambiguity with one threshold for
>>> getting anything meaningful and another for being conclusive. This
>>> refers to one concise algorithm systems.
>>> Since the levels vary with algorithms, there would be a consideration
>>> in finding multiple algorithms that did not lessen the strength of any
>>> component level.
>> If I don't err, a cascade of two encryption systems of different
>> nature wouldn't weaken any of them, e.g. cascading transposition and
>> substitution in classical crypto.
>
> Right, a complementary arrangement of two primitives does exactly
> that. This means that finding primitive elements that can add
> strength to each other is the way to go.
>
> If strength for an algorithm ideally is to be in the keys alone, then
> this means using combinations of primitives that utilize stronger keys
> is a good idea. That's pretty straight forward.
I suppose you brought up in the 2nd paragraph above a theme that seems
to be fairly neglected. Let me therefore ask some questions. Doesn't
the design of any cipher generally presupposes that the user employs
a strong key? If the answer is no, wouldn't a user then need to know
how tolerant is a given cipher to weakness of keys? Further, in order
to know in that case of his safety of use of the cipher, how could he
'measure' the strength/weakness of his key in quantitative terms in
practice to determine the fulfillment of the requirement?
Thanks,
M. K. Shen
WTShaw
Most ciphers, the so-called historical ones, waste keys that might be
used in a stronger up. That is the overall design does not live up to
high expectations. Then the best thing to be done is to fly under the
radar by keeping passages short enough not to be conclusively solved
anyway. So, you need frequent key changes, protocols that are awkward-
confusing, and the need to drop the whole scheme for efficiency's
sake.
Many classic ciphers already have rough quantitative appraisals from
an experienced point of view...there are tables. The necessity is for
the operator-clerk to have experience and a feeling for what works
efficiently and well. Now beyond this old established cipher
strategy, there are neoclassical options that can and do work rather
well, and myrids of newer algorithms that can test the mettle of
solvers. But, too difficult does not promote activity of solvers who
may expect to best any ciphertext, even including a few who specialize
in rather sparse clues...Hi Jim. Since these missing ciphers are not
promoted for one or few reasons, those who otherwise work in the field
see a vacuum at that level and think that nothing means everything,
that what might be there must be worthless...untrue.
Emperical testing requires effort by even other than the designer. I
for one would encourage new ciphers and that they be somehow
evaluated. Someone might even learn something. There are useful
examples.
Starting with the OTP and digressing from it is actually a good idea.
There are many ways that it can be changed. The principles of honest
scientific evaluation are not to be dismissed where cipher ideas can
otherwise be rated. New ciphers are to give new dimensions to one or
more ideas, not to solve everything at once. Then, you would have
newer primitives to add back to the mix rather than merely rude cat
calls from the gallery. It's a tell that so many cipher ideas are
dismissed because of basic incompetence and unfairness by would be
evaluators who otherwise what to be classed as learned cryptographers.
Even making critical mistakes is essential if learning is to take
place. Don't bet everything on a just born horse or say nay to just
any unevaluated neigh.
WTShaw
As the OTP represents both a black hole of failed method and a
pinnacle of promise; it is overall insufficient for rational use. An
improvement would be strengthening the key stream. Hashing it can
render it most difficult to recover and provide additional
opportunities for different protocols. One good method is as I have
used for other key purposes, using a counted hash technique.
For discussion, consider a 26 character alphabet used in the key
stream. Convert each 26 characters into a 26 character permutation and
chain the permutations together. A plain text stream would be much
easier to solve with patterns derive from common letters and words in
the data and key string. With a hashed key, the ciphertext would tend
to be most random. Simple but effective. There are lots of possible
design variations without returning to the failed OTP..
No, good cipher designs are not that hard, but not knowing what needs
to be done or how to get there gets you nowhere. Consider that the
hashing technique referenced above used combined primitives of
substitution and transposition in a sort of a parallel method. The
result is really a primitive in itself. But of course for as long as
it has been in the tool kit even once classified, few have seen its
real promise in modern designs.
WTShaw
As a continuance, consider that a hashed key that produces a list of
permutations and is easily made and remembered in its parts does meet
historic criteria for algorithms, at least as applied to keys. How
such a key is applied is another question.
While some treat the unknown cipher type problem as beneath their
dignity, it remains a valid type puzzle and has been for decades. With
clues to the method, solving the following hashed lines for their well
known source might demonstrate the relative strength of one variation
of counted hash use. The exact procedure is not quite up to par
according to my standards, just cruising slightly above the trees.
Don't falsely rely much on anything you know as this is a new bird for
many. It's designed not to be a quick solve even if you know haw, or
do you? Surprise me and I will explain all and then up the strength
from this:
dgqavbxzmjwfykiolehtpncusr
qcvuhndkposbayjlmgtfwzixre
mbcklfxngjpihtdseozyaqwruv
zovptnjgwhiakcqudmrsbeyflx
sybrncfptaozhekmdxjiglvuqw
klgvdfyntiuoaqprjhmcwszebx
klzypgqhtefadxmvjrnwicubos
ogvtzwdibmplkjefcayrqsunxh
WTShaw
>
> dgqavbxzmjwfykiolehtpncusr
> qcvuhndkposbayjlmgtfwzixre
> mbcklfxngjpihtdseozyaqwruv
> zovptnjgwhiakcqudmrsbeyflx
> sybrncfptaozhekmdxjiglvuqw
> klgvdfyntiuoaqprjhmcwszebx
> klzypgqhtefadxmvjrnwicubos
> ogvtzwdibmplkjefcayrqsunxh
Concerning recoverability of the sources texts for these permutations,
their nature as linked hashes would suggest likely ambiguity in
suggested recoveries which by comparisons of lines might suggest a
widespread known passage if used. Because of the combined hashing
nature of the linked lines, a case might be made that for any given
line as a hash that the source could not be absolutely defined and
that all line hashes are equal as in possibility from a draw. There
are more ways to further obscure the source but our present occupation
is to go beyond that focus.
Even though the source of the permutations is obscured by hashes, use
of the array as a simple linear key for different encryptions might
lead to frequency analysis of coincidences between the passages, their
solutions, and ultimately to the above representation. An improvement
would be not to use these permutations as simple linear keys at all
but as rotatable wheels in more complicated systems where the nature
of the working key is better hidden. Appropriate advanced algorithms
utilizing premutations can be capable of all degrees of increased
security over simplistic linear approaches.