<!DOCTYPE html>
<html lang="en">
<head>
	<meta charset="utf-8"/>
	<meta name="viewport" content="initial-scale=1.0,maximum-scale=1.0" />
	<title>IoC – Frequency Analysis</title>
	<link rel="stylesheet" type="text/css" href="../style.css">
<script type="text/javascript">
var idx = -1;
document.addEventListener("keydown", keyDownHandler, false);
function keyDownHandler(e) {
    if (e.key == "Right" || e.key == "ArrowRight") {
        idx = Math.min(idx + 1, 28);
    } else if (e.key == "Left" || e.key == "ArrowLeft") {
        idx = Math.max(idx - 1, 0);
    } else {
    	return;
    }
    location.replace('#tb-i' + idx);
}
</script>
</head>
<body>
	<nav class="small">
		<a href="../index.html" class="home"></a>
		<a href="#top">Top</a>
		<a href="#reliability">Reliability</a>
__NAVIGATION__
	</nav>
	<h1 id="top">IoC Analysis on Interrupts</h1>
	<h2>What is this?</h2>
	<p>
		This database consolidates the best, aka. highest Index of Coincidence (IoC) scores, for any given interrupt – considering all possible interrupt constellations. We look at the first 20 interrupts only, and try all combinations for these. But instead of looking at the whole chapter we only look at the text upto interrupt no. 21. This way we can test all the possibilities and, in case we have the right key length, find the key length with the highest probability. Since we tried all combinations for this shorter text, the complete text will be fully decrypted.
	</p>
	<p>
		Example:
	</p>
	<ul>
		<li>Input: ᛁ ᚹᚪᚱᚾ ᚣᚩᚢ ᛁᚠ ᚣᚩᚢ ᛞᚩᚾ ᛏ ᛏᛖᛚᛚ ᛗᛖ</li>
		<li>Interrupt: ᚩ</li>
		<li>Interrupt-limit: 2 <small>(with a limit of 3, the full string would be considered)</small></li>
		<li>IoC analysis on: ᛁ ᚹᚪᚱᚾ ᚣᚩᚢ ᛁᚠ ᚣᚩᚢ ᛞ</li>
	</ul>
	<p>
		Is it enough information though? Mostly. The three lowest examples have 349, 364, and 376 runes respectively. Meaning that, in the worst case, the frequency analysis will look at only 349 runes. For a key length of 25 it will leave only 14 runes per group. That is not very much but the best we can get. You could increase the interrupt count to 21 or 22 which would make it better but the execution time doubles<sup>1</sup> with each increment.
	</p>
	<p>
		<small><sup>1</sup> testing 20 interrupts takes approx. 38 hours (pages 0–55 with all interrupt runes). Or 30 seconds for a single test.</small>
	</p>

	<h3 id="assumptions">Assumptions</h3>
	<dl>
		<dt id="a1">“Normal” english text</dt>
		<dd>
			IoC is based on the assumption that we know the underlying text (english) and that the text follows a normal character distribution. If the text was prepared to be extra hard to decrypt, one could have removed all letter ‘e’ to make IoC pretty much useless (there are a few 100+ pages books that do exactly that).
			<span>⤳ Well, let us hope we have normal texts.</span>
		</dd>
		<dt id="a2">Mono- and polyalphabetic substitution</dt>
		<dd>
			Each encrypted rune has a 1-to-1 mapping to its decrypted counterpart relative to its group. For polyalphabetic ciphers the groups are determined by cycling through different substitution alphabets. The number of groups is from now on described as key length.
			<br>
			It is completely irrelevant whether the encryption algorithm uses a Ceaser shift (variant), Atbash, Vigenere, or an Affine substition, as long as it is monoalphabetic (in its group), the IoC will stay the same.
			<span>⤳ The results do not apply to polyphonic or polygraphic ciphers.</span>
		</dd>
		<dt id="a3">Single rune keys</dt>
		<dd>
			If a polyalphabetic cipher is used, we assume the decryption is based on this rune alone. E.g., it does not look at the neighboring rune, nor words, nor its position in the text. Further, the decryption takes only one rune as input.
			<span>⤳ We can not detect bi-gram or tri-gram substitions or totient streams.</span>
		</dd>
		<dt id="a4">Key length</dt>
		<dd>
			We only consider key lengths of up to 32 runes. Longer keys will split the text too much, leaving too little data per group to analyze IoC. Even 32 is probably too high in most cases. You can see that in the results that the IoC values for longer key lengths have a tendency to be higher. Keep in mind that a key length of 30 on a text with just 300 runes will be a mere 10 runes per key group.
			<br>
			That said, there is still a reason for why we go up to 32 runes. Shorter keys will have, so to say, resonance frequencies. For example, a key length of 8 will have a similar IoCs for key lengths of 16 and 24 as it is just a multiple of 8.
			<span>⤳ Don’t focus too much on high IoC values at the upper key length limit unless it is a multiple of a shorter one.</span>
		</dd>
		<dt id="a5">Whitespace</dt>
		<dd>
			IoC does not care about whitespace, at least not in this analysis. Both, training data and LP paged were stripped of any whitespace before calculating the IoC. This means, if the given whitespace should be bogus, the IoC value would still be higher compared to other key lengths.
			<span>⤳ Whitespace does not affect the results.</span>
		</dd>
		<dt id="a6">One cipher per chapter</dt>
		<dd>
			So far we assumed that each chapter (grouped by its page artwork) has exactly one cipher. Thus, each IoC is calculated based on the entire chapter rather than per page. This gives more data for frequency analysis but will fail if the chapter should have more than one cipher (or change midway).
			<span>⤳ Will not detect if a chapter has multiple ciphers (e.g., one per page, sub-chapter, or line)</span>
		</dd>
		<dt id="a7">Order of decryption</dt>
		<dd>
			We assum the decryption starts at the beginning of a page. Even though this should not matter for IoC, since a mere revert would not change the frequency, it matters for the interrupt positions. Since we only look at the first X runes, the IoC of a reversed stream may be different. Further, the interrupt positions will not help you if you need to start from the back.
			<span>⤳ Reverse order does not change IoC, hence this results are also applicable.</span>
		</dd>
	</dl>

	<h3 id="reliability">Reliability</h3>
	<p>
		The following table shows how many runes were considered while analyzing the IoC. Low value, low confidence. The darker the color is, the higher the chances are the results are accurate. Everything below <strong>384</strong> is far from ideal (16 runes per key group for a key length of 24). Everything above <strong>812</strong> is considered reliable (29 runes per key group for a key length of 28). Hence, values less than 384 have a white background and values above 812 have a dark blue one.
	</p>
	__TAB_RELIABLE__

	<h2>IoC per interrupt</h2>
	<p>
		Lets look at the first result. Assuming the interrupt rune is ᚠ, we get the following table. Notice that the column in ‘p56_an_end’ has a few dark values, even though the used cipher is a totient function (which will not be detected as of assumption <a href="#assumptions">#2</a>). If you look back at the <a href="#reliability">previous table</a>, you will see that the whole chapter only has 85 runes. Even for a key length of 6 the runes per group is only 14 runes. It is just too little data to perform IoC and so it will contain false positives.
	</p>
	<p>
		Next, if you look at the ‘0_welcome’ column you will see peaks at key lengths 8, 16, and 24. The solution to this page was a 8-length vigenere key. This is a very typical pattern for such ciphers. Note, the last peak at 30 is due to the long key length. 465 / 30 is just 15.5 runes per group. So, IoC has more freedom to “optimize” the key – and thus you should stop looking too much into higher value key lengths. Everything above 24 is not that reliable anymore.
	</p>
	<p>
		<small>P.S.: you can use the left and right keys to navigate between the interrupts. Or the navigation at the top.</small>
	</p>

	__INTERRUPT_TABLES__

	<h2>What’s next?</h2>
	<p>
		Things to try:
	</p>
	<ul>
		<li>Use different IoC metrics. E.g., remove ‘e’ from alphabet and recalculate coincidence.</li>
		<li>Split text into two (alternating) parts and test each part separately on different key lengths.</li>
		<li>Not sure if it makes sense to analyze bigrams and trigrams in this case but feel free to try.</li>
	</ul>
</body>
</html>