Mixing
Hashing a counter to prevent distinguishers in CTR mode
$begingroup$
Because a block cipher is a PRP and thus bijective, the fact that the input in CTR mode never repeats means that each block of keystream will be unique. This creates a distinguisher from random data following the birthday bound if enough data is encrypted even before the counter repeats, especially if the block size is too small. Stream ciphers like ChaCha20 avoid this issue by feeding a counter into a PRF instead of a PRP, meaning blocks of keystream will repeat according to the birthday bound.
Is it feasible to mitigate this problem with a PRP by feeding the nonce and counter through a very fast and deterministic hashing function first? Because the input to the block cipher is not secret in CTR mode, it would not need to be a secure hash function. All it would need to do is admit collisions due to the birthday bound, allowing for a repeating block in the keystream after roughly $2^{n/2}$ blocks.
Is this correct? If so, what is the fastest hash function which has the required properties?
ctr distinguisher
asked Jan 28 at 4:03
forestforest
4,55811743
$endgroup$
add a comment |
$begingroup$
Because a block cipher is a PRP and thus bijective, the fact that the input in CTR mode never repeats means that each block of keystream will be unique. This creates a distinguisher from random data following the birthday bound if enough data is encrypted even before the counter repeats, especially if the block size is too small. Stream ciphers like ChaCha20 avoid this issue by feeding a counter into a PRF instead of a PRP, meaning blocks of keystream will repeat according to the birthday bound.
Is it feasible to mitigate this problem with a PRP by feeding the nonce and counter through a very fast and deterministic hashing function first? Because the input to the block cipher is not secret in CTR mode, it would not need to be a secure hash function. All it would need to do is admit collisions due to the birthday bound, allowing for a repeating block in the keystream after roughly $2^{n/2}$ blocks.
Is this correct? If so, what is the fastest hash function which has the required properties?
ctr distinguisher
asked Jan 28 at 4:03
forestforest
4,55811743
$endgroup$
2
$begingroup$
I think it would need to be a secure hash function, otherwise we could force it to generate identical key streams at will.
$endgroup$
– Ella Rose♦
Jan 28 at 6:01
1
$begingroup$
If you want to use AES or a typical block cipher, the solution to this problem is dual CTR streams with different keys, but identical inputs. It is still reversible but no longer has guaranteed block uniqueness, and you get to use the primitive you already have (at half speed). And while block uniqueness is very important in CTR mode, it is not in dual CTR, because the location of duplicates is key dependent and pseudorandom, just like the block cipher output. $CTR_{k1}(nonce+counter) oplus CTR_{k2}(nonce+counter)$
$endgroup$
– Richie Frame
Jan 28 at 10:11
$begingroup$
Combination of two stream ciphers may offer some further insight...
$endgroup$
– Paul Uszak
Jan 28 at 22:18
add a comment |
$begingroup$
Because a block cipher is a PRP and thus bijective, the fact that the input in CTR mode never repeats means that each block of keystream will be unique. This creates a distinguisher from random data following the birthday bound if enough data is encrypted even before the counter repeats, especially if the block size is too small. Stream ciphers like ChaCha20 avoid this issue by feeding a counter into a PRF instead of a PRP, meaning blocks of keystream will repeat according to the birthday bound.
Is it feasible to mitigate this problem with a PRP by feeding the nonce and counter through a very fast and deterministic hashing function first? Because the input to the block cipher is not secret in CTR mode, it would not need to be a secure hash function. All it would need to do is admit collisions due to the birthday bound, allowing for a repeating block in the keystream after roughly $2^{n/2}$ blocks.
Is this correct? If so, what is the fastest hash function which has the required properties?
ctr distinguisher
asked Jan 28 at 4:03
forestforest
4,55811743
$endgroup$
Because a block cipher is a PRP and thus bijective, the fact that the input in CTR mode never repeats means that each block of keystream will be unique. This creates a distinguisher from random data following the birthday bound if enough data is encrypted even before the counter repeats, especially if the block size is too small. Stream ciphers like ChaCha20 avoid this issue by feeding a counter into a PRF instead of a PRP, meaning blocks of keystream will repeat according to the birthday bound.
Is it feasible to mitigate this problem with a PRP by feeding the nonce and counter through a very fast and deterministic hashing function first? Because the input to the block cipher is not secret in CTR mode, it would not need to be a secure hash function. All it would need to do is admit collisions due to the birthday bound, allowing for a repeating block in the keystream after roughly $2^{n/2}$ blocks.
Is this correct? If so, what is the fastest hash function which has the required properties?
ctr distinguisher
ctr distinguisher
asked Jan 28 at 4:03
forestforest
4,55811743
asked Jan 28 at 4:03
forestforest
4,55811743
asked Jan 28 at 4:03
forestforest
4,55811743
asked Jan 28 at 4:03
forestforest
4,55811743
asked Jan 28 at 4:03
forestforest
4,55811743
4,55811743
2
$begingroup$
I think it would need to be a secure hash function, otherwise we could force it to generate identical key streams at will.
$endgroup$
– Ella Rose♦
Jan 28 at 6:01
1
$begingroup$
If you want to use AES or a typical block cipher, the solution to this problem is dual CTR streams with different keys, but identical inputs. It is still reversible but no longer has guaranteed block uniqueness, and you get to use the primitive you already have (at half speed). And while block uniqueness is very important in CTR mode, it is not in dual CTR, because the location of duplicates is key dependent and pseudorandom, just like the block cipher output. $CTR_{k1}(nonce+counter) oplus CTR_{k2}(nonce+counter)$
$endgroup$
– Richie Frame
Jan 28 at 10:11
$begingroup$
Combination of two stream ciphers may offer some further insight...
$endgroup$
– Paul Uszak
Jan 28 at 22:18
add a comment |
2
$begingroup$
I think it would need to be a secure hash function, otherwise we could force it to generate identical key streams at will.
$endgroup$
– Ella Rose♦
Jan 28 at 6:01
1
$begingroup$
If you want to use AES or a typical block cipher, the solution to this problem is dual CTR streams with different keys, but identical inputs. It is still reversible but no longer has guaranteed block uniqueness, and you get to use the primitive you already have (at half speed). And while block uniqueness is very important in CTR mode, it is not in dual CTR, because the location of duplicates is key dependent and pseudorandom, just like the block cipher output. $CTR_{k1}(nonce+counter) oplus CTR_{k2}(nonce+counter)$
$endgroup$
– Richie Frame
Jan 28 at 10:11
$begingroup$
Combination of two stream ciphers may offer some further insight...
$endgroup$
– Paul Uszak
Jan 28 at 22:18
2
2
$begingroup$
I think it would need to be a secure hash function, otherwise we could force it to generate identical key streams at will.
$endgroup$
– Ella Rose♦
Jan 28 at 6:01
$begingroup$
I think it would need to be a secure hash function, otherwise we could force it to generate identical key streams at will.
$endgroup$
– Ella Rose♦
Jan 28 at 6:01
1
1
$begingroup$
If you want to use AES or a typical block cipher, the solution to this problem is dual CTR streams with different keys, but identical inputs. It is still reversible but no longer has guaranteed block uniqueness, and you get to use the primitive you already have (at half speed). And while block uniqueness is very important in CTR mode, it is not in dual CTR, because the location of duplicates is key dependent and pseudorandom, just like the block cipher output. $CTR_{k1}(nonce+counter) oplus CTR_{k2}(nonce+counter)$
$endgroup$
– Richie Frame
Jan 28 at 10:11
$begingroup$
If you want to use AES or a typical block cipher, the solution to this problem is dual CTR streams with different keys, but identical inputs. It is still reversible but no longer has guaranteed block uniqueness, and you get to use the primitive you already have (at half speed). And while block uniqueness is very important in CTR mode, it is not in dual CTR, because the location of duplicates is key dependent and pseudorandom, just like the block cipher output. $CTR_{k1}(nonce+counter) oplus CTR_{k2}(nonce+counter)$
$endgroup$
– Richie Frame
Jan 28 at 10:11
$begingroup$
Combination of two stream ciphers may offer some further insight...
$endgroup$
– Paul Uszak
Jan 28 at 22:18
$begingroup$
Combination of two stream ciphers may offer some further insight...
$endgroup$
– Paul Uszak
Jan 28 at 22:18
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
I'm reading the question as generating a keystream per: $S_igets E_K(F(mathrm{IV},i))$ where $F$ is a public function built from a hash function; for incremental index $i$ starting from $0$ and public random $mathrm{IV}$, with $F$ having a sizable collision rate when $i$ varies; and for $E$ a block cipher with secret key $K$.
That is quite insecure: the location of the collisions, that is values of $i$, $j$ with $ine j$ and $F(mathrm{IV},i)=F(mathrm{IV},j)$, can be found by an adversary from the public $mathrm{IV}$. And then knowledge that $K_i=K_j$ can be used to mount an attack allowing decryption of some plaintext fragment from partially known plaintext.
answered Jan 28 at 7:05
fgrieufgrieu
81.8k7178349
$endgroup$
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "281"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: false,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66836%2fhashing-a-counter-to-prevent-distinguishers-in-ctr-mode%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
I'm reading the question as generating a keystream per: $S_igets E_K(F(mathrm{IV},i))$ where $F$ is a public function built from a hash function; for incremental index $i$ starting from $0$ and public random $mathrm{IV}$, with $F$ having a sizable collision rate when $i$ varies; and for $E$ a block cipher with secret key $K$.
That is quite insecure: the location of the collisions, that is values of $i$, $j$ with $ine j$ and $F(mathrm{IV},i)=F(mathrm{IV},j)$, can be found by an adversary from the public $mathrm{IV}$. And then knowledge that $K_i=K_j$ can be used to mount an attack allowing decryption of some plaintext fragment from partially known plaintext.
answered Jan 28 at 7:05
fgrieufgrieu
81.8k7178349
$endgroup$
add a comment |
$begingroup$
I'm reading the question as generating a keystream per: $S_igets E_K(F(mathrm{IV},i))$ where $F$ is a public function built from a hash function; for incremental index $i$ starting from $0$ and public random $mathrm{IV}$, with $F$ having a sizable collision rate when $i$ varies; and for $E$ a block cipher with secret key $K$.
That is quite insecure: the location of the collisions, that is values of $i$, $j$ with $ine j$ and $F(mathrm{IV},i)=F(mathrm{IV},j)$, can be found by an adversary from the public $mathrm{IV}$. And then knowledge that $K_i=K_j$ can be used to mount an attack allowing decryption of some plaintext fragment from partially known plaintext.
answered Jan 28 at 7:05
fgrieufgrieu
81.8k7178349
$endgroup$
add a comment |
$begingroup$
I'm reading the question as generating a keystream per: $S_igets E_K(F(mathrm{IV},i))$ where $F$ is a public function built from a hash function; for incremental index $i$ starting from $0$ and public random $mathrm{IV}$, with $F$ having a sizable collision rate when $i$ varies; and for $E$ a block cipher with secret key $K$.
That is quite insecure: the location of the collisions, that is values of $i$, $j$ with $ine j$ and $F(mathrm{IV},i)=F(mathrm{IV},j)$, can be found by an adversary from the public $mathrm{IV}$. And then knowledge that $K_i=K_j$ can be used to mount an attack allowing decryption of some plaintext fragment from partially known plaintext.
answered Jan 28 at 7:05
fgrieufgrieu
81.8k7178349
$endgroup$
I'm reading the question as generating a keystream per: $S_igets E_K(F(mathrm{IV},i))$ where $F$ is a public function built from a hash function; for incremental index $i$ starting from $0$ and public random $mathrm{IV}$, with $F$ having a sizable collision rate when $i$ varies; and for $E$ a block cipher with secret key $K$.
That is quite insecure: the location of the collisions, that is values of $i$, $j$ with $ine j$ and $F(mathrm{IV},i)=F(mathrm{IV},j)$, can be found by an adversary from the public $mathrm{IV}$. And then knowledge that $K_i=K_j$ can be used to mount an attack allowing decryption of some plaintext fragment from partially known plaintext.
answered Jan 28 at 7:05
fgrieufgrieu
81.8k7178349
edited Jan 29 at 16:06
answered Jan 28 at 7:05
fgrieufgrieu
81.8k7178349
answered Jan 28 at 7:05
fgrieufgrieu
81.8k7178349
answered Jan 28 at 7:05
fgrieufgrieu
81.8k7178349
81.8k7178349
add a comment |
add a comment |
Thanks for contributing an answer to Cryptography Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcrypto.stackexchange.com%2fquestions%2f66836%2fhashing-a-counter-to-prevent-distinguishers-in-ctr-mode%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
2
$begingroup$
I think it would need to be a secure hash function, otherwise we could force it to generate identical key streams at will.
$endgroup$
– Ella Rose♦
Jan 28 at 6:01
1
$begingroup$
If you want to use AES or a typical block cipher, the solution to this problem is dual CTR streams with different keys, but identical inputs. It is still reversible but no longer has guaranteed block uniqueness, and you get to use the primitive you already have (at half speed). And while block uniqueness is very important in CTR mode, it is not in dual CTR, because the location of duplicates is key dependent and pseudorandom, just like the block cipher output. $CTR_{k1}(nonce+counter) oplus CTR_{k2}(nonce+counter)$
$endgroup$
– Richie Frame
Jan 28 at 10:11
$begingroup$
Combination of two stream ciphers may offer some further insight...
$endgroup$
– Paul Uszak
Jan 28 at 22:18