Does secure hashing imply secure symmetric encryption?Should we MAC-then-encrypt or encrypt-then-MAC?Is SHA-256 secure as a CTR block cipher?Why does second pre-image resistance imply pre-image resistanceCan we use a sort of “hash” function in CTR mode instead of a block cipher?Implementing 5 modes of operation with a hash functionOverview of relations between cryptographic primitives?A fast non-cryptographic hash function that is “strong enough”?HMAC versus encrypted hashNeed for secure hash function for a bloom filterHashing with (some sort of) Public and Private keys/salt/nonceWhat type of encryption is this homebrew “encyption algorithm”? $$
How to add some symbol (or just add newline) if the numbers in the text are not continuous
What is the converted mana cost of land cards?
Declaring 2 (or even multi-) dimensional std::arrays elegantly
Punishment in pacifist society
Why are Latin and Sanskrit called dead languages?
Updating multiple vector points at once with vertex editor in QGIS?
What percentage of the mass/energy of the universe is in the form of electromagnetic waves?
How to use multiple criteria for -find
Are there photos of the Apollo LM showing disturbed lunar soil resulting from descent engine exhaust?
Is torque as fundamental a concept as force?
Are there any writings by blinded and/or exiled Byzantine emperors?
Solve this icositetragram
What is the most likely cause of short, quick, and useless reviews?
Are manifolds admitting a circle foliation covered by manifolds with a (non-trivial) circle action?
Design of 50 ohms RF trace for 2.4GHz...Double layer FR-4 PCB
Function of the separated, individual solar cells on Telstar 1 and 2? Why were they "special"?
How to run a command 1 out of N times in Bash
How to disambiguate between various meditation practices?
To which country did MiGs in Top Gun belong?
properties that real numbers hold but complex numbers does not
Initializing a std::array with a constant value
Why do we need explainable AI?
Strange LockTime values in Electrum transactions?
How do we know if a dialogue sounds unnatural without asking for feedback?
Does secure hashing imply secure symmetric encryption?
Should we MAC-then-encrypt or encrypt-then-MAC?Is SHA-256 secure as a CTR block cipher?Why does second pre-image resistance imply pre-image resistanceCan we use a sort of “hash” function in CTR mode instead of a block cipher?Implementing 5 modes of operation with a hash functionOverview of relations between cryptographic primitives?A fast non-cryptographic hash function that is “strong enough”?HMAC versus encrypted hashNeed for secure hash function for a bloom filterHashing with (some sort of) Public and Private keys/salt/nonceWhat type of encryption is this homebrew “encyption algorithm”? $$
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty margin-bottom:0;
$begingroup$
I was wondering if the mere existence of a (by some definition) secure cryptographic hash function immediately implies an equally secure symmetric encryption scheme.
By my understanding, one could to the following given such a function:
Encryption: Using a shared secret key, we calculate the hash of the key concatenated with the first character of the text, the key concatenated with the first two characters of the text, etc. (every prefix), giving the same number of hashes as characters in the input. This would inflate the size somewhat, but only by a small constant factor.
Decryption: Knowing the key, we can calculate the hash of our key concatenated with every character from the alphabet, and once we find the one that matches the first hash, we can repeat the process with the next hash, until the entire text is found. This would require some more hash calculations than encryption, but only a constant factor, the size of the alphabet (this could be reduced by a bit for bit scheme instead of a character by character scheme).
As far as I know, this incremental series of slightly different inputs to a hash function should not cause the resulting hashes to be predictable, and neither should it leak information about the key.
One weakness I can see is that messages that start out the same and are using the same key will have the beginning of the hash sequence equal up to the point of divergence, but this can easily be mitigated by prefixing the message with a unique ID of some sort, perhaps just a hash of the message itself.
The above is the reasoning that made me think that "hash function" ⇒ "symmetric encryption".
Is there some fundamental principle or scheme that proves/disproves that this is the case?
encryption hash
New contributor
$endgroup$
add a comment |
$begingroup$
I was wondering if the mere existence of a (by some definition) secure cryptographic hash function immediately implies an equally secure symmetric encryption scheme.
By my understanding, one could to the following given such a function:
Encryption: Using a shared secret key, we calculate the hash of the key concatenated with the first character of the text, the key concatenated with the first two characters of the text, etc. (every prefix), giving the same number of hashes as characters in the input. This would inflate the size somewhat, but only by a small constant factor.
Decryption: Knowing the key, we can calculate the hash of our key concatenated with every character from the alphabet, and once we find the one that matches the first hash, we can repeat the process with the next hash, until the entire text is found. This would require some more hash calculations than encryption, but only a constant factor, the size of the alphabet (this could be reduced by a bit for bit scheme instead of a character by character scheme).
As far as I know, this incremental series of slightly different inputs to a hash function should not cause the resulting hashes to be predictable, and neither should it leak information about the key.
One weakness I can see is that messages that start out the same and are using the same key will have the beginning of the hash sequence equal up to the point of divergence, but this can easily be mitigated by prefixing the message with a unique ID of some sort, perhaps just a hash of the message itself.
The above is the reasoning that made me think that "hash function" ⇒ "symmetric encryption".
Is there some fundamental principle or scheme that proves/disproves that this is the case?
encryption hash
New contributor
$endgroup$
$begingroup$
With a hash function, you can build a cipher with CTR mode. See Can we use a sort of “hash” function in CTR mode instead of a block cipher? and Is SHA-256 secure as a CTR block cipher?
$endgroup$
– kelalaka
10 hours ago
$begingroup$
Also see crypto.stackexchange.com/questions/29232/…
$endgroup$
– Richie Frame
5 hours ago
$begingroup$
Just to point out that the answers given are "yes" to the possibility of a hash based encryption scheme, but not "yes" to the particular encryption scheme you propose. That falls under the general advice of "don't write your own cipher"
$endgroup$
– Josiah
2 hours ago
add a comment |
$begingroup$
I was wondering if the mere existence of a (by some definition) secure cryptographic hash function immediately implies an equally secure symmetric encryption scheme.
By my understanding, one could to the following given such a function:
Encryption: Using a shared secret key, we calculate the hash of the key concatenated with the first character of the text, the key concatenated with the first two characters of the text, etc. (every prefix), giving the same number of hashes as characters in the input. This would inflate the size somewhat, but only by a small constant factor.
Decryption: Knowing the key, we can calculate the hash of our key concatenated with every character from the alphabet, and once we find the one that matches the first hash, we can repeat the process with the next hash, until the entire text is found. This would require some more hash calculations than encryption, but only a constant factor, the size of the alphabet (this could be reduced by a bit for bit scheme instead of a character by character scheme).
As far as I know, this incremental series of slightly different inputs to a hash function should not cause the resulting hashes to be predictable, and neither should it leak information about the key.
One weakness I can see is that messages that start out the same and are using the same key will have the beginning of the hash sequence equal up to the point of divergence, but this can easily be mitigated by prefixing the message with a unique ID of some sort, perhaps just a hash of the message itself.
The above is the reasoning that made me think that "hash function" ⇒ "symmetric encryption".
Is there some fundamental principle or scheme that proves/disproves that this is the case?
encryption hash
New contributor
$endgroup$
I was wondering if the mere existence of a (by some definition) secure cryptographic hash function immediately implies an equally secure symmetric encryption scheme.
By my understanding, one could to the following given such a function:
Encryption: Using a shared secret key, we calculate the hash of the key concatenated with the first character of the text, the key concatenated with the first two characters of the text, etc. (every prefix), giving the same number of hashes as characters in the input. This would inflate the size somewhat, but only by a small constant factor.
Decryption: Knowing the key, we can calculate the hash of our key concatenated with every character from the alphabet, and once we find the one that matches the first hash, we can repeat the process with the next hash, until the entire text is found. This would require some more hash calculations than encryption, but only a constant factor, the size of the alphabet (this could be reduced by a bit for bit scheme instead of a character by character scheme).
As far as I know, this incremental series of slightly different inputs to a hash function should not cause the resulting hashes to be predictable, and neither should it leak information about the key.
One weakness I can see is that messages that start out the same and are using the same key will have the beginning of the hash sequence equal up to the point of divergence, but this can easily be mitigated by prefixing the message with a unique ID of some sort, perhaps just a hash of the message itself.
The above is the reasoning that made me think that "hash function" ⇒ "symmetric encryption".
Is there some fundamental principle or scheme that proves/disproves that this is the case?
encryption hash
encryption hash
New contributor
New contributor
edited 9 hours ago
Maeher
4,2981 gold badge22 silver badges33 bronze badges
4,2981 gold badge22 silver badges33 bronze badges
New contributor
asked 10 hours ago
HohmannfanHohmannfan
1284 bronze badges
1284 bronze badges
New contributor
New contributor
$begingroup$
With a hash function, you can build a cipher with CTR mode. See Can we use a sort of “hash” function in CTR mode instead of a block cipher? and Is SHA-256 secure as a CTR block cipher?
$endgroup$
– kelalaka
10 hours ago
$begingroup$
Also see crypto.stackexchange.com/questions/29232/…
$endgroup$
– Richie Frame
5 hours ago
$begingroup$
Just to point out that the answers given are "yes" to the possibility of a hash based encryption scheme, but not "yes" to the particular encryption scheme you propose. That falls under the general advice of "don't write your own cipher"
$endgroup$
– Josiah
2 hours ago
add a comment |
$begingroup$
With a hash function, you can build a cipher with CTR mode. See Can we use a sort of “hash” function in CTR mode instead of a block cipher? and Is SHA-256 secure as a CTR block cipher?
$endgroup$
– kelalaka
10 hours ago
$begingroup$
Also see crypto.stackexchange.com/questions/29232/…
$endgroup$
– Richie Frame
5 hours ago
$begingroup$
Just to point out that the answers given are "yes" to the possibility of a hash based encryption scheme, but not "yes" to the particular encryption scheme you propose. That falls under the general advice of "don't write your own cipher"
$endgroup$
– Josiah
2 hours ago
$begingroup$
With a hash function, you can build a cipher with CTR mode. See Can we use a sort of “hash” function in CTR mode instead of a block cipher? and Is SHA-256 secure as a CTR block cipher?
$endgroup$
– kelalaka
10 hours ago
$begingroup$
With a hash function, you can build a cipher with CTR mode. See Can we use a sort of “hash” function in CTR mode instead of a block cipher? and Is SHA-256 secure as a CTR block cipher?
$endgroup$
– kelalaka
10 hours ago
$begingroup$
Also see crypto.stackexchange.com/questions/29232/…
$endgroup$
– Richie Frame
5 hours ago
$begingroup$
Also see crypto.stackexchange.com/questions/29232/…
$endgroup$
– Richie Frame
5 hours ago
$begingroup$
Just to point out that the answers given are "yes" to the possibility of a hash based encryption scheme, but not "yes" to the particular encryption scheme you propose. That falls under the general advice of "don't write your own cipher"
$endgroup$
– Josiah
2 hours ago
$begingroup$
Just to point out that the answers given are "yes" to the possibility of a hash based encryption scheme, but not "yes" to the particular encryption scheme you propose. That falls under the general advice of "don't write your own cipher"
$endgroup$
– Josiah
2 hours ago
add a comment |
2 Answers
2
active
oldest
votes
$begingroup$
The existence of a family of collision resistant compressing functions does indeed imply the existence of CPA secure, CCA secure and even authenticated encryption. This follows from several classic results in cryptography.
A family of collision resistant compressing functions is also a family of one-way functions.
By the seminal work of Håstad, Impagliazzo, Levin, and Luby (commonly referred to as HILL) "A Pseudorandom Generator from any One-way Function" [HILL99] any one-way function implies the existence of a pseudorandom generator (PRG).
The equally important work of Goldreich, Goldwasser, and Micali "How to construct random functions" [GGM86] had already established that a PRG was sufficient to construct a pseudorandom function (PRF) via the so-called GGM construction.
Once you have PRFs, you have two things. First the classic example of a CPA secure encryption scheme where the ciphertext is $(r,F_k(r)oplus m)$ for a uniformly chosen $r$. Second, the PRF itself is also a deterministic message authentication code with canonical verification. Using the encrypt-then-mac construction we can then construct a secure authenticated encryption scheme.
$endgroup$
add a comment |
$begingroup$
Theoretically-speaking, yes: (collision-resistant) hash functions imply* one-way functions (OWF), and therefore they also can be used to build symmetric primitives using the chain of reductions from OWF to PRGs (pseudo-random generators) to PRFs (pseudo-random functions) and finally to PRPs (pseudo-random permutations) or block ciphers (cf. this answer).
*Refer, for example, to this paper for a proof.
$endgroup$
add a comment |
Your Answer
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
);
);
Hohmannfan is a new contributor. Be nice, and check out our Code of Conduct.
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%2f72986%2fdoes-secure-hashing-imply-secure-symmetric-encryption%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The existence of a family of collision resistant compressing functions does indeed imply the existence of CPA secure, CCA secure and even authenticated encryption. This follows from several classic results in cryptography.
A family of collision resistant compressing functions is also a family of one-way functions.
By the seminal work of Håstad, Impagliazzo, Levin, and Luby (commonly referred to as HILL) "A Pseudorandom Generator from any One-way Function" [HILL99] any one-way function implies the existence of a pseudorandom generator (PRG).
The equally important work of Goldreich, Goldwasser, and Micali "How to construct random functions" [GGM86] had already established that a PRG was sufficient to construct a pseudorandom function (PRF) via the so-called GGM construction.
Once you have PRFs, you have two things. First the classic example of a CPA secure encryption scheme where the ciphertext is $(r,F_k(r)oplus m)$ for a uniformly chosen $r$. Second, the PRF itself is also a deterministic message authentication code with canonical verification. Using the encrypt-then-mac construction we can then construct a secure authenticated encryption scheme.
$endgroup$
add a comment |
$begingroup$
The existence of a family of collision resistant compressing functions does indeed imply the existence of CPA secure, CCA secure and even authenticated encryption. This follows from several classic results in cryptography.
A family of collision resistant compressing functions is also a family of one-way functions.
By the seminal work of Håstad, Impagliazzo, Levin, and Luby (commonly referred to as HILL) "A Pseudorandom Generator from any One-way Function" [HILL99] any one-way function implies the existence of a pseudorandom generator (PRG).
The equally important work of Goldreich, Goldwasser, and Micali "How to construct random functions" [GGM86] had already established that a PRG was sufficient to construct a pseudorandom function (PRF) via the so-called GGM construction.
Once you have PRFs, you have two things. First the classic example of a CPA secure encryption scheme where the ciphertext is $(r,F_k(r)oplus m)$ for a uniformly chosen $r$. Second, the PRF itself is also a deterministic message authentication code with canonical verification. Using the encrypt-then-mac construction we can then construct a secure authenticated encryption scheme.
$endgroup$
add a comment |
$begingroup$
The existence of a family of collision resistant compressing functions does indeed imply the existence of CPA secure, CCA secure and even authenticated encryption. This follows from several classic results in cryptography.
A family of collision resistant compressing functions is also a family of one-way functions.
By the seminal work of Håstad, Impagliazzo, Levin, and Luby (commonly referred to as HILL) "A Pseudorandom Generator from any One-way Function" [HILL99] any one-way function implies the existence of a pseudorandom generator (PRG).
The equally important work of Goldreich, Goldwasser, and Micali "How to construct random functions" [GGM86] had already established that a PRG was sufficient to construct a pseudorandom function (PRF) via the so-called GGM construction.
Once you have PRFs, you have two things. First the classic example of a CPA secure encryption scheme where the ciphertext is $(r,F_k(r)oplus m)$ for a uniformly chosen $r$. Second, the PRF itself is also a deterministic message authentication code with canonical verification. Using the encrypt-then-mac construction we can then construct a secure authenticated encryption scheme.
$endgroup$
The existence of a family of collision resistant compressing functions does indeed imply the existence of CPA secure, CCA secure and even authenticated encryption. This follows from several classic results in cryptography.
A family of collision resistant compressing functions is also a family of one-way functions.
By the seminal work of Håstad, Impagliazzo, Levin, and Luby (commonly referred to as HILL) "A Pseudorandom Generator from any One-way Function" [HILL99] any one-way function implies the existence of a pseudorandom generator (PRG).
The equally important work of Goldreich, Goldwasser, and Micali "How to construct random functions" [GGM86] had already established that a PRG was sufficient to construct a pseudorandom function (PRF) via the so-called GGM construction.
Once you have PRFs, you have two things. First the classic example of a CPA secure encryption scheme where the ciphertext is $(r,F_k(r)oplus m)$ for a uniformly chosen $r$. Second, the PRF itself is also a deterministic message authentication code with canonical verification. Using the encrypt-then-mac construction we can then construct a secure authenticated encryption scheme.
answered 9 hours ago
MaeherMaeher
4,2981 gold badge22 silver badges33 bronze badges
4,2981 gold badge22 silver badges33 bronze badges
add a comment |
add a comment |
$begingroup$
Theoretically-speaking, yes: (collision-resistant) hash functions imply* one-way functions (OWF), and therefore they also can be used to build symmetric primitives using the chain of reductions from OWF to PRGs (pseudo-random generators) to PRFs (pseudo-random functions) and finally to PRPs (pseudo-random permutations) or block ciphers (cf. this answer).
*Refer, for example, to this paper for a proof.
$endgroup$
add a comment |
$begingroup$
Theoretically-speaking, yes: (collision-resistant) hash functions imply* one-way functions (OWF), and therefore they also can be used to build symmetric primitives using the chain of reductions from OWF to PRGs (pseudo-random generators) to PRFs (pseudo-random functions) and finally to PRPs (pseudo-random permutations) or block ciphers (cf. this answer).
*Refer, for example, to this paper for a proof.
$endgroup$
add a comment |
$begingroup$
Theoretically-speaking, yes: (collision-resistant) hash functions imply* one-way functions (OWF), and therefore they also can be used to build symmetric primitives using the chain of reductions from OWF to PRGs (pseudo-random generators) to PRFs (pseudo-random functions) and finally to PRPs (pseudo-random permutations) or block ciphers (cf. this answer).
*Refer, for example, to this paper for a proof.
$endgroup$
Theoretically-speaking, yes: (collision-resistant) hash functions imply* one-way functions (OWF), and therefore they also can be used to build symmetric primitives using the chain of reductions from OWF to PRGs (pseudo-random generators) to PRFs (pseudo-random functions) and finally to PRPs (pseudo-random permutations) or block ciphers (cf. this answer).
*Refer, for example, to this paper for a proof.
answered 10 hours ago
Occams_TrimmerOccams_Trimmer
2,0741 gold badge11 silver badges21 bronze badges
2,0741 gold badge11 silver badges21 bronze badges
add a comment |
add a comment |
Hohmannfan is a new contributor. Be nice, and check out our Code of Conduct.
Hohmannfan is a new contributor. Be nice, and check out our Code of Conduct.
Hohmannfan is a new contributor. Be nice, and check out our Code of Conduct.
Hohmannfan is a new contributor. Be nice, and check out our Code of Conduct.
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%2f72986%2fdoes-secure-hashing-imply-secure-symmetric-encryption%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
$begingroup$
With a hash function, you can build a cipher with CTR mode. See Can we use a sort of “hash” function in CTR mode instead of a block cipher? and Is SHA-256 secure as a CTR block cipher?
$endgroup$
– kelalaka
10 hours ago
$begingroup$
Also see crypto.stackexchange.com/questions/29232/…
$endgroup$
– Richie Frame
5 hours ago
$begingroup$
Just to point out that the answers given are "yes" to the possibility of a hash based encryption scheme, but not "yes" to the particular encryption scheme you propose. That falls under the general advice of "don't write your own cipher"
$endgroup$
– Josiah
2 hours ago