Prev: How cool is this?
Next: The Winds of Change.
From: Mok-Kong Shen on 3 May 2010 10:50

In the thread "On the general benefits of introducing dynamics into
encryption processing" I argued that dynamics can be extremely
beneficial for both block and stream encryptions. In another recent
thread I proposed a dynamic version of the classical Hill cipher, which
was however vigorously disapproved by one expert, whose arguments, on
the other hand, I am unfortunately yet unable to fully capture. (There
is a talk concerning a prize challenge on that scheme with one person
but his acceptance of my offer appears to be unsure currently.)

I like herewith to present another encryption scheme, which is based on
the same idea of mine that is involved in the proposed dynamic Hill
cipher but which is devoid of the matrix formalism underlying the Hill
cipher and consequently is much simpler to be argued upon in matters of
security (or non-security).

I'll present three variants of the new scheme in decreasing order of
computational complexity (and presumably concomitant level of
security). I personally favour variant 2, while variant 1 may be useful
for easier argumentation on the appropriateness or falasy of my basic
idea as such.

Unless explicitly stated otherwise, all PRNGs in the following are
assumed to be second order congruential mod 2^32 with full period (the
type that I personally favour). A message key (that is unique for the
message) builds a master-PRNG whose output is employed to generate the
other PRNGs mentioned below.

Variant 1:

Generate three PRNGs, with outputs denoted by g_0, g_1 and g_2.
(One set of these values is used for processing one plaintext word.)
Set LSB of g_1 to 1 and LSB of g2 to 0. (This renders f(x)=c solvable.)

Define f(x) = g_0 + g_1*x + g_2*x^2 mod 2^32

Encrypt plaintext word P_i to ciphertext word C_i with C_i = f(P_i).

Variant 2:

Generate two PRNGs, with outputs denoted by g_0 and g_1. (One set of
these values is used for processing one plaintext word.) Set LSB
of g_1 to 1.

Define f(x) = g_0 + g_1*x mod 2^32

Encrypt plaintext word P_i to ciphertext word C_i with C_i = f(P_i).

Variant 3:

Same as Variant 2, excepting that the PRNGs generating g_0 and g_1
are not second order but first order, i.e. linear.

Now Variant 3 has virtually everything linear (I am idiosycratic enough
to have the master-PRNG remaining non-linear, though). The word
'linearity' is presumably exchangeable with 'trivially weak' in the
dictionary of many people in the crypto field. But how is one
"actually" going to mount an attack on that? We have one equation
C_i = g_0 + g_1*P_i mod 2^32 but we have two unknowns g_0 and g_1.
As layman I have yet no clue at all how to proceed from that equation
to predicting the PRNGs.

Thanks.

M. K. Shen

From: Mok-Kong Shen on 3 May 2010 10:57
Mok-Kong Shen wrote:
>
> security). I personally favour variant 2, while variant 1 may be useful

Sorry, typo: Please read "while variant 3".

M. K. Shen
From: Bryan on 4 May 2010 02:51
Mok-Kong Shen wrote:
> In the thread "On the general benefits of introducing dynamics into
> encryption processing" I argued that dynamics can be extremely
> beneficial for both block and stream encryptions. In another recent
> thread I proposed a dynamic version of the classical Hill cipher, which
> was however vigorously disapproved by one expert, whose arguments, on
> the other hand, I am unfortunately yet unable to fully capture.

Well, that's not really such a good description of the history. That
"one expert" -- did he or she call himself or herself an expert -- or
was it you, Mr. Shen, who bestowed the "expert" title? If you, Mr.
Shen, believe this person who addressed your idea to be an expert,
what effort did you put into understanding what this 'expert' offered,
before resigning as "unable to fully capture" what he or she said?

> (There
> is a talk concerning a prize challenge on that scheme with one person
> but his acceptance of my offer appears to be unsure currently.)

"There is talk"? You did talk, that's true, and you did challenge
Maaartin to go beyond what anyone had claimed.

> I like herewith to present another encryption scheme,

The sci.crypt FAQ is now way out of date, but even the ancient version
dismisses such naive proclamations of "another encryption scheme". The
title you chose, "Foiling known-plaintext attacks" suggests you are a
few decades behind the state of the art. Modern ciphers are designed
to resist adaptive chosen plaintext attacks, and beyond.

Perhaps it would help if you cite your best known-plaintext attacks,
Mr. Shen. You've been sci.crypt's most prolific writer over the course
of decades, so now that you want to discuss known-plaintext attacks,
please point to your results on the subject.


--
--Bryan
From: Mok-Kong Shen on 4 May 2010 05:09
Bryan wrote:
> Mok-Kong Shen wrote:
>> In the thread "On the general benefits of introducing dynamics into
>> encryption processing" I argued that dynamics can be extremely
>> beneficial for both block and stream encryptions. In another recent
>> thread I proposed a dynamic version of the classical Hill cipher, which
>> was however vigorously disapproved by one expert, whose arguments, on
>> the other hand, I am unfortunately yet unable to fully capture.
>
> Well, that's not really such a good description of the history. That
> "one expert" -- did he or she call himself or herself an expert -- or
> was it you, Mr. Shen, who bestowed the "expert" title? If you, Mr.
> Shen, believe this person who addressed your idea to be an expert,
> what effort did you put into understanding what this 'expert' offered,
> before resigning as "unable to fully capture" what he or she said?

Concepts are as a rule "relative", e.g. poor and rich. I know/consider
my knowledge in crypto to be poor and I designate myself hence as
layman. From many posts of yours in the group in the past, I estimate
that your knowledge is much higher than mine, hence I deem and call
you be an expert.

On the other hand, it is trivial that nobody is perfect. An expert
may occasionally get wrong, while a layman may occasionally get
right in a case where an expert deceives himself. What I think is
very important is that scientific discussions should not be loaded with
unnecessary "sentiments". Every argument could be formulated succintly,
objectively, anyway without causing negative feelings to other persons.

>> (There
>> is a talk concerning a prize challenge on that scheme with one person
>> but his acceptance of my offer appears to be unsure currently.)
>
> "There is talk"? You did talk, that's true, and you did challenge
> Maaartin to go beyond what anyone had claimed.

By "talk" I meant in the present context simply some exchange of posts
with the purpose to negotiate a final contract of the contest. I stated
my challenge. Mr. Maaartin is free either to accept that or consider
the challenge unacceptable for him. What's wrong in that? (I assume
you are certainly acquainted with the ordinary commercial practice in
markets of all sorts.)

>> I like herewith to present another encryption scheme,
>
> The sci.crypt FAQ is now way out of date, but even the ancient version
> dismisses such naive proclamations of "another encryption scheme". The
> title you chose, "Foiling known-plaintext attacks" suggests you are a
> few decades behind the state of the art. Modern ciphers are designed
> to resist adaptive chosen plaintext attacks, and beyond.
>
> Perhaps it would help if you cite your best known-plaintext attacks,
> Mr. Shen. You've been sci.crypt's most prolific writer over the course
> of decades, so now that you want to discuss known-plaintext attacks,
> please point to your results on the subject.

I don't see any reason why I should unconditionally find or know or
provide instances of past (real) known-plaintext attacks in the present
context. But I believe I do know/understand what known-plaintext
attacks are. (I assume that you don't want me to quote definition of
it from textbooks.) However I explained in my original post quite
clearly that examination of my scheme reveals that known-plaintext
attacks appear to be impossible to mount in such cases (unless, of
course, experts could point out some concrete directions in which that
sort of attacks could indeed realistically feasibly be done).

I like to point out that there is often a general dilemma in crypto
discussions in the group. For, on the one hand, an algorithm is
certainly not secure, simply because someone "claims" it to be so. On
the other hand, an algorithm is also certainly not weak, simply because
someone "claims" it to be so. One needs at least some (easily
understandable and non-sentimental) plausible arguments to render the
matter plausible in the one or the other direction. A rigorous proof of
security is certainly very desirable but, I suppose, could rarely be
expected in practice within the framework of this group. (We are only
an informal discussion group, not a scientific conference on
cryptology or a seminar on crypto in a university.)

BTW, I have said that the basic idea underlying the present scheme and
my proposal of the dynamic version of the Hill cipher is the same.
So, perhaps you could, utilizing your previous work done in
scrutinizing my proposal there, say something concrete/objective on
where the weakness of the scheme lies and in which direction one could
profitably pursue to crack it. (It's anyway my "attempt" here to make it
clear that "linear" isn't synonymous to "trivially weak".)

M. K. Shen
From: Bryan on 5 May 2010 04:54
Mok-Kong Shen wrote:
> I know/consider
> my knowledge in crypto to be poor and I designate myself hence as
> layman. From many posts of yours in the group in the past, I estimate
> that your knowledge is much higher than mine, hence I deem and call
> you be an expert.

But Mr, Shen, after your decades on sci.crypt, where you are the
groups most prolific writer over that term, why is your knowledge
still so poor? Were you deliberately trying not to learn anything?
[...]

> I don't see any reason why I should unconditionally find or know or
> provide instances of past (real) known-plaintext attacks in the present
> context. But I believe I do know/understand what known-plaintext
> attacks are. (I assume that you don't want me to quote definition of
> it from textbooks.)

What I want to see are your results. The fact that you personally
cannot conceive of how to launch attacks on the schemes you dump here
is not so impressive when we consider that you never discover any
attack against anything, even when clues are spoon-fed to you.

> I like to point out that there is often a general dilemma in crypto
> discussions in the group.

The immediate dilemma is how to warn novices about posts that imitate
the style and tone of serious work, but are are worse than useless in
terms of content.


--
--Bryan
 |  Next  |  Last
Pages: 1 2 3 4 5 6 7
Prev: How cool is this?
Next: The Winds of Change.