Cryptography Reference
In-Depth Information
1. Several equations may suggest different values of the same sum of the
key bytes. To resolve this issue, each equation with a specific sum is
associated with a set of N counters for storing the weight of each possible
value in Z
N
. However, each value is not given the same weight. The
weight of a particular value depends on the frequency of its occurrence.
A weight of 2 is assigned to values with probability > 0.05, a weight of
1 is assigned to values with probability between 0.008 and 0.05 and a
weight of 0 to all other values (these weights are tuned empirically).
2. For each equation, the value with the highest weight is considered first.
If this fails to retrieve the correct key, backtracking is performed and
the value with the second highest weight is considered, and so on. The
algorithm is parameterized by the number of attempts λ
t
to be tried on
the t-th guess, 0 ≤t < l. These parameters are tuned empirically.
3. An equivalence relation is defined over the set of all possible sums. Two
sums are said to be in the same equivalence class, if and only if the value
of each of them can be computed from the value of the other and the
values of the known sums. Counters of all sums in an equivalence class
are merged together and exactly one representative of each equivalence
class is kept.
4. If the sum K[y
1
+ 1 ⊎ y
2
] is correct, then it is expected that all the
following three events occurred with high probability.
• S
r
[r] = r, where r ∈ [y
1
+ 1,y
2
].
• S[y
1
] = j
y
1
+1
.
• S[y
2
] = j
y
2
+1
.
This information is utilized in two ways.
(a) When considering a value for a sum of of key bytes K[y
1
+ 1⊎y
2
]
which is still unknown, if the known sums indicate that the above
three events are likely to have occurred for y
1
,y
2
, then the weight
associated with the value for the sum K[y
1
+ 1⊎y
2
] is increased.
(b) All suggestions passing over some r, y
1
< r < y
2
, for which S
r
[r] =
r must have the same error
∆ = C
y
2
−C
y
1
−K[y
1
+ 1⊎y
2
].
So, if several suggestions passing over some r have the same error
∆, then other suggestions passing over r are corrected by ∆.
5. Suppose S[y] = v. Two cases may arise.
• If v < y, then the equation derived from S[y] is discarded, as it is
expected that v has already been swapped when i = v had occurred
and so is not likely to be in location y after y iterations of the KSA.
