Prev: A link on North Korean home-grwon OS
Next: If we could factor large numbers quickly, how exactly does everything break?
From: WTShaw on 11 Apr 2010 00:00
Permutations can get a bad reputation as keys with algorithms that
rely on little else than simple substitution. They may be simply
recovered even without a crib or because of a stylized sequence that
has some words in the permutation.

Nevertheless, on a random draw basis, they do have relative strengths.
Consider that for a permutation of two elements, there is a single bit
of strength. For three elements, it is one trit plus one bit for a
total equivalent to 2.58 bits.

Using this logic, many years ago I wrote a most simple program to
figure bit and trit equivalent strengths for various sizes of
permutations. Here is the bit part of the table given in pairs as the
number of elements and the equivalent number of bits:

2=1; 3=2.58; 4=4.58; 5=6.9; 6=9.49; 7=12.3; 8=15.3; 9=18.47; 10=21.79;
11=25.25; 12=28.84; 13=32.54; 14=36.34; 15=40.25; 16=44.25; 17=48.34;
18=52.51; 19=56.76; 20=61.08; 21=65.47; 22=69.93; 23=74.43; 24=70.04;
25=83.68; 26=88.38; 27=03.14; 28=97.94; 29=102.8; 30=107.71;
31=112.66; 32=117.66; 33=122.71; 34=127.8; 35=132.92; 36=138.09;
37=143.3; 38=145.55; 39=153.84; 40=159.16; 41=164.52; 42=169.91;
43=175.34; 44=180.79; 45=189.29; 46=191.81; 47=197.36; 48=202.95;
49=208.56; 50=214.21; 51=219.88; 52=225.58; 53=231.31; 54=237.06;
55=242.84; 56=248.65; 57=254.49; 58=260.34; 59=266.23; 60=272.13;
61=278.06; 62=284.02; 63=290; 64=296; 65=302.02; 66=308.06; 67=314.13;
68=320.22; 69=326.32; 70=332.45; 71=338.6; 72=344.77; 73=350.96;
74=357.17; 75=363.4; 76=369.65; 77=375.92; 78=382.2; 79=388.5;
80=394.83; 81=401.17; 82=407.52; 83=413.9; 84=420.29; 85=426.7;
86=433.13; 87=439.57; 88=446.03; 89=452.51; 90=459; 91=465.51;
92=472.03; 93=478.57; 94=485.12; 95=491.69; 96=498.28; 97=504.88;
98=511.49; 99=518.12; 100=524.76; 101=531.42; 102=538.1; 103=544.78;
104=551.48; 105=558.2; 106=564.92; 107=571.67; 108=578.42; 109=585.19;
110=591.97; 111=598.77; 112=605.57; 113=612.39; 114=619.23;
115=626.07; 116=632.93; 117=639.8; 118=646.48; 119=653.58; 120=660.48;
121=667.4; 122=674.33; 123=681.28; 124=688.23; 125=695.2; 126=702.17;
127=709.16; 128=716.16; 129=723.17; 168=1004.56.

It all depends on how permutations are used as to whether strength is
maximized. Properly done, permutations do not exhibit the
vulnerabilities as keys as you were probably taught. It all depends
on their use and whether and/or how well partial solutions are
exploitable.

As an absolute identity value as an internal key, permutations can
present a significant challenge for brute forcing. There are
innumerable shortcuts to keying that create permutations but the
methods can be secretly diverse and personalized so as to be
convenient for the known user while obscure to anyone else. Related
shortcuts could just as well produce bit streams or pseudorandom
character streams as well but going through a permutation stage helps
to give a flat distribution.

From: David Eather on 11 Apr 2010 02:14
You wrote a whole program and even years later thought it something that
everyone should know about.

You wrote a whole program to calculate this:

equivalent number of bits = log(N!) / log(2)

where N is the number of objects to be permuted.

Sorry, anyone who did any formal maths already knows that, as does
anyone who studied cryptography for any length of time and they don't
need a table of repeated calculations. They can already directly
calculate it for any value they desire. Even better, by replacing log(2)
with log(X) they can calculate it to any value to base X as well.

You don't even know what you don't know. You would be best served by
listening and asking genuine questions.


On 11/04/2010 2:00 PM, WTShaw wrote:
> Permutations can get a bad reputation as keys with algorithms that
> rely on little else than simple substitution. They may be simply
> recovered even without a crib or because of a stylized sequence that
> has some words in the permutation.
>
> Nevertheless, on a random draw basis, they do have relative strengths.
> Consider that for a permutation of two elements, there is a single bit
> of strength. For three elements, it is one trit plus one bit for a
> total equivalent to 2.58 bits.
>
> Using this logic, many years ago I wrote a most simple program to
> figure bit and trit equivalent strengths for various sizes of
> permutations. Here is the bit part of the table given in pairs as the
> number of elements and the equivalent number of bits:
>
> 2=1; 3=2.58; 4=4.58; 5=6.9; 6=9.49; 7=12.3; 8=15.3; 9=18.47; 10=21.79;
> 11=25.25; 12=28.84; 13=32.54; 14=36.34; 15=40.25; 16=44.25; 17=48.34;
> 18=52.51; 19=56.76; 20=61.08; 21=65.47; 22=69.93; 23=74.43; 24=70.04;
> 25=83.68; 26=88.38; 27=03.14; 28=97.94; 29=102.8; 30=107.71;
> 31=112.66; 32=117.66; 33=122.71; 34=127.8; 35=132.92; 36=138.09;
> 37=143.3; 38=145.55; 39=153.84; 40=159.16; 41=164.52; 42=169.91;
> 43=175.34; 44=180.79; 45=189.29; 46=191.81; 47=197.36; 48=202.95;
> 49=208.56; 50=214.21; 51=219.88; 52=225.58; 53=231.31; 54=237.06;
> 55=242.84; 56=248.65; 57=254.49; 58=260.34; 59=266.23; 60=272.13;
> 61=278.06; 62=284.02; 63=290; 64=296; 65=302.02; 66=308.06; 67=314.13;
> 68=320.22; 69=326.32; 70=332.45; 71=338.6; 72=344.77; 73=350.96;
> 74=357.17; 75=363.4; 76=369.65; 77=375.92; 78=382.2; 79=388.5;
> 80=394.83; 81=401.17; 82=407.52; 83=413.9; 84=420.29; 85=426.7;
> 86=433.13; 87=439.57; 88=446.03; 89=452.51; 90=459; 91=465.51;
> 92=472.03; 93=478.57; 94=485.12; 95=491.69; 96=498.28; 97=504.88;
> 98=511.49; 99=518.12; 100=524.76; 101=531.42; 102=538.1; 103=544.78;
> 104=551.48; 105=558.2; 106=564.92; 107=571.67; 108=578.42; 109=585.19;
> 110=591.97; 111=598.77; 112=605.57; 113=612.39; 114=619.23;
> 115=626.07; 116=632.93; 117=639.8; 118=646.48; 119=653.58; 120=660.48;
> 121=667.4; 122=674.33; 123=681.28; 124=688.23; 125=695.2; 126=702.17;
> 127=709.16; 128=716.16; 129=723.17; 168=1004.56.
>
> It all depends on how permutations are used as to whether strength is
> maximized. Properly done, permutations do not exhibit the
> vulnerabilities as keys as you were probably taught. It all depends
> on their use and whether and/or how well partial solutions are
> exploitable.
>
> As an absolute identity value as an internal key, permutations can
> present a significant challenge for brute forcing. There are
> innumerable shortcuts to keying that create permutations but the
> methods can be secretly diverse and personalized so as to be
> convenient for the known user while obscure to anyone else. Related
> shortcuts could just as well produce bit streams or pseudorandom
> character streams as well but going through a permutation stage helps
> to give a flat distribution.
>

From: bmearns on 12 Apr 2010 12:38
On Apr 11, 2:14 am, David Eather <eat...(a)tpg.com.au> wrote:
> You wrote a whole program and even years later thought it something that
> everyone should know about.
>
> You wrote a whole program to calculate this:
>
> equivalent number of bits = log(N!) / log(2)
>
> where N is the number of objects to be permuted.
>
> Sorry, anyone who did any formal maths already knows that, as does
> anyone who studied cryptography for any length of time and they don't
> need a table of repeated calculations. They can already directly
> calculate it for any value they desire. Even better, by replacing log(2)
> with log(X) they can calculate it to any value to base X as well.
>
> You don't even know what you don't know. You would be best served by
> listening and asking genuine questions.
>
> On 11/04/2010 2:00 PM, WTShaw wrote:
>
> > Permutations can get a bad reputation as keys with algorithms that
> > rely on little else than simple substitution.  They may be simply
> > recovered even without a crib or because of a stylized sequence that
> > has some words in the permutation.
>
> > Nevertheless, on a random draw basis, they do have relative strengths.
> > Consider that for a permutation of two elements, there is a single bit
> > of strength. For three elements, it is one trit plus one bit for a
> > total equivalent to 2.58 bits.
>
> > Using this logic, many years ago I wrote a most simple program to
> > figure bit and trit equivalent strengths for various sizes of
> > permutations. Here is the bit part of the table given in pairs as the
> > number of elements and the equivalent number of bits:
>
> > 2=1; 3=2.58; 4=4.58; 5=6.9; 6=9.49; 7=12.3; 8=15.3; 9=18.47; 10=21.79;
> > 11=25.25; 12=28.84; 13=32.54; 14=36.34; 15=40.25; 16=44.25; 17=48.34;
> > 18=52.51; 19=56.76; 20=61.08; 21=65.47; 22=69.93; 23=74.43; 24=70.04;
> > 25=83.68; 26=88.38; 27=03.14; 28=97.94; 29=102.8; 30=107.71;
> > 31=112.66; 32=117.66; 33=122.71; 34=127.8; 35=132.92; 36=138.09;
> > 37=143.3; 38=145.55; 39=153.84; 40=159.16; 41=164.52; 42=169.91;
> > 43=175.34; 44=180.79; 45=189.29; 46=191.81; 47=197.36; 48=202.95;
> > 49=208.56; 50=214.21; 51=219.88; 52=225.58; 53=231.31; 54=237.06;
> > 55=242.84; 56=248.65; 57=254.49; 58=260.34; 59=266.23; 60=272.13;
> > 61=278.06; 62=284.02; 63=290; 64=296; 65=302.02; 66=308.06; 67=314.13;
> > 68=320.22; 69=326.32; 70=332.45; 71=338.6; 72=344.77; 73=350.96;
> > 74=357.17; 75=363.4; 76=369.65; 77=375.92; 78=382.2; 79=388..5;
> > 80=394.83; 81=401.17; 82=407.52; 83=413.9; 84=420.29; 85=426.7;
> > 86=433.13; 87=439.57; 88=446.03; 89=452.51; 90=459; 91=465.51;
> > 92=472.03; 93=478.57; 94=485.12; 95=491.69; 96=498.28; 97=504.88;
> > 98=511.49; 99=518.12; 100=524.76; 101=531.42; 102=538.1; 103=544.78;
> > 104=551.48; 105=558.2; 106=564.92; 107=571.67; 108=578.42; 109=585.19;
> > 110=591.97; 111=598.77; 112=605.57; 113=612.39; 114=619.23;
> > 115=626.07; 116=632.93; 117=639.8; 118=646.48; 119=653.58; 120=660.48;
> > 121=667.4; 122=674.33; 123=681.28; 124=688.23; 125=695.2; 126=702.17;
> > 127=709.16; 128=716.16; 129=723.17; 168=1004.56.
>
> > It all depends on how permutations are used as to whether strength is
> > maximized.  Properly done, permutations do not exhibit the
> > vulnerabilities as keys as you were probably taught.  It all depends
> > on their use and whether and/or how well partial solutions are
> > exploitable.
>
> > As an absolute identity value as an internal key, permutations can
> > present a significant challenge for brute forcing. There are
> > innumerable shortcuts to keying that create permutations but the
> > methods can be secretly diverse and personalized so as to be
> > convenient for the known user while obscure to anyone else. Related
> > shortcuts could just as well produce bit streams or pseudorandom
> > character streams as well but going through a permutation stage helps
> > to give a flat distribution.

Permutations are just as good as anything else chosen randomly. What
would make you think otherwise? As you're program and David Eather's
simple equation illustrate, a permutation contains a certain amount of
information, so it is exactly that strong.

The only down side to permutations is that they are informationally
sparse. Consider, for instance, a permutation of the 26-character
English alphabet. That's about 88.38 bits of information, but each
character requires an average of 4.7 bits to represent it, giving a
total of 122.2 bits to represent the entire alphabet. The density is
slightly less than 73%, but if the permutation is created randomly, it
does still contain 88.38 bits of information so it's exactly as strong
as any other key with 88.38 bits of information. From a strictly
practical consideration, it's easier to just store/remember 84 bits
than 123 bits with an equivalent amount of information.

The real issue with permutations is how they are created. For
instance, in that little JavaScript application of yours that we
discussed in a thread last week, you created the permutation based
upon secret information which most likely contained significantly less
information than the permutation was capable of encoding. In this
case, regardless of how secure the encryption algorithm itself was,
your security is limited by the information in that secret and the
permutation is just a time burner, nothing more or less.

The factoradic number system is the normal way to generate random
permutations from seed data. Factoradic is a mixed-radix number system
where each item in a permutation represents a different digit in the
number. It defines a one-to-one mapping between all possible
permutations and all non-negative integers so any digital input (seed)
data can be represented by a permutation.

-Brian

From: WTShaw on 14 Apr 2010 02:55
On Apr 11, 1:14 am, David Eather <eat...(a)tpg.com.au> wrote:
> You wrote a whole program and even years later thought it something that
> everyone should know about.
>
> You wrote a whole program to calculate this:
>
> equivalent number of bits = log(N!) / log(2)
>
> where N is the number of objects to be permuted.
>
> Sorry, anyone who did any formal maths already knows that, as does
> anyone who studied cryptography for any length of time and they don't
> need a table of repeated calculations. They can already directly
> calculate it for any value they desire. Even better, by replacing log(2)
> with log(X) they can calculate it to any value to base X as well.
>
> You don't even know what you don't know. You would be best served by
> listening and asking genuine questions.

While your figures are correct in general, the route I took was to
actually simulate the real process. Your figures will not always match
the real experimental values.
From: WTShaw on 14 Apr 2010 03:16
On Apr 12, 11:38 am, bmearns <mearn...(a)gmail.com> wrote:

>
> Permutations are just as good as anything else chosen randomly. What
> would make you think otherwise? As you're program and David Eather's
> simple equation illustrate, a permutation contains a certain amount of
> information, so it is exactly that strong.

I agree but in a recent response, that simple fact was rejected.
>
> The only down side to permutations is that they are informationally
> sparse. Consider, for instance, a permutation of the 26-character
> English alphabet. That's about 88.38 bits of information, but each
> character requires an average of 4.7 bits to represent it, giving a
> total of 122.2 bits to represent the entire alphabet. The density is
> slightly less than 73%, but if the permutation is created randomly, it
> does still contain 88.38 bits of information so it's exactly as strong
> as any other key with 88.38 bits of information. From a strictly
> practical consideration, it's easier to just store/remember 84 bits
> than 123 bits with an equivalent amount of information.

Memory is not the obstacle these days but utility is. In forcing
everything convenient to bits, you reject natural content that
otherwise you could not easily use.
>
> The real issue with permutations is how they are created. For
> instance, in that little JavaScript application of yours that we
> discussed in a thread last week, you created the permutation based
> upon secret information which most likely contained significantly less
> information than the permutation was capable of encoding. In this
> case, regardless of how secure the encryption algorithm itself was,
> your security is limited by the information in that secret and the
> permutation is just a time burner, nothing more or less.

As there are almost infinite ways to do this, you reject any method
that you cannot control. My answer is that it is right to encourage
private generation of complex keys because that is often where real
strength lies and always does in ideal systems, or should. Making keys
has nothing to do with the actual encryption algorithm except meeting
operational runtime critera.
>
> The factoradic number system is the normal way to generate random
> permutations from seed data. Factoradic is a mixed-radix number system
> where each item in a permutation represents a different digit in the
> number. It defines a one-to-one mapping between all possible
> permutations and all non-negative integers so any digital input (seed)
> data can be represented by a permutation.
>
> -Brian

For runtime purposes, while conversion to and from such other system
of enumeration can be done, it is not descriptive and adds a level of
complication that is unnecessary. Incorporating the true set is
seamless to a permutation as is. I realize that you are not familiar
with the mathematics of most bases anyway.

There is utility in what you say for permutations above a certain
length but that is not the problem in descriptions of limited
processes.
 |  Next  |  Last
Pages: 1 2 3 4 5
Prev: A link on North Korean home-grwon OS
Next: If we could factor large numbers quickly, how exactly does everything break?