My BLT
in [Cryptography]
|
From: David Eather on 24 Feb 2010 20:00 On 25/02/2010 6:09 AM, bmearns wrote: > Thanks for the interesting analysis, Richard and David. I'm wondering > if our host has any to provide? > > I'm very much an amateur at cryptanalysis, but I was able to do a > partially successful known-plain-text attack against the cipher by > hand over the course of a few hours, ending up with the pools fully > reconstructed, and 15 of the 27 table entries filled in. The reason I > wasn't able to reconstruct the entire table, despite having the full > pools, is because the order matters. There may be a clever way to > complete it from the tables without additional data, but I wasn't able > to come up with anything. > > The attack was against the known plaintext "i have a card for you > later", encoded as "coi hdm fvp igc ute pzs ynl ouj cdm epa wdy ezo > hwg cuz def acr vto pgm lep yjk zin hmu ond qlj rpg cdv jlk" (note > that the encoding was done off the top of my head, so it's likely not > as good as a true random encoding). I came up with the following pools > (each in no particular order): > 1: h y c j p a e v s > 2: d n u g m l t z / > 3: i o w q k r f b x > > and the following partial table: > 1 2 3 > 1 c?o e/r ?di > 2 y?f v?? ?u? > 3 ht? al? ??? > > My technique was just deductive reasoning. I started of course with > identical plaintext letters. For instance, 'a' is encoded 4 different > times, as 'igc', 'ouj', 'wdy', and 'qlj'. Therefore i, o, w, and q are > all in the same pool, as are {g u d l} and {c j y j}. Two of the > spaces are encoded as 'ynl' and 'cdm', so d and n are in the same > pool, and I can add n to the existing pool: {g u d l n}. > > Another type of reasoning I used was when two different plaintext > characters had two corresponding triplet-values the same (as in, from > the same pool), I new the characters in the remaining triplet-position > had to be in different pools. For instance, if two different letters > were encoded as 'abz' and 'abq', then I knew q and z must be in > different pools from each other, or the triplet would encode the same > plaintext character. I don't think there are any of these in the > original encoded version, but once I was able to deduce that certain > characters were in the same pool, this type of situation started > popping up. > > Finally, once I started getting fairly large partial pools, I could > reason that those two pools were distinct from one another. For > instance, if a partial pool contained {g u d l n m} and another had {h > y c j}, those must be different pools, because combined it would have > 10 characters (which is too many, all pools have 9). > > The mutually-exclusive type of deductions in the last two paragraphs > weren't nearly as helpful as the deductions from the first paragraph, > but they were eventually useful. After a while, I ended up with 3 > pools which were all too large to be combined with one another, and > then I was able to determine that a particular character was not in > either of the first two pools, so there was only one place left for it > to go. > > Anyway, I know that known-plain-text is generally the easiest type of > attack, but it took a relatively small amount of plaintext to > reconstruct the entire pool, and more than half the table. If a > sufficient crib was available, this sort of partial reconstruction > could be performed. Any characters that were able to be filled in to > the table could then be deciphered from the remainder of the unknown > message. For undeciphered letters (those which didn't make it into the > table from the crib), having the pools (even partial) would allow a > large number of possibilities to be removed so that the remainder > could be evaluated to see what makes sense, and of course each letter > that is deciphered will improve further analysis. > > A final note about the analysis: the exact order of the table doesn't > necessarily have to match the original. The table I came up with > through the analysis is actually different from the one that was used > to encode the message originally, but as long as it is self consistent > and consistent with the crib/ciphertext, it should work. > > All in all, it was kind of a fun game, somewhat similar to soduko. > Maybe they should start publishing these in the Sunday paper. > > -Brian A nice proof that reasoning beats brute force.
From: WTShaw on 25 Feb 2010 10:18 On Feb 23, 1:14 pm, bmearns <mearn...(a)gmail.com> wrote: > > I'm very curious, though, to see if Shaw can offer any cryptanalysis > on this cipher. It's interesting, but I'm not convinced of it's > security. > > -Brian I think that looking at a weakness of it might be useful as in the following: Dual or Duel Solution of BLT Cipher Texts As previously stated, "Identical plaintext should never be encrypted twice with BLT as two or more known compatable but differently coded ciphertexts might compromise all of the BLT advantage." But if two or more ciphertexts using a single message and the same key were available, there are two advantages for it short of testing BLT for absolute strength using a single ciphertext: 1) Solution could be a game, testing the chances of useful cross ciphertexts pairings to gain access to the plaintext. This could be done as a solitary challenge. 2) Two or more parties receiving compatible ciphertexts gnerated using the same unknown key and both(all) from a single plaintext could compare what they had received and work toward a true solution whereas without cooperation a given solution might be too much of a challenge. A man-in-the-middle, if he has a clue to what is happening, might also have saved the data, so separate delivery of the ciphertexts is required for security. I've fully considered how to solve dual ciphertexts and consider the following: 1) Six different keys could be used to accurately solve a message but for completeness sake, only one would probably appear to be the result of a pangram attempt. The six possibilites are from permutations of the digits 123: 123, 132, 213, 231, 312, 321. 2) Compare the ciphertexts to isolate the pools by pairing the individual ciphertext letters of the two versions and linking as many letter together as possible. Remember two pools contain nine letters each and one pool has eight letters and the slant sign. 3) Look for triads in the ciphertexts with all three letters from the same pool. If used, these should represent 111, 222, 333, and those key letters would be those in the pool. In the 27 character key, the three true letters would be at positions 1, 14, and 27. Remember that BLT may or may not allow the use of a true plaintext letter as a member of a triad that represents it. I've done it both ways, including and excluding usage of specific plaintext letters in the triads that represent them. 4) Look for triads build from letters in all three pools. These will represent key characters having six possible locations in the 27 character key, address=position, 123=6th, 132=8th, 213=12th, 231=16th, 312=20th, and 321=22th. "con sid er/ hwt pkm abl yfg jqu vxz" 5) Look for triads built from these other combinations of pools and try to determine which actual key letters they represent. For some, doing this type of thing is not theirs. Some people are better at solving than others even to amazing facility. Some construct aides and computer programsfor help. BLT would be new to all even as I've talked about it for ages. The following might help: 6) If plaintext is words separated by spaces, slant sign is probably the most frequent user of triads and would have the slant sign as a member of the pools involved. A space would not be represented in position one and probably not in the last nine positions, 19-27. 7) Rare or unused key letters would tend toward latter positions. 8) Obvious exact or nearly correct spellings in the key would tend to be in low key positions. 9) Patience and a clear head are helpful in solving. I hope that the above is correct but please post errors, or suggestions that you might have if you do this type of work.
From: WTShaw on 25 Feb 2010 10:24 On Feb 23, 3:52 pm, Richard Outerbridge <ou...(a)interlog.com> wrote: > In article > > I suspect the patterns would rapidly reveal themselves to frequency > analysis, and the original square deduced therefrom, even if all 729 > different encodings for each letter are "randomly" employed. I have > no estimate for the unicity distance (how much ciphertext is needed > for key recovery). > > outer Unicity is a big question for any such cipher. For short messages, it might be really difficult to parce BLT, but an honest unicity value might be relative. Since ciphertext is roughly three times plaintext, that should be a factor for comparison with other ciphers. This creature, BLT, has intrigued me for maybe 15 years, fun perhaps is its only real virtue???
From: WTShaw on 25 Feb 2010 10:28 On Feb 23, 6:57 pm, David Eather <eat...(a)tpg.com.au> wrote: > On 24/02/2010 7:52 AM, Richard Outerbridge wrote: > > > > > In article > > <f7a29c3d-3fa8-4b27-8030-b343d57ce...(a)n5g2000vbq.googlegroups.com>, > > bmearns<mearn...(a)gmail.com> wrote: > > >> I'm very curious, though, to see if Shaw can offer any cryptanalysis > >> on this cipher. It's interesting, but I'm not convinced of it's > >> security. > > > Let's take a look at etaion, for English. > > > e : 131 [csehpayjv] [nd/tmlguz] [csehpayjv] 12.702% > > t : 213 [oirwkbfqx] [csehpayjv] [nd/tmlguz] 9.056% > > a : 231 [oirwkbfqx] [nd/tmlguz] [csehpayjv] 8.167% > > i : 122 [csehpayjv] [oirwkbfqx] [oirwkbfqx] 6.996% > > o : 112 [csehpayjv] [csehpayjv] [oirwkbfqx] 7.507% > > n : 113 [csehpayjv] [csehpayjv] [nd/tmlguz] 6.749% > > > Total: 51.177% > > > Assuming you know the method (and the method is assumed known) even > > though there are 729 different ways of encoding each of these trigrams > > (thus making it a homophonic) they will not be absolutely unrelated, as > > is the case with a true homophonic, or nomenclature. > > > I suspect the patterns would rapidly reveal themselves to frequency > > analysis, and the original square deduced therefrom, even if all 729 > > different encodings for each letter are "randomly" employed. I have > > no estimate for the unicity distance (how much ciphertext is needed > > for key recovery). > > > outer > > I used the following table to calculate the unicity distance for an > alphabet of 27 letters. I included the SPACE character as it would be > the most useful for comprehension of an encrypted message. > The text was from "The Leading Facts of English History" by D. H. > Montgomery (c)1887. So, some small frequency variation is to be expected > when used on other texts. The calculated entropy rate per character is > 4.097 bits. > > SPACE 1759 17.59% SPACE 1759 17.59% > A 633 6.33% E 1059 10.59% > B 123 1.23% T 771 7.71% > C 247 2.47% A 633 6.33% > D 342 3.42% O 627 6.27% > E 1059 10.59% N 597 5.97% > F 214 2.15% I 558 5.58% > G 165 1.65% R 534 5.34% > H 498 4.98% S 526 5.26% > I 558 5.58% H 498 4.98% > J 13 0.13% D 342 3.42% > K 45 0.45% L 334 3.34% > L 334 3.34% C 247 2.47% > M 200 2.00% F 214 2.15% > N 597 5.97% M 200 2.00% > O 627 6.27% U 195 1.95% > P 155 1.55% G 165 1.65% > Q 9 0.09% W 162 1.62% > R 534 5.34% P 155 1.55% > S 526 5.26% Y 133 1.33% > T 771 7.71% B 123 1.23% > U 195 1.95% V 77 0.77% > V 77 0.77% K 45 0.45% > W 162 1.62% X 19 0.19% > X 19 0.19% J 13 0.13% > Y 133 1.33% Q 9 0.09% > Z 5 0.05% Z 5 0.05% > Total 10000 100.00% Total 10000 100.00% > > since each character can be encoded in 729 different ways the > probability of each character is divided by 729. Entropy of each > character is calculated > > H = P*LOG(p)/LOG(2) * -1 > > and then summed remembering that there are 729 encodings for each > character (an even distribution is assumed)so based on single character > probabilities the rate of the encoding is 13.607 bit per encoding (that > is per 3 digit group) > > This gives a redundancy of > > D = 13.607 - 4.097 (each 3 char grouping is only carrying to information > of the 27 character alphabet) > = 9.51 bits per encoding > > and the unicity distance becomes > > U = 13.607/9.51 > = 3.32 characters > > which is very, very bad. What it means is that because of the hogh > amount of redundancy in the cipher, any decryption that makes sense and > is over 4 characters long has a high probability to be correct. Your efforts were extensive, impressed that you tried, but you are saying that roughly 10 characters of plaintext with an unknown 27 character key could be decrypted. Really?
From: WTShaw on 25 Feb 2010 10:33
On Feb 24, 6:51 am, David Eather <eat...(a)tpg.com.au> wrote: > On 24/02/2010 10:57 AM, David Eather wrote: > > I think a simple improvement would be to use a separate password to > generate the 3 pools. That would be the normal situation. The unknown example is using a separate key. Making the key and the message the same was not an intended use of the cipher. |