| |
 |
|
|
Science Forum Index » Cryptography Forum » A Paranoid Encryption Mode
Page 1 of 1
|
| Author |
Message |
| John Savard |
 Posted: Thu Dec 25, 2003 5:34 pm |
|
|
|
Guest
|
Let us suppose, as a recent thread started by Mok-Kong Shen has done,
that two parties share a secret symmetric key-exchange key, and they
wish to exchange secret messages, each of which will begin with a
header field sent in the clear, containing information such as the
date and time of the message and a serial number for the message.
It is intended that no attempt will be made to generate random session
keys with physical randomness, in order to avoid the possibility of
the random session key being used to leak key bits by tampering.
Given that the header field probably has only a very limited number of
possible values, I don't find the idea of simply encrypting the header
field with the key-exchange key to produce the session key appealing,
even though it is not really insecure. I would prefer to do something
more elaborate, involving elements taken from such encryption modes as
OAEP and the various attempts at integrity-aware encryption modes.
Here, then, is my idea of an encryption mode for this case.
It is assumed that a block cipher with a 128-bit block and a 256-bit
key will be used for encryption. The session key and the key exchange
key will both be 256 bits in length.
This mode will not serve to encrypt messages shorter than 640 bits in
length, or five 128-bit blocks.
Encipherment step 1:
The message shall be divided into a first 256 bits, and a remainder. A
256-bit CRC shall be applied to the remainder of the message. The
value produced by that CRC shall be exclusive-ORed with the first 256
bits.
The result of that operation will be termed the session key seed.
Encipherment step 2:
The header to be sent in the clear with the message shall be operated
upon to produce a canonical 256-bit header token. It is not necessary
or intended that a hash function be used for this step.
The session key seed will be encrypted, using the XOR of the
key-exchange key and the header token as the key. (The first 128 bits
will be encrypted in ECB mode, the second 128 bits in CBC mode, using
the output of the ECB operation as the previous plaintext block.)
The result of this encryption shall be sent as the first 256 bits of
the message.
This result will then be XORed with the header token, and the result
of that will be encrypted, using the XOR of the key-exchange key and
the session key seed as the key.
The result of this encryption shall be the session key for encrypting
the remainder of the message.
Encipherment step 3:
The remainder of the message shall be considered to consist of
plaintext blocks P(0), P(1), P(2)... P(N) and any incomplete block at
the end of the message will be enciphered in step 4.
The first 128 bits of the session key seed shall be used to fill a
maximum-period shift register in Galois configuration that is stepped
to the left, except that if they are all zero, the value 0101...01
will be used instead.
The second 128 bits of the session key seed shall be used to fill a
maximum-period shift register in Galois configuration that is stepped
to the right.
These shift registers will be used to generate mask values M(0), M(1),
M(2)... as follows:
a) Step the first shift register.
b) Add the contents of the first shift register to the contents of the
second shift register, using modulo 2^128 addition, with the result
replacing the contents of the second shift register.
c) Step the second shift register. Its contents will be a mask value.
The first time this is done, M(0) is generated.
The remainder of the message will now be enciphered, using the session
key SK, to produce ciphertext blocks as follows:
C(i) = M(i) XOR E( P(i) XOR M(i+1) XOR C(i-1), SK )
where C(-1) will be treated as consisting of all zeroes.
Encipherment step 4:
If there is a portion of the remainder of the message that is left
over after dividing the remainder into blocks P(0) to P(N), then if
that portion is k bits in length, P(N+1) shall be formed from the last
128-k bits of P(N) followed by the left over portion of that message,
and it shall be enciphered as follows:
C(N+1) = M(N+1) XOR E( P(N+1) XOR M(N+2) XOR Q, SK)
where Q is the concatenation of the last 64 bits of P(N-2) and the
first 64 bits of P(N-1).
The last 128-k bits of P(N) will not be included in the message, which
will consist of the header field, the first 256 bits of the message
proper as generated in step 2, P(0) through P(N-1), the first k bits
of P(N), and P(N+1) if a partial block exists or P(0) through P(N) if
a partial block does not exist.
Encipherment step 5:
A 16-bit checksum, using a cyclic redundancy check polynomial, shall
be generated for the encrypted message exclusive of the clear header
field, but including the first 256 bits of the encrypted message and
the encrypted remainder of the message including any partial block at
the end.
The concatenation of the last 112 bits of the message and this 16 bit
checksum will be encrypted using the session key.
All but the last 112 bits of the message will be masked by being XORed
with the last 112 bits of the message repeatedly. The last 112 bits of
the message will not be sent, instead the 128 bit result of the
previous encryption will be sent at the end of the message.
Other details need to be addressed. Steps must be taken to ensure that
the header field is not used to leak key bits, and that key bits are
not hidden invisibly in messages.
A 16-bit checksum is, of course, not enough to prevent existential
forgeries absolutely, but it will serve to allow messages corrupted by
transmission noise to be rejected, and to make it likely that other
types of forgery attempts will be detected.
It is also intended that the header field will at least be sufficient
to prevent the session key from being a hash of the session key seed
that has significantly less than 2^256 possible values.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html |
|
|
| Back to top |
|
| John Savard |
| Posted: Thu Dec 25, 2003 9:49 pm |
|
|
|
Guest
|
On Thu, 25 Dec 2003 22:34:23 GMT, jsavard@ecn.aSBLOKb.caNADA.invalid
(John Savard) wrote, in part:
Quote: All but the last 112 bits of the message will be masked by being XORed
with the last 112 bits of the message repeatedly.
This must be changed. The first 256 bits of the message must be
excluded from the XOR, or, of course, the authorized decryptor will be
unable to retrieve the session key.
I have not even the excuse of too much eggnog to exculpate this silly
mistake.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html |
|
|
| Back to top |
|
| lyal |
| Posted: Mon Dec 29, 2003 1:57 am |
|
|
|
Guest
|
"John Savard" <jsavard@ecn.aSBLOKb.caNADA.invalid> wrote in message
news:3feb5bb7.47376@news.ecn.ab.ca...
Quote: Let us suppose, as a recent thread started by Mok-Kong Shen has done,
that two parties share a secret symmetric key-exchange key, and they
wish to exchange secret messages, each of which will begin with a
header field sent in the clear, containing information such as the
date and time of the message and a serial number for the message.
It is intended that no attempt will be made to generate random session
keys with physical randomness, in order to avoid the possibility of
the random session key being used to leak key bits by tampering.
Given that the header field probably has only a very limited number of
possible values, I don't find the idea of simply encrypting the header
field with the key-exchange key to produce the session key appealing,
even though it is not really insecure. I would prefer to do something
more elaborate, involving elements taken from such encryption modes as
OAEP and the various attempts at integrity-aware encryption modes.
[snip]
Why not hash (or use any standard one-way function based on secret key
algorithms) the public values in the header, then hash the result with the
pre-distributed master symmetric key(s)?
And any standard block or stream cipher may be used - no new
crypto-analysis needed for the crypto steps.
This means the message/session key is unique to a message (and statistically
probably not used for any other message), and there is significant
computational difficulty in determining the master key shoud the session key
be derived in any fashion, to the limit of the OWF reversability protection.
A response message may use a different mater key, ensuring a degree of
directionality in the keys used per message, per network node.
As an aside -as the message keys are statistically unique to the message,
and the encrypted version of a password is unique to a user, this process
enables electronic signatures (the full description covers a few more steps)
under the UNCITRAL model law on electronic signatures - all without PKI.
Use different master keys for confidentiality paths, integrity paths,
authentication/electronic signatures, and no two messages (statistically
speaking) will use the same session keys for any security purpose.
Products using this concept, and which covered by patents in some
jurisdictions, are on the market today.
Lyal |
|
|
| Back to top |
|
| Kenneth Almquist |
| Posted: Sun Jan 04, 2004 8:17 pm |
|
|
|
Guest
|
jsavard@ecn.aSBLOKb.caNADA.invalid (John Savard)
Quote: Let us suppose, as a recent thread started by Mok-Kong Shen has done,
that two parties share a secret symmetric key-exchange key, and they
wish to exchange secret messages, each of which will begin with a
header field sent in the clear, containing information such as the
date and time of the message and a serial number for the message.
It is intended that no attempt will be made to generate random session
keys with physical randomness, in order to avoid the possibility of
the random session key being used to leak key bits by tampering.
Given that the header field probably has only a very limited number of
possible values, I don't find the idea of simply encrypting the header
field with the key-exchange key to produce the session key appealing,
even though it is not really insecure. I would prefer to do something
more elaborate, involving elements taken from such encryption modes as
OAEP and the various attempts at integrity-aware encryption modes.
It's not clear to me that the limited number of possible header
values is a problem.
I suppose that one issue is that the limited number of possible
header values increases the likelyhood that there will be duplicate
header values, resulting in duplicate session keys. But let's assume
the message header includes, among other things:
1) A sequence number, which periodicaly wraps around.
2) The data/time stamp indicating when the message was sent.
3) The identify of the machine sending the messages.
If the time it takes for the sequence number field to wrap around is
greater than the granularity of the time stamp, and if the time stamp
service is well behaved (meaning that the reported time doesn't go
backwards or remain unchanged for long periods of time), then each
message header will be unique. So it seems to me that this is
an issue to the extent that you don't trust the time stamp service.
Another issue is that the limited number of header values might make
it possible for an attacker to perform some sort of precomputations
which would decrease the time to break a message once the attacker
intercepts it. In my view, this is not a real concern.
If you don't want to rely on the header fields alone to generate
the session key, there are two possibilities. One is to use a
random source of bits to generate the key. The other is to use
the (unencrypted) body of the message as well as the header, to
generated the session key.
If the first possibility is chosen, you want to be sure that the
random bits are not used to leak key data. This means that a message
sender must obtain the random bits from a separate random bit service.
This avoids leaking key bits because the random bit server doesn't
know the key, but it creates the risk that an attacker could replay
messages from the random bit server and thereby cause the same
session key to be reused. In addition, the cost of the random
bit server and the network traffic required to obtain bits from
the random bit server may make this option unattactive.
The second possibility--making the session key depend in part on
the message body--is equivalent to changing making the session
key depend only on the header, and using a different encryption
algorithm. In case that point isn't clear, let me restate it
more formally.
Let H be the message header, P (for plaintext) be the message
body, and X be the key exchange key. Let Hash be a function,
and E(P, key) be an encryption function, We use the notation
<a, b> to denote the ordered pair containing a and b, and ~X to
denote the bitwise complement of X. Now define:
E1(P, <X, H>) = E(P, E(Hash(H), X))
E2(P, <X, H>) = <E(Hash(<H, P>), ~X), E(P, E(Hash(<H, P>), X))>
Both E1 and E2 are encryption functions which use the ordered
pair <X, H> as a key.
For both E1 and E2, if we assume that the E and Hash functions have
no cryptographic weaknesses, then the most efficient attack is an
exhaustive search. The size of the key space is the same for both
functions. If E does contain a cryptographic weakness, then it
is possible that the differing structures of E1 and E2 mean that
one of them is more vulnerable than the other, but it is not clear
to me which one would be more vulterable. E1 is simpler, which
might make it easier to break, but E2 includes a call to E in
which both the key and the text to be encrypted depend on P,
possibly allowing an attacker to take advantage of a weakness
in the way changes to plaintext and key bits interact. Also,
with E2 the ciphertext is longer than the plaintext, giving the
attacker more ciphertext to work with.
Your proposal is different from E2, and I must admit I haven't
looked at it very carefully, but it seems to me that the same
basic considerations apply. I don't want to sound too negative
here, but you've introduced a bunch of complexity without, as
far as I can see, making a convincing case that the complexity
produces security which is stronger or as strong as that provided
by E1.
Kenneth Almquist |
|
|
| Back to top |
|
| John Savard |
| Posted: Sun Jan 04, 2004 10:11 pm |
|
|
|
Guest
|
On 4 Jan 2004 20:17:06 -0500, ka@sorry.no.email (Kenneth Almquist)
wrote, in part:
Quote: The second possibility--making the session key depend in part on
the message body--is equivalent to changing making the session
key depend only on the header, and using a different encryption
algorithm. In case that point isn't clear, let me restate it
more formally.
You are quite correct. After all, what I am doing is taking the
header, and using it as input to an encryption operation performed on
the message as a whole.
But different encryption algorithms aren't equivalent in security.
John Savard
http://home.ecn.ab.ca/~jsavard/index.html |
|
|
| Back to top |
|
| Kenneth Almquist |
| Posted: Mon Jan 05, 2004 7:20 pm |
|
|
|
Guest
|
John Savard wrote:
Quote: On 4 Jan 2004 20:17:06 -0500, ka@sorry.no.email (Kenneth Almquist)
wrote, in part:
The second possibility--making the session key depend in part on
the message body--is equivalent to changing making the session
key depend only on the header, and using a different encryption
algorithm.
You are quite correct. After all, what I am doing is taking the
header, and using it as input to an encryption operation performed on
the message as a whole.
But different encryption algorithms aren't equivalent in security.
Yes, but saying that two algorithms aren't equivalent in security
doesn't tell us *which* of the two algorithms is more secure. In
the article which began this thread, you posted a fairly complex
design. However, you either failed to explain why one might choose
your proposal over a simple design, or else you did explain but I
failed to understand the explanation.
Kenneth Almquist |
|
|
| Back to top |
|
| |
|
Page 1 of 1
All times are GMT - 5 Hours
The time now is Tue Oct 07, 2008 4:15 pm
|
|