Cryptography Reference
In-Depth Information
combination of parts can verify that the data is there. This applica-
tion may be valuable if you happen to be storing the information on
your hard disk and you want to deny that it is there.
Ross Anderson, Roger Needham, and Adi Shamir created two ver-
sions of what they called a steganographic file system. [ANS98] Their
first uses math very similar to secret sharing and so it is described
here.
The system grabs a large block of disk space, randomizes it, and
then absorbs files that are protected with passwords. If you don't
know the password, then you can't find the file. If you do know the
password, then the random bits produce the file. There's no way to
identify that the file exists without the password.
“Three may keep a secret
if two are
dead.”-Benjamin
Franklin
This scheme is far from perfect. For it to work well, the passwords
must be assigned in a hierarchy. That means if someone knows one
password,
K
i
, then they must know all other passwords
K
j
where
. If there are only three files, then the person with access
to file 3 must also have access to files 1 and 3. Anderson, Needham
and Shamir imagine that a person under interrogation may reveal
the password to several modestly dangerous files without revealing
the more sensitive ones.
The mathematics is all linear algebra. For the sake of simplicity,
the system is defined for binary numbers where addition is the XOR
(
0
≤ j<i
⊕
) operation and multiplication is the AND (
)operation.
A basic steganographic file system can hold
·
m
n
bits
long. In the beginning, the files are set to be random values that are
changed as information is stored in the system. It often helps to think
of the file system as a big matrix with
files that are
m
rows and
n
columns. Let
C
i
stand for the
th
row.
The password for file
i
j
is
K
j
,a
m
-bit-long vector where
K
j
(
i
)
th
bit of the vector. To recover file
stands the
i
j
from the file system,
add together all of the rows,
C
i
,where
K
j
(
i
)=1
.Thatis:
m
⊕
i=1
K
j
(
i
)
C
i
.
How do you store a file in the system? Here's a basic sketch of the
steps for storing
one
file:
n
1. Break it into
bit blocks.
2. Choose a password for each block. One good solution is to
concatenate a random string,
, before the password, hash it
with a cryptographically secure hash function,
S
H
, and take the
first
m−
1
bits to serve as
K
j
.
3. Add a parity bit to
K
j
to make sure it is the correct length. Use
odd parity to ensure that the number of 1 bits in the vector
