IS A DEPTH?
===========
Introduction
============
Recovering plain text from messages in depth is very time consumming. Before
to undertacking this task we must be sure that the messages are in depth.
Indeed, many messages with similar indicator groups, are not genuine messages
in depth at all, but are messages with the same text which were enciphered
twice in succession, since in the first encipherment a mistake was made in
the setting of the message. For this reason the read addressee could not
decipher the message, sent a query back, and then the message was sent again
with the correct encipherment. Often, it is not possible to decide in advance
whether these messages are in depth or not.
In TICOM DF-120 document, German cryptanalysts describe several methods which
can help to decide whether two messages are in depth or not.
Note: Most of the following text is an excerpt of the TICOM DF-120 document.
1. Trigraph Differences
=======================
a) Statistics
-------------
From solved M-209 messages from Africa, out of 10,000 letters the 300
most frequent clear text trigraphs were counted (taking into account the
separator letter "Z") and the clear text found correspond to the negative
cipher intervals in messages in depth. The triple number (Zahlentripel)
which arose was weighted with values built up simply from the product of the
frequencies of their occurences, since the probability that two definite
clear text trigraphs will appear over each other is equal to the product
of the frequency of the percentage of their occurence.
From these differences a table was prepared which indicates for us the
corresponding weight for every possible zahlentripel.
b) The Method
-------------
One now finds each interval triple which appears in the two cipher messages,
in the upper as well as in the lower message, and adds up the weights which
apply to them.
The sum is then multipled by 100 and divided by twice the number of positions
being investigated. ...
The final result then gives us a point of departure for telling whether the
messages being investigated are in depth or not. Experience has show that
values of 50,000 or more make depth probable. Values under 40,000 speak
against depth, and with numbers in between 40,000 and 50,000 one can count
on either possibility.
c) Example
Note: There is no a complete example in the TICOM document.
I tried to reconstitute one.
I created a text of 10,000 characters from a Gutemberg's projet text.
I calculated trigraphs frequency of the most 300 frequent ones.
Then, I calculated the zahlentripel table;
Here an excerpt of this table:
==========================
! zahlentripel ! weight !
==========================
! 13-16-14 ! 480 !
! .... ! ... !
! 14-14-16 ! 234 !
! 14-14-17 ! 660 !
! 14-14-18 ! 1430 !
! 14-14-19 ! 742 !
! .... ! ... !
! 16-14-14 ! 672 !
! .... ! ... !
For example, calculation of the 14-14-18 entry:
- Frequency of the "NGZ" trigram: 55
- Frequency of the "ZSH" trigram: 26
- Difference between NGZ and ZSH: 14-14-18
- Weight of this difference: 55*26 = 1430
Note: we store only the most high values.
Here are three messages (we have removed the indicators). Are they in depth?
Msg1:
RWRAS XQDUE DVDSO ANZQC HAKPQ IZFIG DDNNA SMTVY
SHWYC RGXSU UVPFE KHMEZ PNKMU HBZAY VJYST GFBSN OGFHV DJBFV
PBWCR EXEBP UTBJB HTQEN BFEQW GUXKB OVPTH WMMDQ TBMZK WRRHY
LORIA SQLRT SSIBZ ASZJT EPKBN ZRWLL MRBBG MGUHM IARWY NCCQB
BSXND GVSLY JIFGR CSWLQ UEYYG PWFYD BMSIF LOVPR GRCXX EUFDN
JLLDN HKGMD PKRUJ CKGFZ OKCIT XWKXS YHTKV LAQZU MIDVR DHJGM
Msg2:
EGDMC PIBPC MSQKN JMISB KVPJE YKFUG XXKFL MRHHQ
SKXFO GZSNM UHHOQ VSMNV JEQOY TNWWQ RGLFF XKVSW GSKQX EWBXR
OSAMA VBSMH GBOES RTZXX XJLYX CHILK OQGIN YYSWU BTBGE ZAHSQ
GFLEB WVDMN GXXMZ MBIRA DVPIV FOBAJ MLKTA PLYKH YPSBQ LCZCF
PLXYF YBSHW ZSTTI LGPYG FGHJM ZKGGD BJNGO JTTAR WRFSK NOGDR
AYCYL UIIQS ULLTN WKPBO XTFMR PGEDX GXDNW GZNNU CUMBG SDWRM
Msg3:
JYIHY HAWBW OXWMM GGGOD LYQNM VIHLX REETK YNWOK
NXJZY HFMVY KXZNE UHCBZ HASWE AAVNI QRQMH YZDXK RODAB QJKPM
DPXJM BGKVZ UWEUG FHYMU GMLGV DZKAZ QMIJG BPAMJ ITRDR PIEKI
QPNSO BFYRW NNEBR PGCPG KFQIU TDNYI PIPMY MWCJI GKODX MZYUK
LGXFI WMLQH CGGBE HSUUU PQHER DAFOV CJZKV JJELY MLJLA ZLFRY
JFZXB JKKAI FPFJJ GPKCQ RIZQJ SIFVJ AWNOX XEWVQ FOMEA FGZUD
Begining of the calculation from the two first messages:
RWRAS....DHJGM
RWR DHJ
WRA HJG
RAS JGM
EGDMC....SDWRM
EGD => Difference (RWR - EGD) = 13-16-14, weight = 480
GDM => Difference (WRA - GDM) = 16-14-14, weight = 672
DMC => Difference (RAS - DMC) = 14-14-16, weight = 234
SDW => Difference (DHJ - SDW) = 11-04-13, weight = 756
DWR => Difference (HJG - DWR) = 04-13-15, weight = 935
WRM => Difference (JGM - WRM) = 13-15-00, weight = 4611
Sum = (480 + 672 + 234 + .... + 756 + 935 + 4611)
Z = (Sum * 100) / (2 * length) = (392503 * 100) / (2*290) = 67,673
Final results (with 290 letters in superposition):
- Messages 1 and 2: 67,673 (they are effectively in depth)
- Messages 1 and 3: 43,332
- Messages 2 and 3: 44,822
But if I only take the first 70 letters:
- Messages 1 and 2: 75,419 (they are effectively in depth)
- Messages 1 and 3: 32,748
- Messages 2 and 3: 37,257
Finally, if I only take the first 50 letters:
- Messages 1 and 2: 77,296 (they are effectively in depth)
- Messages 1 and 3: 41,679
- Messages 2 and 3: 30,440
Remark: The German Cryptanalysts doesn't transform value by logarithm
function. Normally, when we multiply probalities we add logarithms.
2. Other Criteria
=================
a) Number of Doublets
---------------------
The doublet frequency of two English clear texts when a word separator letter
is used is about 8%. In the cipher text of messages in depth, however, doublets
occur only when there also are doublets at these positions in the basic clear
texts. A doublet frequency of between 6 and 8 percent in our cipher text,
therefore, signifies depth.
This doublet criterion is not valid for messages which are offset by one in
their clear text...
b) Different Length and Different Enipherment Times
---------------------------------------------------
With the same length and the same encipherment time there is always the
suspicion that we are dealing with the same text in both messages and that
it was only sent on time wrong and on time correctly. Here we obtain, by
means of our trigraph differences, a starting point for depth.
3. Other methods not used by German cryptanalysts
=================================================
a) IC
---------------------------
IC (Index of Coincidence) is a technique invented by W.F. Friedman of putting
two texts side-by-side and counting the number of times that identical letters
appear in the same position in both texts. If the texts are in depth, the IC
is characteristic of the language. If the texts aren't in depth, the IC is
near by 0.0385
IC:
- Message 1 & 2: 0.076
- Message 1 & 3: 0.051
- Message 2 & 3: 0.028
Remark: The IC measure was used by Germans but to find depths for code problems,
not for M-209 problems. They used Hollerith tabulation machines to do that.
b) Bamburismus
--------------
Bambursimus uses a mathematical measure to decide if two messages are in depth.
This measure is more accurate than IC. It was invented by Alan Turing.
The Bayes Factor for M monograms in an overlap of N is therefore:
BF = ((P ** M) * ((1-P)**(N-M))) / (((1./26.)**M)*((25./26.)**(N-M)))
In deci BAN :
BFdB = int ( 20 * log (BF ))
P is the probability of single character matching (it is equivalent to IC [Index of Coincidence]).
In German, P = 0.0762
In English, P = 0.0667
In French, P = 0.0778
In Spanish, P = 0.0770
(1 – P ) is the inverse probability (probability of no matching)
M is the number of coincidences
N is the length of superimposition
The presence of bigrams and trigrams are considered as bonus.
Final BFdb results (with 290 letters in superposition):
- Messages 1 and 2: 82 with 1 bigram (they are effectively in depth)
- Messages 1 and 3: 0
- Messages 2 and 3: -84