8 ms·
A cryptographic hash function H can be used for encryption though, by mimicking a one-time pad: Pick a random integer k, concatenate it with a secret s, hash th
by triska 5y ago
A cryptographic hash function H can be used for encryption though, by mimicking a one-time pad: Pick a random integer k, concatenate it with a secret s, hash the result obtaining H(s•k), XOR this with the plaintext yielding the ciphertext C and send the pair (k,C). Pick another integer if you need to encrypt more data.
Decryption proceeds in the same way, mutatis mutandis. This is the basic idea behind one of the best currently used ciphers, ChaCha20: It builds on a hash function.
From a regulatory and legal perspective, this means that if you want to ban strong encryption, you must ban cryptographic hash functions.
- nathias 5y agois this unbreakable like OTP?
- triska 5y agoNo, because the key stream is not random: It depends functionally on the integer which is sent in plain text, and on the shared secret. For example, if you pick the same integer twice with the same secret then the XOR of the two ciphertexts is the XOR of the two plaintexts, thus losing confidentiality.
- Karliss 5y agoNeither is OTP secure if you reuse the key. One of main properties of OTP is that an encrypted message could be decrypted to any message of same size. In case of block cyphers and message longer than one block only a fraction of all messages can be obtained. So if you had enough compute resource(and it wasn't more than atoms in universe) for brute force or weakness was found in cyphers you could find which of the potential decrypted messages makes sense and is more likely.
- smitty1e 5y ago> Neither is OTP secure if you reuse the key. I thought the OT meant "One Time". Reusing the key would take the key from singular to plural usage, no?
- Closi 5y agoAbsolutely - OTP with key reuse is not OTP!
- pdpi 5y agoYup, but it’s more useful to talk about that reuse as a bad implementation of one-time pads than it is to call it something other than OTP. In the classic sense of a small paper pad used by spies, reuse was fairly common because of the logistical problem of supplying agents with fresh pads.
- Karliss 5y agoYes, but I was explaining that no reuse requirement can be equally important for encryption schemes that don't have it included in the name. Claiming that one of them is worse than other because of number reuse even though doing so is equally wrong for both is not a good example.
- runeks 5y agoWould it be secure to encrypt a sequence of blocks by having the next integer be H(k) — such that the random integer for block number i is H applied to the original random integer (k) i times? Thus needing only an initial random integer from which all subsequent random integers are derived.
- eternalban 5y agoThe general idea is to create a PRNG using the cryptographic hash. Since these hashes generally produce far more bits than needed for scalars (64 bits), you can mix the extra bits for the next cycle of the PRNG and emit (say) 64 bits per cycle. The sequence of the PRNG output is the 'pad'.
- aliceryhl 5y agoNo. With the hash-based algorithm you can go through every possible secret key and starting integer and check whether the result looks like English text (or whatever the contents are). If your English-text check is sufficiently good (how good it has to be decreases with the length of the text), then you're only going to have a very small number of matches, and one of those will be the plain text. The above attack doesn't work on OTP because the above attack would simply yield a list of all English strings of the given length, and there would be no way to tell them apart. Obviously the above attack is infeasible because there are too many secrets to check them all in a reasonable amount of time, but to be unbreakable in the same way OTP is, you have to be robust against even attacks that take an infinite amount of time.
- akerl_ 5y agoI’m not sure what you mean by “the above attack would simply yield a list of all English strings of a given length”. To attack classic OTP, you’d brute force the keyspace. Since we’re XORing, whatever we encode the key as, it’s fundamentally being used in binary to XOR between plaintext and ciphertext. So your key is a binary blob the same length as the ciphertext. You keep trying and looking for what seems to be viable plaintext. You never get “all English strings of the given length”, because you’re not brute forcing the output, you’re brute forcing the key, which isn’t necessarily English. For the hash-based approach, you’re bruteforcing the secret used for the hash function. That keyspace can be any length, unbounded on either end by the size of the message. Likewise, you’re trying H(sk) by guessing s and k, and then XORing the message and trying to determine if it looks like what you’d expect. Your lower bound for the hash method is if the message length is shorter than the hash functions output, in which case you can cheat and literally just treat it like classic OTP, by bruteforcing possible values for H(sk) rather than guessing k and running the computation. But beyond that it’s the same dance (and if the hash function is slow, you can always fall back to brute forcing any length message the same way you would for classic OTP). In both cases, assuming a large key size puts you past computational sanity for brute forcing, but neither the hash construction nor OTP is secure against “infinite” time.
- eperdew 5y ago
- charlieyu1 5y agoI’m not even sure that OTP is secure by modern standards. Since OTP encrypts with XOR only, a man-in-the-middle can still modify the message by XOR a few bytes with constants like 0x01 to modify the message.
- DarylZero 5y agoOTP can be combined with some message authentication code, so I don't think that's a fair criticism.
- mistercow 5y agoYeah, nothing is secure if you apply it incorrectly. SSH isn't secure if you tweet your private key.
- danlugo92 5y agoBut my private key just laying there unencrypted in `~/.ssh/id_rsa` is safe for some reason?? I've never understood this.
- freeqaz 5y agoYou should encrypt your private key with a password. Then you can use ssh-agent to hold a copy of that decrypted key in-memory so that you don't have to type your password in every time you 'git push'
- deleted 5y ago[deleted]
- deleted 5y ago[deleted]
- ris 5y agoThe more classic example is probably Feistel ciphers.
- Normal_gaussian 5y agoWhich along with other block ciphers are the surprisingly hard to search solution to the problem of providing a bounded, iterable, id that doesnt leak its position of iteration. (ie, provide an n character id without duplicates and using the entire space. Useful for ids for image hosting etc.)
- deleted 5y ago[deleted]
- SAI_Peregrinus 5y agoOr just CTR mode of a hash function (which is closer to what ChaCha20 does internally, it runs a permutation in CTR mode). H(constant, key, nonce, ctr) gets a keystream block, XOR each keystream block with the corresponding plaintext (to encrypt) or ciphertext (to decrypt) block. The constant is important in ChaCha's case, it keeps the attacker-controlled portion of the block strictly less than half the total block, prevents an all-zero input, and has some asymmetry to help diffusion overall.
- axiosgunnar 5y agoInteresting post but stuff like > From a regulatory and legal perspective, this means that if you want to ban strong encryption, you must ban cryptographic hash functions. aka „you can't ban math! ha!“ is just a nerd dream. The government would simply ban Whatsapp etc from implementing E2E encryption, something that is completely feasible, and 99% of the population‘s communications would be unencrypted.
- ThePhysicist 5y agoYep we use that to e.g. construct stream ciphers for structure-preserving pseudonymization. Security proof is quite simple as well if you can assume the hash function is secure. No one would use this for encryption though as it's quite slow compared to a modern stream cipher. We use it because there's (to my knowledge) no standardized stream cipher that provides output feedback mode (OFB) out-of-the-box.
- ignoramous 5y ago> ...structure-preserving pseudonymization Can you write about this a bit more, please (what does it mean)? Is it comparable to Tokenization (typically used to hide sensitive-date like credit card details, for example) [0], or to Homomorphic encryption [1]? [0] https://en.wikipedia.org/wiki/Tokenization_(data_security) https://en.wikipedia.org/wiki/Tokenization_(data_security) [1] https://people.csail.mit.edu/vinodv/FHE/FHE-refs.html https://people.csail.mit.edu/vinodv/FHE/FHE-refs.html
- ThePhysicist 5y agoTokenization typically means that a third party keeps an association table, though it is possible to generate tokens cryptographically. Homomorphic encryption is something different again, though you could call this structure-preserving pseudonymization homomorphic as it preserves certain structural properties of the input data. It does not provide the same security guarantees as FHE though as the structure preservation weakens the encryption. For pseudonymization this is a tradeoff that can be worthwhile though.
- tptacek 5y agoPretty much everybody uses this for encryption; the most popular stream cipher (qua stream cipher) in the world is Salsa20/ChaCha20, which is simply a keyed hash function run in counter mode.
- 0xdeadb00f 5y ago> (to my knowledge) no standardized stream cipher that provides output feedback mode (OFB) out-of-the-box. I wasn't aware stream ciphers typically had different modes of operation like block ciphers did. Could you expand on this? I'm kind of interested.
- deleted 5y ago[deleted]
- freeqaz 5y agoYou nerd sniped me with this. At least now I could implement ChaCha from memory... so thanks for that! It's cool to see how simple it is. It's a lot more intuitive than other ciphers are!
- sangel 5y agoI think this requires assuming H is a random oracle, no? Suppose H(s||k) is a collision-resistant hash function. Let's build another CRHF from H as follows: H'(s || k) = H(s || k) || last-bit-of-k. Now let's instantiate the cryptosystem you proposed with H'. Suppose m is message and that it is of length equal to the length of the bitstring produced by H'. We have C = H'(s||k) XOR m. The ciphertext is thus: (k, C). What can an attacker do? Well, the attacker can XOR the last bit of C with the last bit of k and get the last bit of m. This is already enough to violate semantic security.
- staticassertion 5y agoI don't think they're proposing their implementation is sufficient. ChaCha has a nonce for a reason.
- matthewdgreen 5y agoYou're correct that collision resistance is not sufficient for the above construction to be secure, but you don't need to assume H() is a random oracle. You could instead model H(k||s) as a pseudorandom function with k as the key. And of course, if you don't trust existing functions to be directly pseudorandom, then a PRF can be built from one-way functions: so pre-image resistance is sufficient. (The remaining question is how to get there from CR alone.)
- sammyq 5y agoWhy is k an integer, could it be any arbitrary string? Also does k need have some special properties such as primality?