Hashing is not encryption
eric.mann.blog
eric.mann.blog
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.
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.
I thought the OT meant "One Time". Reusing the key would take the key from singular to plural usage, no?
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.
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.
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.
If your key for OTP is uniform random bits without any additional encoding, and of the same length as the plaintext, then won't you enumerate all possible messages of the given length? E.g., "abcdef" and "123456" are indistinguishable when encrypted without knowing the key because there exist keys that map each string to the same ciphertext.
You misunderstand me. If you go through all possible keys and try to decrypt with each key, then for every possible input (of the same length), there will be one of the keys that yield that input. Hence, by going through all keys, you will hit all possible inputs, which includes all strings written in 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.
My assumption is that the secret for the hash function input is of fixed length and shorter than the plaintext. This is not an unreasonable assumption — pretty much all existing hash functions satisfy that assumption unless the plaintext is really short.
> 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.
These algorithms are certainly not computationally feasible, but OTP really is secure against unbounded computation in a way that the hash-based OTP is not. Knowing the ciphertext from an OTP gives literally no information about the original plaintext besides its length.
On the other hand, knowing the ciphertext of the hash-based algorithm must yield some information about the plaintext. To see why, consider an example:
1. The hash function takes as input a secret/integer of a combined 1024 bits. 2. The plaintext and ciphertext is 1000000 bits long.
Here, if you try all possible inputs to the hash function and try to decrypt the ciphertext using each one, then you're going to get a list with 2^1024 possible plaintexts. However, there are 2^1000000 possibilities for what the plaintext could be, so there must be some plaintexts missing from the list. Any plaintext that is missing from the list cannot possibly be the original plaintext.
(ie, provide an n character id without duplicates and using the entire space. Useful for ids for image hosting etc.)
I've never understood this.
But there are also niche situations where an attacker has read permissions for files but not memory. It's atypical, but in cases where you have 'confused deputies' it happens - for example, if I have a service that attempts to safely broker reads to files but that service has a logic bug where a client can trick it into reading sensitive files.
The classic example of this is a path traversal in a web service.
Also, while there's no boundary, attackers are a lot happier reading files than memory. They're only human.
In general I find that, when you can, you should just encrypt your data. It can protect you in some surprising ways.
e.g. using my tinc VPN mesh
grep keys /etc/ssh/sshd_config
AuthorizedKeysFile /etc/ssh/keys/%u
from="192.168.0.0/16,10.15.10.2" ssh-rsa AAAAB3NzaC1yc2EAAAADAQABAAABAQDDlyvd+LAveSiIIgQW3Y+aWsb8bTu70tgXQjoWMrMAbKt1/sDoE/w2qqLBSqLjJmA46zKqwgZhnO8hkZjpizjb909fNYrgyNOsRcHOvumanORUGjcumxi5fklqNZCXC1rehX4z+tnVzygtDNQcqlmyy1ElBM+SxKS+YIrOymPOU6bc5V1sildq5cVUSuEHcLggOadCj6azbiR1J46D6UYxAaKYjq2OloLZXRhvSYrmVeH+PNKiShgYBu4TfCg4UoJKZsHTaeS2akZAQTqcjy7bB8HRWGXYEMKAKA95w8MTqaWlIoMKBuOJnd8+wRXrZKnSsTQmQQZg0rggO6GC8ufT leaked_on_purpose
AllowUsers root@192.168.*.*Yes one can disable any/all forms of authentication. At that point it might be worth shutting down the SSH daemon to save a few MB of ram. If you mean permit null passwords that can be enabled too.
> At that point it might be worth shutting down the SSH daemon
Could be useful with ForceCommand. Sometimes you really only want to authenticate the server -- like with HTTPS.
Match Group sftpusers
PubkeyAuthentication yes
PasswordAuthentication yes
PermitEmptyPasswords yes
GatewayPorts no
ChrootDirectory /data/sftphome/%u
ForceCommand internal-sftp -l DEBUG1 -f AUTHPRIV -P symlink,hardlink,fsync,rmdir,remove,rename,posix-rename
AllowTcpForwarding no
AllowAgentForwarding noWhen I connect without a `-i` parameter the SSH client attempts to authenticate with all my keys, succeeding with none, then succeeds with authentication type `none`. When I specify -i `/dev/null` the logs are confusing as to what's happening:
$ ssh -i /dev/null -v serveradmin@50.116.13.30 2>&1 | egrep -ie 'auth|attempt'
debug1: Authenticating to 50.116.13.30:22 as 'serveradmin'
debug1: Will attempt key: /dev/null explicit
debug1: Authentication succeeded (none).
Authenticated to 50.116.13.30 ([50.116.13.30]:22).
A null password is using none [1] which is a reserved term and has specific implications. In this case of passwords, none will succeed since I enabled null passwords and that account has no password set. So none is matching in the PasswordAuthentication option.
/etc/passwd serveradmin:x:22218:5000::/data/sftphome/serveradmin:/bin/false
/etc/shadow serveradmin::18955:0:99999:7:::
usermod -p '' serveradmin
I hope that helps this make sense. It is understandable that this is confusing because what I am doing is the opposite of what people are instructed to do. Null passwords are considered a security risk unless you do it intentionally for some unorthodox implementation reason which I have done. I have a cron job that adds accounts within some character restrictions that bots try to brute force. I then monitor the bots behavior to see what current bots are attempting over SSH. I do the same for http/https. Both are what is referred to as a low-interaction honeypot.
Here is a bot with IP and port redacted that just tried to use my server as a DNS proxy:
Connection from 8.37.x.x port x on 50.116.13.30 port 22
Accepted password for admin from 8.37.x.x port x ssh2
Changed root directory to "/data/sftphome/admin" [postauth]
refused local port forward: originator 127.0.0.1 port x, target 1.1.1.1 port 53 [postauth]
Received disconnect from 8.37.x.x port x:11: Disconnected on user's request. [postauth]
Yes, true one-time pad encryption is not secure by modern standards, as you mention there's no authentication, you need a perfect random number source, and key management is horrendous.
However, the concept of encryption by XORing a stream and the plaintext is very much the modern way of doing things, and "OTP" is an analogy for that.
> 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.
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)
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.
It's cool to see how simple it is. It's a lot more intuitive than other ciphers are!
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.
So a hash function is allowed to destroy information, whereas it's pretty important that an encryption algorithm doesn't!
Look at the hash construction in stream ciphers, for example. The keystream is very long, but the key is short.
Or look at a perfect hash function, as used for hash tables.
I’ve never actually walked through the math behind hashing algorithms, but I’m assuming collisions come from truncation. I’m guessing you’re usually not able to know exactly where two inputs that collide for the first n bits end up diverging, so the only way to ensure most hash functions are one to one is if the outputs have infinite length. But, if you had outputs of infinite length for different inputs, eventually they’d have to diverge. Idk if that’s true of all hashing functions/maybe there’s a way to know after what point outputs for different inputs have to diverge for some.
That doesn’t necessarily mean you can figure out what length output for a given input is needed to make it one to one. Not sure you could avoid collisions even if the length of the output was infinite, but I’m assuming different inputs have to have outputs that diverge at some point.
Assume you have two inputs, A and B.
A may hash to: A38uT75kjGz B may hash to: A38uHso629t
So yes, if you were to cut these off after the A38u then you would no longer be able to say for sure if you hashed A or B to arrive at your hash.
Of course in practice this usually isn't a problem as long as you have "a long enough" output.
Assuming a perfectly random uniform distribution, the usual desirable property of a cryptographic hash - the probability of a hash function not having a fixed point (that is, hashing at least one x to itself) is (1-1/n)**n, where n is the number of possible outputs. As n approaches infinity - which it does pretty rapidly in this case, since we're talking about 2**32 to 2**512 in practice - this approaches 1/e, or about 37%.
So, not only is it possible, but most "good" hash functions (63% of them) will have them.
We use different words for Cryptographic Hashes, Password Hashes, XOFs, MACs, and (non-cryptographic) Hashes because they do different things and have different security properties. Misusing the terminology makes reasoning about what is meant difficult.
Suggested reading: Sponge Functions - https://keccak.team/files/SpongeFunctions.pdf
"Informally speaking, a random oracle* maps a variable-length input message to an infinite output string. It is completely random, i.e., the produced bits are uniformly and independently distributed. The only constraint is that identical input messages produce identical outputs. A hash function produces only a fixed number of output bits, say, n bits. So, a hash function should behave as a random oracle whose output is truncated to n bits."
For older designs like MD5, SHA-1, and SHA-256, the final hash is literally that state, just serialized into bytes and returned to the caller. (This is what makes "length extension attacks" possible on these hashes, which is why we need constructions like HMAC.) For newer designs like SHA-3 and the BLAKE family, the output is some function of the state, which prevents length extension attacks. This also makes it easy for these functions to offer "extendable output" features, i.e. as many output bytes as you like. (SHA-3 isn't standardized with this feature, but the very closely related SHAKE functions will gladly give you outputs of any length.)
However, one important thing to realize about these functions is that extended outputs do not increase security. This is counterintuitive, because we're used to distinctions like SHA-256 vs SHA-512, with the larger output providing more security in some sense. That's true, but it requires SHA-512 to keep a larger state in addition to producing a larger output. SHAKE128 and BLAKE3 always use the same state size, regardless of how many output bytes you ask for, and if you produce a collision in that state, all the output bytes will collide too.
Another commenter mentioned perfect hash functions, and my understanding of those is that they typically require the input set to be of some fixed size. If the input set is "any possible string", which it pretty much is for cryptographic hashes, I think trying to design a perfect hash function starts to get weird? At the very least, the state you need to keep will be proportional to the longest message you want to hash.
Or just truncate the hash so you don't get full state, like SHA-512/256.
1. It's less widely supported than SHA-256 or SHA-512. For example, it's present in OpenSSL but not in Python's hashlib. A reasonable workaround here is to just truncate SHA-512 yourself, which gives you a functionally similar but not-output-compatible hash. But no one loves monkeying around with standards like this.
2. SHA-512 doesn't have any hardware support that I'm aware of. SHA-256 has dedicated hardware acceleration on lots of ARM chips and recent x86 chips, which is very nice. But SHA-256 doesn't have enough margin in the digest size to truncate it. (SHA-224 is a thing, but it dumps more collision resistance than we're really comfortable with, in exchange for being only slightly resistant to length extensions.)
3. If your goal is to construct an XOF, SHA-512/256 is kind of perversely inefficient. You end up throwing away half your output bytes to prevent length extensions, but then running the hash (or at least the compression function) again to get more output bytes. On the output performance side, this is leaving a free factor of two on the table.
Find that makes it obvious why hash collisions are a thing and also why hashes are useful. A limited namespace is much easier to work with, assuming you don’t need the actual data.
Also, in general I disagree. For most people, safe defaults like hash tables with safe hashes and CSPRNG for random numbers are fast enough. And they have the important property of keeping people from shootings themselves in the feet.
People who have more stringent perf requirements will know and shouldn’t have a problem choosing a different implementation.
And to work with the analogy of the article: grinding a cow into a hamburger is hashing but not secure hashing, because if you have the right tools you can inspect the hamburger and determine some properties about the particular cow that it came from, like if it had mad cow disease. I dunno exactly what a securely hashed burger would be, but I don’t think it’d taste very good.
And you need to be sure that the properties you're trading off are really something you don't need. Using a cryptographic hash is much simpler, has fewer ways to going wrong and usually isn't that slow anyway.
I agree with your second point, developers reach for asymmetric signatures when hmac would do, and reach for hmac when a long fast non-cryptographic algorithm would do. I _think_ its an over-abundance of caution rather than a misunderstanding of the characteristics of hash functions.
The only thing is add is that the definition of encryption is incomplete. It seems to focus on symmetric encryption. Asymmetric encryption doesn't require the initial encryption key to get back to the original message. Rather, it uses a key pair - one public and one private.
In my pedantic technical opinion (technical as in literal, not technical-interview), these are all subsets of encryption. Encryption to me is anything that scrambles the data to non-literal-plain-text in a way where you need a key to read it. These are just encryption, but the password is always just the word "password", or for a specific example, the source text.
In my continued opinion, can't hashes be "found out" in theory if you had unlimited computing time + unlimited attempts at brute force hashing every string?
Encoding is just encrypting the text into a non-literal-plain-text format by using (an extremely weak, known password) to translate into another (computer-readable) language. I don't really have anything to add from the source to this one.
Why is my distinction about the definition of encryption important to me?
In my opinion, we shouldn't limit our mind to ONLY knowing encryption as a method containing some math formula someone came up with to scramble you data based on an input password. There are a magnitude of ways to encrypt your actions in a more broad sense.
For example, what if you identify yourself by handing in a series of paintings to somebody (an authenticator) who physically determines your entry? He can determine if you pass by having knowledge that the order of the paintings and the artist's initials correspond to their position in the alphabet to decrypt your ID number. (Some other tricks could be used to prevent random turn in or duplicates, such as only using a specific style of art, but I'm skipping that for this example.) Is that not an encryption method that accepts a user input and encrypts it with a black box formula to output some code?
You can't re-read what's hashed, though.
> I don't really understand the confusion around these terms in terms of day-to-day actual work. Is this really a problem?
It absolutely is. I've seen software that, instead of salt-hashing passwords in the DB, will encrypt them with an global RSA public key (not only less secure and way less efficient, you now also have an effective undocumented max-length of passwords).
Or, way more common, utilizing base64-encoding as "encryption".
If understanding of the differences was more widespread, at least these systems may have been less terrible.
My point boils down to it seems like there is ambiguity between the technical definition vs the actual practice and security requirements we've currently decided on as acceptable.
Somebody who uses base64 to "encrypt" into a database clearly did their job wrong.
A test question that says something like "True/False, encryption can be used to alter the original string into a different string" is true because it doesn't go into the details about the security that we all (should) know needs to be there. When we ask the question kind of backwards from the ambiguous meaning like this, I think we can get a different definition and end up with silly things that technically meet the definition requirement such as base64.
Anyway, my take doesn't really matter. It's more of venting how I always get stuck on easy questions in software dev interviews and end up losing out to somebody who uses base64 in prod to attempt implementing "encryption" to the database.
Hashing is similar to compressing a massive photo into a small thumbnail, it makes it easier and quicker to browse through photos, but you cannot recover the detailed resolution from the thumbnail.
Wrong. Possible with a rainbow table.
Knowing this you can see that it is only practical as an attack if the set of inputs you want to try is so small that you can realistically try all of them and keep the results somewhere.
Rainbow Tables got famous because Microsoft's incredibly bad LANMAN hashing scheme only has small inputs (7 bytes, the algorithm runs twice on passwords up to 14 bytes), so you actually can try literally all of them, but at the time a terabyte hard disk was very expensive, Rainbow Tables meant you needed much less disk space to store the resulting data and attack this lousy scheme (but somewhat more CPU to calculate the table).
I suspect it’s partly for the reason you’ve mentioned: the line between uses can sometimes get blurry. It’s a decent article that could do with some additional clarifications.
[0] Future can be nanoseconds later in any data-in-transit unlike data-at-rest, so I picked future to address the ambiguity of time measurement in different contexta.
Password databases should use a specialized, intentionally slow hash function, with a salt and preferably also with a secret key. That is, they should use something like argon2(secret, salt, password) or HMAC(secret,argon2(salt,password)) -- the latter so that you can keep the HMAC secret on an HSM.
This is a common interview question for a reason. A candidate who thinks hashes and encryption are typically alternatives isn't ready to do secure system design.