Cryptography Reference
In-Depth Information
Algorithm 1.
KKSforge
: algorithm that forges a valid KKS signature.
PARAMETERS:
r
: number of iterations,
l
: small integer (
l
40),
p
: very small integer (1
p
4).
S
: a subset of [1
···N
] from which in each iteration a subset of cardinality
K
+
k
+
l
will be randomly chosen.
INPUT:
H
OUTPUT:
a list
∈
F
2
×
L
containing valid signature/message pairs (
σ,
x
)
F
2
.
1:
L←∅
.
2:
for
1
t
r
do
3:
Step 1:
Randomly pick
K
+
k
+
l
positions among
S
to form the set
I
.Thisset
is partitioned into
I
=
I
1
∪ I
2
such that
||I
1
|−|I
2
||
1.
4:
Step 2:
Perform Gaussian elimination over the complementary set
{
1
,
2
,...,N
+
to put
H
in quasi-systematic form (as shown in Figure 4).
k}\I
5:
Step 3:
6:
Generate all binary vectors
x
1
of length
(
K
+
k
+
l
)
/
2
and weight
p
and store
them in a table at the address
H
1
x
1
7:
for all
binary vectors
x
2
of length
(
K
+
k
+
l
)
/
2
and weight
p
do
x
1
stored at the address
H
2
x
2
do
8:
for all
de
=(
x
1
||
x
2
)
H
3
and form the codeword
x
de
=(
x
1
||
x
2
||
x
3
)of
9:
Compute
x
3
C
pub
10:
if
t
1
|
x
[1
···N
]
|
t
2
then
11:
L←L∪{
x
}
12:
end if
13:
end for
14:
end for
15:
end for
16:
return
L
4.3 Explaining the Success of the Attack
It turns out that this attack works extremely well on all the parameter choices
made in the literature, and this even without knowing a single message-signature
pair which would make life much easier for the attacker as demonstrated in
[COV07]. In a first pass, the attack recovers easily message-signature pairs for
all the parameters suggested in [BMJ11, KKS97, KKS05]. Once a signature-
message pair is obtained, it can be exploited to bootstrap an attack that recovers
the private key as we will explain later.
The reason why the attack works much better here than for general linear codes
comes from the fact that
ˆ
does not behave like a random matrix at all even if the
two chosen matrices for the scheme, namely
H
H
and
G
are chosen at random
.The
left part and the right part
H
and
F
are namely related by the equation:
T
.
F
=
H
J
G
