Re: [tor-dev] Request for comment: AEZ for relay cryptography
Seems a great challenge !!!
Lluís
Nick Mathewson:
> [This is a draft proposal; I'm not giving it a number yet. I'm hoping
> it'll receive some good advice.]
>
> Filename: xxx-aez-relay.txt
> Title: AEZ for relay cryptography
> Author: Nick Mathewson
> Created: 13 Oct 2015
> Status: Draft
>
> 1. Summary and preliminaries
>
>This proposal describes an improved algorithm for circuit
>encryption, based on the wide-block SPRP AEZ. I also describe the
>attendant bookkeeping, including CREATE cells, and several
>variants of the proposal.
>
>For more information about AEZ, see
>http://web.cs.ucdavis.edu/~rogaway/aez/
>
>For motivations, see proposal 202.
>
> 2. Specifications
>
> 2.1. New CREATE cell types.
>
>We add a new CREATE cell type that behaves as an ntor cell but which
>specifies that the circuit will be created to use this mode of
>encryption.
>
>[TODO: Can/should we make this unobservable?]
>
>The ntor handshake is performed as usual, but a different PROTOID is
>used:
> "ntor-curve25519-sha256-aez-1"
>
>To derive keys under this handshake, we still use HKDF_SHA256, but we
>produce 96 bytes of output:
>
> struct hkdf_output {
> u8 key_forward[48];
> u8 key_backward[48];
> };
>
>These two fields are constant for the lifetime of the circuit. (But
>see section 4.3 below.)
>
>(Also see 4.1 for a variant that uses less storage key material.)
>
> 2.2. New relay cell payload
>
>We specify the following relay cell payload format, to be used when
>the exit node circuit hop was created with the CREATE format in 2.1
>above:
>
> struct relay_cell_payload {
> u32 zero_1;
> u16 zero_2;
> u16 stream_id;
> u16 length IN [0..498];
> u8 command;
> u8 data[498]; // payload_len - 11
> };
>
>Note that the payload length is unchanged. The fields are now
>rearranged to be aligned. The 'recognized' and 'length' fields are
>replaced with zero_1, zero_2, and the high 7 bits of length, for a
>minimum of 55 bits of unambigious verification. (Additional
>verification can be done by checking the other fields for
>correctness; AEZ users can exploit plaintext redundancy for
>additional cryptographic checking.)
>
>When encrypting a cell for a hop that was created using one of these
>circuits, clients and relays encrypt them using the AEZ algorithm
>with the following parameters:
>
>Key = Kf for forward cells, Kb for backward cells.
>
># In theory, we are allowed to use a single key here, but I'm
>#
>
>tau = 0
>
># We want no per-hop ciphertext expansion. Instead we use
># redundancy in the plaintext to authenticate the data.
>
>Nonce =
> struct {
>u64 cell_number;
>u8 is_forward;
>u8 is_early;
> }
>
># The cell number is the number of relay cells that have
># traveled in this direction on this circuit before this cell.
># ie, it's zero for the first cell, two for the second, etc.
>#
># is_forward is 1 for outbound cells, 0 for inbound cells.
># is_early is 1 for cells packaged as RELAY_EARLY, 0 for
># cells packaged as RELAY.
>#
># Technically these two values would be more at home in AD
># than in Nonce; but AEZ doesn't actually distinguish N and AD
># internally.
>
>AD = [ The last 32 bytes of the previous cell's plaintext,
> if this is not the first cell sent in this direction on
> this circuit ]
>
># Using this as additional data guarantees that any corrupt
># ciphertext received will corrupt the plaintext, which will
># corrupt all future plaintexts. Using the last 32 bytes of the
># ciphertext would not have the same property.
>
>This instantiates a wide-block cipher, tweaked based on the cell
>index and direction. It authenticates part of the previous cell's
>plaintext, thereby ensuring that if the previous cell was corrupted,
>this cell will be unrecoverable.
>
>
> 3. Design considerations
>
> 3.1. Wide-block pros and cons?
>
>See proposal 202, section 4.
>
> 3.2. Given wide-block, why AEZ?
>
>It's a reasonably fast probably secure wide-block cipher. In
>particular, it's performance-competitive with AES_CTR.
>
> (How fast is it?
>
> To encrypt a 509-byte relay cell with a 16 byte nonce and 32 bytes
> of additional data, AEZ only uses 360 aes rounds. This is the same
> number of aes rounds as we'd need to CTR encrypt a 512-byte cell
> with 11.25 rounds per block. AES128 uses 10 rounds per block;
> AES256 uses 14 rounds per block.
>
> We could chop out 4 of the AES rounds by optimizing the code
> for the tau=0 case, or with AD shene
Re: [tor-dev] Request for comment: AEZ for relay cryptography
Nick Mathewson transcribed 3.1K bytes:
> On Tue, Oct 13, 2015 at 8:05 AM, Mike Perry wrote:
>> Nick Mathewson:
> [...]
>>> (How fast is it?
>>>
>>> To encrypt a 509-byte relay cell with a 16 byte nonce and 32 bytes
>>> of additional data, AEZ only uses 360 aes rounds. This is the same
>>> number of aes rounds as we'd need to CTR encrypt a 512-byte cell
>>> with 11.25 rounds per block. AES128 uses 10 rounds per block;
>>> AES256 uses 14 rounds per block.
>>>
>>> We could chop out 4 of the AES rounds by optimizing the code
>>> for the tau=0 case, or with AD shenenegans, but that's probably
>>> unwise.
>>>
>>> Additionally, we would no longer need to maintain a running SHA-1
>>> of cells.)
>>
>> Can you explain how the 'recognized' behavior will work in more detail
>> with AEZ then? In the current circuit crypto, the shorter recognized
>> field is used just as a hint to check the larger SHA-1 hash. But with
>> what you specified above, it sounds like there is now only 55 bits with
>> which to check for 'recognized' at a hop, before causing some kind of
>> (unpredictable?) error condition due to other, later protocol checks
>> failing?
>
> Sure!
>
> Currently, the 2-byte 'recognized' field tells us whether to check a
> 4-byte, truncated SHA1 hash. That gives 32 bits of resistance vs
> forgery, and a one-in-65536 chance of checking the the SHA1 hash when
> we don't need to. (The recognized field doesn't provide any forgery
> resistance, since AES-CTR is malleable.)
>
> So the current pseudocode is:
> P_cell = CTR_Decrypt(Key, Ctr, Enc_cell)
> If (P_cell.recognized == 0 &&
>SHA1(sha_state + P_cell)[:4] == P_cell.digest) {
> // Cell is recognized and valid; add P_cell to sha_state and handle it.
> } else {
>// Cell is not recognized or not valid; forward it to the next
> hop in the circuit
>}
>
> With this AEZ proposal, we have 55 bits of forgery resistance, since
> any attempt to meddle with any bit in the ciphertext will have an
> unpredictable affect on all bits on the plaintext. (It's an SPRP).
> So the algorithm is:
>
> P_cell = AEZ_decrypt(Key, State, Enc_cell)
> If (P_cell.zero_16 == 0 && P_cell.zero_32 == 0 &&
>P_cell.length <= 498) {
> // Cell is recognized and valid; add P_cell to state and handle it.
> } else {
>// Cell is not recognized or not valid; forward it to the next
> hop in the circuit.
>}
>
> This represents an _increase_ in our security, since we now have a
> much better chance of rejecting random or tampered cells.
>
>> In general, it would also be nice to specify in detail how leaky-pipe
>> circuits could still be used without breaking the construction,
>> especially as we get closer to chosing which one of these options to
>> take. It sounds like some of the options in 4.2 and 4.3 may break it, if
>> we're not careful with the implementation.
>
> Sounds good; I'll try to specify how it works. It's important to add
> provisos like "processed at this hop" to most of the descriptions
> there, so I should really add pseudocode as appropriate.
I should take a closer look at using AEZ w.r.t. leaky pipes and loose-source
routing. However, my inclination is to say that, when using the leaky pipe
feature, you can still talk to any node in the circuit simply by ensuring
that, when that node decrypts it, the 16(ish) zeros come out as expected.
Similarly, for loose-source routed circuits, since (essentially) all cells
arriving (in either direction) at a node which is utilising the loose-source
feature are processed as "unrecognised" — regardless of whether or not they
are actually recognised — also nothing should change (except for the increased
forgery resistance that Nick mentioned).
Ex. 1: Alice is building her circuit through Bob the Bridge, and Bob uses
Bridge Guards. Alice would like to extend to Charlie, and so she sends an
EXTEND2 inside a RELAY_EARLY to Bob which says so. Bob recieves this, does
AEZ_Decrypt([…]) on the RELAY_EARLY cell, notices that the 16(ish) bytes at
the end are zeros, and consequently updates the circuit's digest. Finally Bob
forwards the cell through the the leaky pipe towards the Bridge Guard (mostly)
regardless of whether the cell was "recognised". (Cf. proposal #188 §3.1.1
steps 6.a. and 6.c., but nothing should really change with the switch to AEZ
as far as I can tell.)
--
♥Ⓐ isis agora lovecruft
_
OpenPGP: 4096R/0A6A58A14B5946ABDE18E207A3ADB67A2CDB8B35
Current Keys: https://blog.patternsinthevoid.net/isis.txt
signature.asc
Description: Digital signature
___
tor-dev mailing list
[email protected]
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Request for comment: AEZ for relay cryptography
On Tue, Oct 13, 2015 at 8:05 AM, Mike Perry wrote:
> Nick Mathewson:
[...]
>> (How fast is it?
>>
>> To encrypt a 509-byte relay cell with a 16 byte nonce and 32 bytes
>> of additional data, AEZ only uses 360 aes rounds. This is the same
>> number of aes rounds as we'd need to CTR encrypt a 512-byte cell
>> with 11.25 rounds per block. AES128 uses 10 rounds per block;
>> AES256 uses 14 rounds per block.
>>
>> We could chop out 4 of the AES rounds by optimizing the code
>> for the tau=0 case, or with AD shenenegans, but that's probably
>> unwise.
>>
>> Additionally, we would no longer need to maintain a running SHA-1
>> of cells.)
>
> Can you explain how the 'recognized' behavior will work in more detail
> with AEZ then? In the current circuit crypto, the shorter recognized
> field is used just as a hint to check the larger SHA-1 hash. But with
> what you specified above, it sounds like there is now only 55 bits with
> which to check for 'recognized' at a hop, before causing some kind of
> (unpredictable?) error condition due to other, later protocol checks
> failing?
Sure!
Currently, the 2-byte 'recognized' field tells us whether to check a
4-byte, truncated SHA1 hash. That gives 32 bits of resistance vs
forgery, and a one-in-65536 chance of checking the the SHA1 hash when
we don't need to. (The recognized field doesn't provide any forgery
resistance, since AES-CTR is malleable.)
So the current pseudocode is:
P_cell = CTR_Decrypt(Key, Ctr, Enc_cell)
If (P_cell.recognized == 0 &&
SHA1(sha_state + P_cell)[:4] == P_cell.digest) {
// Cell is recognized and valid; add P_cell to sha_state and handle it.
} else {
// Cell is not recognized or not valid; forward it to the next
hop in the circuit
}
With this AEZ proposal, we have 55 bits of forgery resistance, since
any attempt to meddle with any bit in the ciphertext will have an
unpredictable affect on all bits on the plaintext. (It's an SPRP).
So the algorithm is:
P_cell = AEZ_decrypt(Key, State, Enc_cell)
If (P_cell.zero_16 == 0 && P_cell.zero_32 == 0 &&
P_cell.length <= 498) {
// Cell is recognized and valid; add P_cell to state and handle it.
} else {
// Cell is not recognized or not valid; forward it to the next
hop in the circuit.
}
This represents an _increase_ in our security, since we now have a
much better chance of rejecting random or tampered cells.
> In general, it would also be nice to specify in detail how leaky-pipe
> circuits could still be used without breaking the construction,
> especially as we get closer to chosing which one of these options to
> take. It sounds like some of the options in 4.2 and 4.3 may break it, if
> we're not careful with the implementation.
Sounds good; I'll try to specify how it works. It's important to add
provisos like "processed at this hop" to most of the descriptions
there, so I should really add pseudocode as appropriate.
best,
--
Nick
___
tor-dev mailing list
[email protected]
https://lists.torproject.org/cgi-bin/mailman/listinfo/tor-dev
Re: [tor-dev] Request for comment: AEZ for relay cryptography
Nick Mathewson:
> [This is a draft proposal; I'm not giving it a number yet. I'm hoping
> it'll receive some good advice.]
>
> Filename: xxx-aez-relay.txt
> Title: AEZ for relay cryptography
> Author: Nick Mathewson
> Created: 13 Oct 2015
> Status: Draft
>
> 1. Summary and preliminaries
>
>This proposal describes an improved algorithm for circuit
>encryption, based on the wide-block SPRP AEZ. I also describe the
>attendant bookkeeping, including CREATE cells, and several
>variants of the proposal.
>
>For more information about AEZ, see
>http://web.cs.ucdavis.edu/~rogaway/aez/
>
>For motivations, see proposal 202.
>
> 2. Specifications
>
> 2.1. New CREATE cell types.
>
>We add a new CREATE cell type that behaves as an ntor cell but which
>specifies that the circuit will be created to use this mode of
>encryption.
>
>[TODO: Can/should we make this unobservable?]
>
>The ntor handshake is performed as usual, but a different PROTOID is
>used:
> "ntor-curve25519-sha256-aez-1"
>
>To derive keys under this handshake, we still use HKDF_SHA256, but we
>produce 96 bytes of output:
>
> struct hkdf_output {
> u8 key_forward[48];
> u8 key_backward[48];
> };
>
>These two fields are constant for the lifetime of the circuit. (But
>see section 4.3 below.)
>
>(Also see 4.1 for a variant that uses less storage key material.)
>
> 2.2. New relay cell payload
>
>We specify the following relay cell payload format, to be used when
>the exit node circuit hop was created with the CREATE format in 2.1
>above:
>
> struct relay_cell_payload {
> u32 zero_1;
> u16 zero_2;
> u16 stream_id;
> u16 length IN [0..498];
> u8 command;
> u8 data[498]; // payload_len - 11
> };
>
>Note that the payload length is unchanged. The fields are now
>rearranged to be aligned. The 'recognized' and 'length' fields are
>replaced with zero_1, zero_2, and the high 7 bits of length, for a
>minimum of 55 bits of unambigious verification. (Additional
>verification can be done by checking the other fields for
>correctness; AEZ users can exploit plaintext redundancy for
>additional cryptographic checking.)
>
>When encrypting a cell for a hop that was created using one of these
>circuits, clients and relays encrypt them using the AEZ algorithm
>with the following parameters:
>
>Key = Kf for forward cells, Kb for backward cells.
>
># In theory, we are allowed to use a single key here, but I'm
>#
>
>tau = 0
>
># We want no per-hop ciphertext expansion. Instead we use
># redundancy in the plaintext to authenticate the data.
>
>Nonce =
> struct {
>u64 cell_number;
>u8 is_forward;
>u8 is_early;
> }
>
># The cell number is the number of relay cells that have
># traveled in this direction on this circuit before this cell.
># ie, it's zero for the first cell, two for the second, etc.
>#
># is_forward is 1 for outbound cells, 0 for inbound cells.
># is_early is 1 for cells packaged as RELAY_EARLY, 0 for
># cells packaged as RELAY.
>#
># Technically these two values would be more at home in AD
># than in Nonce; but AEZ doesn't actually distinguish N and AD
># internally.
>
>AD = [ The last 32 bytes of the previous cell's plaintext,
> if this is not the first cell sent in this direction on
> this circuit ]
>
># Using this as additional data guarantees that any corrupt
># ciphertext received will corrupt the plaintext, which will
># corrupt all future plaintexts. Using the last 32 bytes of the
># ciphertext would not have the same property.
>
>This instantiates a wide-block cipher, tweaked based on the cell
>index and direction. It authenticates part of the previous cell's
>plaintext, thereby ensuring that if the previous cell was corrupted,
>this cell will be unrecoverable.
>
>
> 3. Design considerations
>
> 3.1. Wide-block pros and cons?
>
>See proposal 202, section 4.
>
> 3.2. Given wide-block, why AEZ?
>
>It's a reasonably fast probably secure wide-block cipher. In
>particular, it's performance-competitive with AES_CTR.
>
> (How fast is it?
>
> To encrypt a 509-byte relay cell with a 16 byte nonce and 32 bytes
> of additional data, AEZ only uses 360 aes rounds. This is the same
> number of aes rounds as we'd need to CTR encrypt a 512-byte cell
> with 11.25 rounds per block. AES128 uses 10 rounds per block;
> AES256 uses 14 rounds per block.
>
> We could chop out 4 of the AES rounds by optimizing the code
> for the tau=0 case, or with AD shenenegans, but that's probably
> u
[tor-dev] Request for comment: AEZ for relay cryptography
[This is a draft proposal; I'm not giving it a number yet. I'm hoping
it'll receive some good advice.]
Filename: xxx-aez-relay.txt
Title: AEZ for relay cryptography
Author: Nick Mathewson
Created: 13 Oct 2015
Status: Draft
1. Summary and preliminaries
This proposal describes an improved algorithm for circuit
encryption, based on the wide-block SPRP AEZ. I also describe the
attendant bookkeeping, including CREATE cells, and several
variants of the proposal.
For more information about AEZ, see
http://web.cs.ucdavis.edu/~rogaway/aez/
For motivations, see proposal 202.
2. Specifications
2.1. New CREATE cell types.
We add a new CREATE cell type that behaves as an ntor cell but which
specifies that the circuit will be created to use this mode of
encryption.
[TODO: Can/should we make this unobservable?]
The ntor handshake is performed as usual, but a different PROTOID is
used:
"ntor-curve25519-sha256-aez-1"
To derive keys under this handshake, we still use HKDF_SHA256, but we
produce 96 bytes of output:
struct hkdf_output {
u8 key_forward[48];
u8 key_backward[48];
};
These two fields are constant for the lifetime of the circuit. (But
see section 4.3 below.)
(Also see 4.1 for a variant that uses less storage key material.)
2.2. New relay cell payload
We specify the following relay cell payload format, to be used when
the exit node circuit hop was created with the CREATE format in 2.1
above:
struct relay_cell_payload {
u32 zero_1;
u16 zero_2;
u16 stream_id;
u16 length IN [0..498];
u8 command;
u8 data[498]; // payload_len - 11
};
Note that the payload length is unchanged. The fields are now
rearranged to be aligned. The 'recognized' and 'length' fields are
replaced with zero_1, zero_2, and the high 7 bits of length, for a
minimum of 55 bits of unambigious verification. (Additional
verification can be done by checking the other fields for
correctness; AEZ users can exploit plaintext redundancy for
additional cryptographic checking.)
When encrypting a cell for a hop that was created using one of these
circuits, clients and relays encrypt them using the AEZ algorithm
with the following parameters:
Key = Kf for forward cells, Kb for backward cells.
# In theory, we are allowed to use a single key here, but I'm
#
tau = 0
# We want no per-hop ciphertext expansion. Instead we use
# redundancy in the plaintext to authenticate the data.
Nonce =
struct {
u64 cell_number;
u8 is_forward;
u8 is_early;
}
# The cell number is the number of relay cells that have
# traveled in this direction on this circuit before this cell.
# ie, it's zero for the first cell, two for the second, etc.
#
# is_forward is 1 for outbound cells, 0 for inbound cells.
# is_early is 1 for cells packaged as RELAY_EARLY, 0 for
# cells packaged as RELAY.
#
# Technically these two values would be more at home in AD
# than in Nonce; but AEZ doesn't actually distinguish N and AD
# internally.
AD = [ The last 32 bytes of the previous cell's plaintext,
if this is not the first cell sent in this direction on
this circuit ]
# Using this as additional data guarantees that any corrupt
# ciphertext received will corrupt the plaintext, which will
# corrupt all future plaintexts. Using the last 32 bytes of the
# ciphertext would not have the same property.
This instantiates a wide-block cipher, tweaked based on the cell
index and direction. It authenticates part of the previous cell's
plaintext, thereby ensuring that if the previous cell was corrupted,
this cell will be unrecoverable.
3. Design considerations
3.1. Wide-block pros and cons?
See proposal 202, section 4.
3.2. Given wide-block, why AEZ?
It's a reasonably fast probably secure wide-block cipher. In
particular, it's performance-competitive with AES_CTR.
(How fast is it?
To encrypt a 509-byte relay cell with a 16 byte nonce and 32 bytes
of additional data, AEZ only uses 360 aes rounds. This is the same
number of aes rounds as we'd need to CTR encrypt a 512-byte cell
with 11.25 rounds per block. AES128 uses 10 rounds per block;
AES256 uses 14 rounds per block.
We could chop out 4 of the AES rounds by optimizing the code
for the tau=0 case, or with AD shenenegans, but that's probably
unwise.
Additionally, we would no longer need to maintain a running SHA-1
of cells.)
It seems secure-ish too. Several cryptographers I know seem to
think it's likely secure enough, and almost surely at least as
good as AES.
[There are many other competing wide-block SPRP c
