21
$\begingroup$

Does there exist an encoding/hashing/encryption scheme whereby the original string can always be derived in its entirety given the entire encoded/hashed/encrypted string, and nothing else (no key/password). But also, no portion of the original string can be derived given any portion of the encoded/hashed/encrypted string.

Basically this would be an algorithm that deterministically and reversibly jumbles up a string in such a way that the reversal algorithm requires the entire jumbled string.

Does such a thing exist? If so, what search terms should I use to learn more about it? I don't know enough about the subject to know the right words to find more information.

$\endgroup$
  • $\begingroup$ Unlikely. Say you have a "jumbled string" missing one character. In that case an adversary can guess / brute force the character. But maybe there is something like this where at least, say, 128 bits of information must be missing. EG you encrypt a string, then put the key at the end, and then hash the ciphertext, and XOR that with the key. $\endgroup$ – Maarten Bodewes Mar 22 '18 at 0:58
  • 1
    $\begingroup$ Yea that would still satisfy my practical requirements. I'm imagining strings of considerable length, and splitting the "jumbled string" into at least 3 chunks and handing them out to untrusted parties to store, so that any one party can't reconstruct any part of the original message, unless they know which chunks go together, and in what order. $\endgroup$ – bhazzard Mar 22 '18 at 1:04
  • 1
    $\begingroup$ Goodness, I hope I didn't just invent an encryption scheme at 2AM, I'm off to bed :P Note that this kind of thing is usually done by a secret sharing scheme. $\endgroup$ – Maarten Bodewes Mar 22 '18 at 1:05
  • 7
    $\begingroup$ Out of curiosity, why are you looking to do this? $\endgroup$ – webwake Mar 22 '18 at 14:38
  • 1
    $\begingroup$ Yes there is. Compression. Especially very, very efficient compression. Take zip for example. Go ahead, zip a file. Then open it in a hex editor and change ONE BYTE in the middle of the file. Unzip it and you get back garbage. $\endgroup$ – slebetman Mar 23 '18 at 9:01
24
$\begingroup$

Clarification

I'm wondering whether there exists an encoding/hashing/encryption scheme whereby the original string can always be derived in its entirety given the entire encoded/hashed/encrypted string, and nothing else (no key/password). But also, no portion of the original string can be derived given any portion of the encoded/hashed/encrypted string.

I am assuming that "no portion of the original string can be derived given any portion of the encoded/hashed/encrypted string" means "no portion of the original string can be derived given anything less than the entire encoded/hashed/encrypted string", otherwise the question would be self-contradictory.

Answer

It sounds like you are looking for a permutation. A permutation is an invertible transformation on a fixed-size set of blocks. If your input is larger, the/an All-Or-Nothing Transform may be useful. The OAEP mentioned by @DannyNiu is an example of an AONT.

For example, many block ciphers are built by interleaving applications of a permutation with the addition of secret key material. The permutation provides diffusion, which ensures that if you modify any part of the output then attempt to invert it, you end up back at a completely different input.

If you simply strip the key addition portion from a block cipher, it should also do what you're asking. For example, AES consists of subBytes, mixColumns, shiftRows, and addRoundKey. If you were to omit the addRoundkey operation, you would be left with a fixed permutation that provides the required avalanche effect and some degree of unpredictability. Another example of a permutation is keccak-f, which does the mixing for the SHA3 algorithm.

A key-less permutation does not provide encryption

Note that such a construction with no key is no longer providing encryption, as it is not possible to provide confidentiality of the message without some kind of secrecy, which is what the key provides. If anyone who has an input message can compute an output "ciphertext", or anyone who has an output "ciphertext" can invert it to the input message, then clearly confidentiality of the input cannot be achieved.

You tagged this question with "encoding", so perhaps confidentiality is not required in your use case. You would need to establish what you need this construction for and whether or not this is an issue.

$\endgroup$
  • 2
    $\begingroup$ This sounds exactly like an all-or-nothing transform. $\endgroup$ – user253751 Mar 23 '18 at 5:10
  • 2
    $\begingroup$ AONT is clearly what the question is looking for. I think you should lead with it. $\endgroup$ – otus Mar 24 '18 at 9:54
  • $\begingroup$ @otus I can do that, but I'm not so sure about the question being so clear cut, considering comments like this one and answers that all suggest different things, it appears that many people had different interpretations of what the asker was looking for. $\endgroup$ – Ella Rose Mar 24 '18 at 15:01
  • $\begingroup$ Ok, maybe not "clearly", but it's the most correct. +1'd now $\endgroup$ – otus Mar 24 '18 at 15:05
14
$\begingroup$

Secret Sharing may be another option to consider. It allows you to take a value, break it up into arbitrarily many pieces, and possession of a subset of these pieces, not the entire set, makes reconstruction of the original value impossible. This is done by multiple means, the simplest of which is with respect to additive secret sharing. Given a secret value $x$, $m$ shares of $x$ in a group $Z_N$ may be generated by selecting $m-1$ random values and assigning them to shares $$\forall i \in \{1,\dots,m-1\},[x]_N^{P_i}\in_RZ_N $$ The final share satisfies the equation $$[x]_N^{P_m}=(x-\sum_{i=1}^{m-1}[x]_N^{P_i})\mod N$$ This way every share is uniform random and is secure in an information theoretic sense. Additionally, this holds up to an individual possessing any $m-1$ magnitude subset of shares. Only possession of all $m$ shares will allow the original secret to be reconstructed, and this holds without respect to assumptions or limitations on computational power. If an individual does posess all $m$ shares, reconstruction of the secret is very easy since: $$x=(\sum_{i=1}^{m}[x]_N^{P_i})\mod N$$

$\endgroup$
  • 3
    $\begingroup$ In practise, I think what the OP actually needs, is to choose a random key, encrypt his text with it, and then distribute the encrypted text plus shares of the secret key to his N parties. $\endgroup$ – Martin Bonner supports Monica Mar 22 '18 at 11:10
  • 1
    $\begingroup$ The OP should also be aware that it is possible to arrange things so the secret can be decoded if any k of the N shares are combined. In fact, arbitrarily complex systems can be constructed (eg: at least six shares must be combined, but there must be at least two from each department, apart from audit which must be represented by at least one share) $\endgroup$ – Martin Bonner supports Monica Mar 22 '18 at 11:14
  • 3
    $\begingroup$ op can encrypt multiple times and distribute keys. Only all keys can decrypt the thing. $\endgroup$ – akostadinov Mar 22 '18 at 13:04
  • 1
    $\begingroup$ Martin Bonner, a threshold lower than the whole set of shares is not possible under additive secret sharing. It is in Shamir's scheme of course but that is not what I was discussing. $\endgroup$ – Ken Goss Mar 23 '18 at 3:16
  • $\begingroup$ It is possible that Shamir's Secret Sharing may be exactly what the OP is really looking for, considering that the OP wrote "I don't know enough about the subject to know the right words to use to ask the question." $\endgroup$ – Wildcard Mar 23 '18 at 3:42
9
$\begingroup$

OAEP - Optimal Asymmetric Encryption Padding may be what you want.

In RSA public-key encryption system, in order to prevent partial decryption, OAEP padding is used. In essence, it's a Feistel network with randomizing element.

When used alone, it can ensure no partial information can be derived from any partial information, but when the whole message is available, it's trivial.

In your case, this is no longer encryption - it's secret sharing.

Related link

$\endgroup$
6
$\begingroup$

A simple way to achieve this with common algorithms would be to do the following:

  1. Choose a random key (key)
  2. Encrypt the data using the random key (encrData)
  3. Hash the encrypted data (encrHash)
  4. Xor the key and the hash (xorKey)
  5. The result data would be the encrypted data + the Xor key (encrData+xorKey)

To reverse:

  1. Split the data into encrData+xorKey
  2. Hash the encrypted data (encrHash)
  3. Xor the xorKey with the encrHash Because the way xor works this reverses the process above (key)
  4. Decrypt the data with the key

If needed base64 the encrypted data to produce string form

With this scheme you will need the entire string to decrypt the data and can use any secure algorithm (ex AES and SHA256)

$\endgroup$
  • $\begingroup$ How secure would this still be if, instead of choosing a random key, we'd just split off the first 512 bits of the message as the “key”? $\endgroup$ – leftaroundabout Mar 22 '18 at 22:24
  • $\begingroup$ @leftaroundabout certainly weakens this method. That being said this method is not secure in itself because the decryption key is already provided with the message. $\endgroup$ – webwake Mar 23 '18 at 13:18
  • $\begingroup$ leftaroundabout, If you were looking to do convergent encryption (where the same text always returns the same output) you could use the hash of the decrypted data and use that as the encryption key. $\endgroup$ – webwake Mar 23 '18 at 13:19
  • $\begingroup$ @leftaroundabout If you use the first 512 bits of the message as the key, then an adversary can decrypt any part of the message they have as long as they also have the first 512 bits, even if they're missing other parts of the message. $\endgroup$ – Macil Mar 23 '18 at 20:26
  • $\begingroup$ @AgentME those 512 bits would never be sent in plaintext, only XORed with the hash of the rest of the message. $\endgroup$ – leftaroundabout Mar 23 '18 at 21:08
1
$\begingroup$

The "key" is secret data that are used in encryption with known "algorithm". Of course you can make keyless algorithm - get permutation, shifting stuff around, bit inversion, whatever. Employ any known strong encryption with built-in values. Mix and match all you want! However, this effectively makes algorithm itself the key. Once someone has access to your encryptor/decryptor and/or any built-in values, they don't need to know any additional data - which is ENTIRE REASON for separate key - and can decrypt whatever they want.

Incidentally that's primary and inevitable point of failure of futile attempts for DRM.

$\endgroup$
  • $\begingroup$ Just in case you're missing the terminology, you're talking about white-box encryption of AES or other block ciphers. $\endgroup$ – Artjom B. Mar 23 '18 at 22:52
0
$\begingroup$

One-time pad it

Given the following conditions...

  • Alice has a plain-text. She wants to encrypt that.
  • After encrypting it, Alice obtains several cipher-texts.
  • Alice wants to give the cipher-texts to people that are not authorised to read the plain-text. None of them shall be able to decipher the cipher-text on their own.
  • If all the people that have the cipher-texts give them back to Alice, Alice must be able to reconstruct the plain-text.

This is easy: use a One-time pad.

  1. Alice creates a key (K1) of the same length as the plain-text.
  2. Alice XORs the plain-text with the key, she gets C1.
  3. Alice gives K1 to Bob and C1 to Carol.

Unless Bob and Carol are in cahoots, neither can reconstruct the message. When both of them give the key and cipher-text back to Alice, Alice only needs to XOR them together to get the plain-text back.

Expanding

Alice wants better security and involves Dave and Erin. The algorithm becomes:

  1. Alice creates a key (K1) of the same length as the plain-text.
  2. Alice XORs the plain-text with K1, she gets C1.
  3. Alice gives K1 to Bob.
  4. Alice repeats 1, 2 and 3, applies K2 on C1, and gets C2. She gives K2 to Carol.
  5. Alice repeats 5, to get K3 and C3. She gives K3 to Dave.
  6. Alice gives C3 to Erin.

This can be repeated as many times as Alice likes.

There is some fragility in this as Alice needs to get the key/cipher back from everyone before she can get her plain-text back. But this is a problem for another post.

$\endgroup$
  • 1
    $\begingroup$ You have the scenario wrong. Alice is not worried about Eve. She actually want's to give bits of the encrypted message to Bob and Charlie (and possibly additional people), and for them all to be able to read the encrypted message but only when they all combine their parts of the message. @webwake's answer shows how to do that. $\endgroup$ – Martin Bonner supports Monica Mar 23 '18 at 14:04
  • $\begingroup$ @MartinBonner Rewritten after your comment. $\endgroup$ – MichaelK Mar 23 '18 at 14:36
-4
$\begingroup$

I believe this can be achieved, but of course you need to secure both of your encryption and decryption algorithms. Hide it on a very secure server with a rest endpoint where authentication is needed to be able to use the rest service. so to use the algorithm you need to send authenticated requests to your secure endpoint. Also dont forget to obfusicate your production codes.

If you are new to writing encryption algorithm you can start by learning som simple trans table encoding just to get a start. Your key will be mathematics and with the use of strong psuedo random number generators. So if you store all results in a database, be sure to use encryption and not pure encodings cause it will be easy to crack.

Why not try to create a random number generator too while your at it. If you can calculate the n^x decimal of sqrt(2) or Pi, or some othe irrational number you can create your own deviation to produce a strong non standard prn.

If you belive your encryption is strong enough try to give a sample of x number of pure values and the values of the encryption to see if anyone can crack them.

And lastly don’t take my word on any of this Im just a noob, with an imagination that I know something I dont, I do other stuff for a living.

$\endgroup$
  • 2
    $\begingroup$ If your algorithm is secret, then it's not keyless—your algorithm is the key. (This is called ‘security through obscurity’, and it's been recognized by cryptographers for over a century since since 1883 to have shortcomings as a design principle.) $\endgroup$ – Squeamish Ossifrage Oct 26 at 19:26
  • $\begingroup$ Nice wiki article thanks :) As I said Im a noob in this and this was a nice clearification! I think I love obscurity by nature, but I see why its not recomended for things that should not for any circumstances be comprimised. $\endgroup$ – Paal Pedersen Oct 26 at 19:44
-5
$\begingroup$

Let's take the simplest cipher I can think of which the key is not obvious: ROT13. You replace a letter with the 13th letter after it, in the alphabet. Because there are 26 letters in the alphabet, you don't need to inverse the algorithm for decryption. Is ROT13 an example of keyless encryption, a very weak one of course? No, because 13 is your key. I don't think any algorithm that can be expressed with a computer can be keyless.

Another bizarre example of which the key is not obvious is a language. Obscure languages have been used as a form of encryption. The most famous example are the code talkers of World War II. Navajo was an unwritten language at that time and the only way to encrypt a message was using your language skills and your mouth. You decrypted a message using your ears, your language skills, and pen and paper. So is this form of encryption keyless? To answer that question, we have to know if this algorithm can be expressed by a computer. There is no way for a computer to translate English to Navajo right now, but there are services that can translate English to Chinese and vice versa. If we trained a language model that could automatically translate English to Navajo using a computer, that model would be your key.

So this answer doesn't ultimatively exclude any form of keyless encryption might exist. I just had a look at some encryption topics not covered by RFC or NIST and I don't think it's possible for keyless encryption to exist.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.