how to efficiently prove the query result is empty? Consider a simplified scenario.
Suppose an untrusted server holds a set of data $A=\{ a_1,a_2,\cdots,a_n\}$.

A client issues a query $b$ to the server and wants to decide if $b\in A$. The server replies a "yes" or "no". Then how can the client verify the correctness of the server's reply?

It is relatively simple if $b$ is indeed in $A$ and the server answers "yes". We can use some siganature- or hash-based schemes. However, what if the server just reply "no"? How can the client verify that $b$ is not in the set?

I know (but not much) some schemes such as Authenticated Set. But the complexity seems rather high.

So I am looking for efficient schemes that can prove that the query result is indeed "empty".

Obviously something needs to be trusted. If there is no prior  trusted something it can't be done.
In one setup used in DNSsec a trusted party signs empty intervals according to some ordering. So when you want to give a negative answer you provide the signed empty interval.
Obviously there is a problem with the validity of such answers when the data changes. You may get a properly signed but obsolete answer. Though people can in many cases commit on a  certain record remaining valid for a significant time frame. Commiting to a range remaining empty is much harder.


Is public-key cryptography the only option in this scenario? Two parties: a client and a server are to a agree on a symmetric key. Both the client and the server are aware of a master password. The way this is currently done is:

Both parties hash the master password using SHA-256 to create a password hash.
The password hash is used by the client to encrypt a message which includes, amongst other things 128 pseudo-random bits. This encrypted message is then sent to the server.
The server checks if the message is valid since it knows the master password and in turn the password hash. If the message is indeed valid, the server also generates a message (of similar structure to the client's message) and in the same way encrypts it using the password hash. The server then responds to the client using the encrypted message.
The client decrypts the encrypted response using the password hash.
At this point both parties have agreed on 256 random bits (128 bits from the client's request and 128 bits from the server's response).

The aim is to make sure that:

It is infeasible to recover the unencrypted contents of either the client request or the server response.
It is infeasible to recover the master password or the password hash from either the client request or the server response.

The problem is that this technique leaves room for offline attacks to guess the master password (online attacks can be dealt with) and there may be other attacks that I haven't thought of yet. This gives rise to the question:

Are there any other possible attacks?

I considered that I could use PKC (RSA specifically) to add another layer of encryption (PKC on top of SKC) on both the client request and the server response so that an attacker cannot brute-force the low entropy master password without having the RSA private key.

Now, additional questions arise:

Is this a valid method for achieving the goals mentioned above?
In either case are there better solutions?
Are there solutions which do not involve PKC?
Which alternative solutions are the most secure?

"Is to be encrypted" is not a ultimate goal. You do not encrypt data for the sake of it; you encrypt data as a way to ensure a given security property, e.g. transmitting some data between two machines, without compromising the data confidentiality with regards to attackers who may spy on the transmission line (or even alter data in transit).

If:

your problem is indeed a question of data transmission;
you can arrange for both sender and receiver to share a common password;
the transmission uses an online protocol where messages can flow in both directions;

then you can use a secured data tunnel, with a Password-Authenticated Key Exchange protocol to establish a shared symmetric key (used for tunnel encryption and integrity) with mutual authentication relative to the password. PAKE protocols ensure that attackers spying on the line, and even active attackers who can try to impersonate the client or the server, learn nothing which can be used to "guess passwords". With a PAKE protocol, each "password guess" must imply some communication with an honest system (the real server or client). Server and clients can then easily detect brute-forcing attacks after only a few dozen tries. Therefore, PAKE protocols are secure even with passwords of low entropy.

A secure tunnel with a PAKE protocol is a complex beast, easy to get wrong in many ways. Hence you really should rely on an existing, well-analyzed protocol. I suggest SSL/TLS with SRP; this is supported by at least the opensource GnuTLS library.

If the transmission is offline (e.g. in an emailing context: the sender must send all its data in one go, and that must be sufficient for the receiver who acts only afterwards), then a password will not be enough, although you can make it quite hard for the attacker by using an appropriate key derivation process, in which the password is hashed many times with a random salt. Usual recommendations are PBKDF2 and bcrypt. A password with about 30 bits of entropy is sufficient if you use a key derivation process which implies at least a few seconds of computation on a reasonably recent PC.

To get more security than that, you must use a stronger shared secret key; if this implies an unsolvable key distribution process, then you can go to a public-key based scheme, the archetypal protocol being OpenPGP (see GnuPG for an opensource implementation). You still need to make sure that the sender has the genuine receiver's public key, but (at least) this implies no sharing of secret data.

Edit: with the new phrasing of the question, the answer is now clear: PAKE. You want to get a shared secret with mutual password-based authentication, and resilience against offline dictionary attacks. PAKE protocols are precisely designed for that. All currently known PAKE protocols involve some "public-key-like" elements, so you will not avoid at least some mathematics. SRP is an adequate, well-documented PAKE protocol.


Why are RSA keys encoded with ASN.1 for TLS? Browser vendors use ASN.1 encoding for RSA certificates in the TLS protocol. RSA public keys are just a number, so why do we need encode them to something else? That increases the risk of security problems.

Think about this, say my public key is

9821347676528476512348612390874073765227653408545634205496835 (note this is not a valid public key, just randomish typing).

What does that mean? Big or little endian? Hex or decimal? Specifically for RSA, where is $e$, where is $N$? What is this public key authorized to do (encrypt, sign, etc)? Who has signed this key? To whom is the key linked?

While a public RSA key is "just a number" there are a lot of reasons to encode the key in a standard way so that every computer everywhere knows how to understand it, what it is authorized to do, who it belongs to, etc.


Computing PGP ed25519 and curve25519 keygrips? There are public key algorithmic differences for how PGP computes fingerprints and keygrips. For the v4 protocol, fingerprints are not exclusively computed from public keys while keygrips are. RFC 4880 makes no mention about keygrips.

After digging into code at 10 different places in the the libgcrypt from https://github.com/gpg/libgcrypt/blob/master/tests/keygrip.c, it is still a mystery as to how PGP keygrips are computed for ed25519 and curve25519.

Fortunately, the keygrip.c provides the two normative example test vectors:

 1. ed25519:
    publicKey = 773E72848C1FD5F9652B29E2E7AF79571A04990E96F2016BF4E0EC1890C2B7DB,
    keygrip   = 9DB6C64A38830F4960701789475520BE8C821F47

 2. cv25519:
    publicKey = 918C1733127F6BF2646FAE3D081A18AE77111C903B906310B077505EFFF12740,
    keygrip   = 0F89A565D3EA187CEA39332398F5D480677DF49C

Can someone provide the operations on the public keys prior to the sha1 hash that creates that creates the keygrip output? (Thanks in advance.)

Keygrips are not part of PGP at all, they're just an implementation detail of GnuPG's key storage architecture specifically (which uses a common key store for PGP, S/MIME, and SSH).

As you saw, GnuPG uses libgcrypt for cryptographic operations, and the keygrip calculation can be found in cipher/pubkey.c where it's just a SHA-1 hash of the public key's parameters.


How can a decryption program tell me that a private key is incorrect for RSA and ECC? I have a program which will encrypt the symmetric key with RSA public key with keysize 2048. I am able to decrypt the message with the corresponding private key.
My question is,  is it possible to decrypt a message with the different private key with same key length successfully? if it is possible then decrypted data can be junk data? In this case, how can I know, decryption is / was successful?

I have the same program for ECC keys (256,384) and will decryption return junk data in ecc using a different private key?

The answer is different for the schemes that are used. So there is no one answer for the simple reason that the different modes have different properties.

In general modes such as PKCS#1 v1.5 or OAEP encryption is used for RSA. These modes contain a specific padding that is performed before the modular exponentiation that is the backbone of RSA. Performing the modular exponentiation with the private key - possibly sped up using the Chinese Remainder Theorem or multi-prime calculations - will result in the padded message. Now the padding is checked before the message is returned. This means that using an invalid private key / ciphertext pair will result in a padding error. Note that padding errors may actually lead to attacks on the key.

It is not possible to perform encryption directly using ECC. Instead ECIES can be used to perform it indirectly. This is basically key agreement followed by encryption using a symmetric key. In this case the asymmetric key agreement may fail without error resulting in an incorrect symmetric key. Then the subsequent decryption may not cause an error either. This can be fixed by using an authenticated cipher such as GCM, which generates an error for any invalid secret key / ciphertext pair.

The same goes for RSA-KEM as for ECIES. So again: it depends on the scheme.

So the conclusion: use an authenticated encryption scheme for the symmetric cipher. And don't forget to protect against padding oracle attacks for RSA. PKCS#1 v1.5 padding should not be used anymore because of a specific padding oracle attacks called the Bleichenbacher attack. OAEP should be secure (if the implementation is secure, of course).

If you do that you can be sure that some kind of error is returned if you use an invalid private key / ciphertext pair.

Another option is to sign the plaintext message. In that case you can verify the authenticity of the message after decryption. This has the additional advantage that an adversary cannot simply encrypt a different message using the public key. In general this should be combined with the authenticated encryption option mentioned in the previous section.


What is FIPS 140-2 for? I've just used the FIPS 140-2 tests as implemented in rngtools, the rngtest.  I ran it on a 12.3MB file of pak8 compressed ASCII text.  It passed most of the tests, with a 0.2% failure rate.  Monobit and Continuous runs tests actually complete without any failures.

It seems very lax at detecting randomness.  What's the point of this test if it (effectively) passes off a highly structured zip like file as good quality random numbers?

Here is the detail...

cat /tmp/raw.txt.fp8 | rngtest

rngtest: starting FIPS tests...
rngtest: entropy source drained
rngtest: bits received from input: 98327312
rngtest: FIPS 140-2 successes: 4906
rngtest: FIPS 140-2 failures: 10
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 1
rngtest: FIPS 140-2(2001-10-10) Runs: 1
rngtest: FIPS 140-2(2001-10-10) Long run: 8
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0

First, in a strict sense, detecting randomness by statistical tests is impossible. One can only detect absence of randomness.

Second, a perfect compression algorithm should generate an output which is indistinguishable to random numbers. A hand-waving argument goes as follows:
If the output would not be indistinguishable from random numbers, then it would contain some remaining structure. And this structure could be used to compress the input even more.

This means, the only thing you can probably do is to throw many good statistical tests to your random numbers. It cannot prove that your source is true random but it can give you some evidence that it is not broken.

A third point to mention is that NIST has already superseeded the simple test of Fips 140-2 by the far more comprehensive tests of the Nist SP 800-90B publication.


can we use two different hash functions in single hmac? Can we use two different hash functions in single hmac..for ex' for inner layer hash function md5 and for outer layer hash function sha1

This is exactly what was done in early versions of HMAC. Of course, there would be no reason to do this with an already broken hash function. Note that MD5 is completely broken and SHA1 is close to, so neither of these are great choices.


Why is it claimed that ElGamal is worse than RSA? I have some notes that claim that ElGamal is worse than RSA in the sense that ElGamal is length-increasing. Do anybody know what this means and why is a bad property?

Edit:

For completeness I show you the model of RSA I'm working on (the very basic one)

and also the ElGamal model I'm working on:

In fact ElGamal advantages are also pointed out. First generation of parameters is more efficient and second ElGammal works in various types of groups while the setup for RSA is $\mathbb{Z}_{n}$. So the comparison should be done over $\mathbb{Z}_{n}$.

What the notes remark is that the ciphertext in ElGamal encryption in $\mathbb Z_p^*$ is about twice as large as the ciphertext in RSA, when working with $p$ and $N$ of about equal size; that's because the ciphertext $(u,v)$ in ElGamal has 2 integers, when $y$ in RSA has 1; and $u$, $v$, $y$ are about the same size (also the size of $p$ and $N$). Making $p$ and $N$ of about same size makes sense, because that give comparable security (for proper other choices).

Larger ciphertext is bad in some sense, because that makes ciphertext transmission even so slightly longer, and requiring extra resources. That fact is not very relevant in practice:

A factor of 2 in size there maters in only some applications (and almost not on anything where the message goes thru a modern network), because practice does not use either ElGamal or RSA for bulk data encryption; its uses hybrid encryption, in which the bandwidth used for asymmetric encryption is small in absolute value, and most often in proportion.
ElGamal encryption can be done in groups (like, elliptic curve groups) with much more compact representations of elements, and then the balance of ciphertext size shifts straight in the other direction, with ElGamal the winner by a factor of more than 2; so in the rares cases where ciphertext size matters, we want to use this ElGamal variant.
There are a lot of other often more important appreciation criteria than ciphertext size for an asymmetric cipher; including

public key size (ElGamal wins by an inch in the race condition of the question's drawing, but RSA can pull a provably safe technique and win comfortably, unless ElGamal pulls the other group card),
key generation speed (ElGamal wins, assuming the practice of reusing the same group for multiple keys),
encryption speed (RSA as usually practiced wins, by a comfortable margin; and its main competitors in this category are cousins like Rabin encryption),
decryption speed (ElGamal as usually practiced wins),
combined encryption and decryption speed on same hardware (ElGamal as usually practiced wins),
simplicity of a safe message padding for non-random message (ElGamal wins by acclamation of the jury)...

As an aside, RSA can not safely encrypt arbitrary messages (for $b$-bit security we need to sacrifice at least $b$ bits out of $\lfloor\log_2(N)\rfloor$, and then in RSA OAEP practice we sacrifice about $2b+15$ bits); when ElGamal in $\mathbb Z_p^*$ can encipher any $m$ in that set, including $\lfloor\log_2(p)\rfloor$ bits.
That aside itself is moot, since in practice we very often encipher messages much shorter than $\lfloor\log_2(N)\rfloor$ or $\lfloor\log_2(p)\rfloor$ anyway, because the messages really are keys to other cryptosystems.


Why do fully homo-morphic constructions use 'ring' or 'lattice' structures? Is there a significantly advantage to these data structures, or is it simply the status-quo and the easiest to use for describing constructions?

Lattices are used simply because we do not know how to build homomorphic encryption from any other problems, like factoring or discrete logarithm.  Their mathematical structure was found to simultaneously enable homomorphic addition and multiplication while other bases for encryption could handle at most one of them.  (For the case of ideal lattices/rings, this seems intuitive:  If ciphertexts are elements of a ring then you can naturally add and multiply them, although things are not really that simple.  It was later found that the ring structure could be removed, and that any lattice would suffice.)

Advantages like quantum resistance etc are only incidental.


LSB of the Exponent in the DL Problem Can Be Efficiently Computed for Groups of Even Order I am studying a script on the mathematical foundations of cryptography as part of which I am currently trying to wrap my head around some basic cryptographic reductions. I am stuck on one problem that I would like to request some help / advice on how to proceed:

Consider the (D)iscrete (L)ogarithm problem for a group $H = \, < \negmedspace h \negmedspace >$ of even cardinality $\lvert H \rvert = 2 n$. Show that there exists an efficient algorithm that computes the LSB of $x$ in the DL problem $y = h^x$.

So far the only thing I managed to come up with is the following: We can determine the order of $y$ and find $c$ s.t. $y^c = h^{x c}= 1$. Since the group caridnality is even we conclude that $x c = m 2 n$. If $c$ is odd we can therefore conclude that $x$ must be even and hence the LSB of $x$ is zero. How can I proceed from here? The only additional insight I can present is, that due to Lagrange, we know that $c$ divides $2 n$.

Write $x=x_0+2x_1$ for $x_0\in\left\{0,1\right\}$, so that the goal becomes determining $x_0$. Now compute $y^n$ (in terms of $h$, $x_0$ and $x_1$), and determine its order. What happens when $x_0=0$ and when $x_0=1$? Can we easily differentiate between them?

Note that this is the idea underlying the Pohlig-Hellman algorithm, so it may help to have a look at that.


Which hash is used when providing signature algorithm ED25519 or ED448? From TLS 1.3 there are two signature algorithms using edDSA:

      /* EdDSA algorithms */
      ed25519(0x0807),
      ed448(0x0808),

All the other signature-schemes provide hash information, for example:

ecdsa_secp256r1_sha256 => sha256

rsa_pkcs1_sha384 => sha384

How can I determine when receiving edDSA signature algorithm which hash to use?

Is there any default value for each one of them?

Hash algorithms:

Ed25519 uses SHA-512 (As referenced on wikipedia or on bearssl.org)
Ed448 uses SHAKE-256$^1$ (As referenced on bearssl.org)

$^1$ SHAKE-256 is a SHA-3 algorithm, a subgroup of the "Keccak" family.


Diffie-Hellman with Galois field I Google around and can't find any page mentioning Diffie-Hellman with Galois field $GF(p^n)$ with $n>1$.

Is there a reason for this?
For example, wouldn't Diffie-Hellman with $GF(2^n)$ be desirable for computation?

The security of the Diffie-Hellman protocol relies on the decisional Diffie-Hellman assumption. This assumption, in turn, requires the discrete-logarithm problem (DLP) to be hard. In an earlier line of works, heuristic quasi-polynomial algorithms were shown for fields with small characterstic [J,BGJT,GKZ]. A proof (for expected run-time) was recently given by Wesolowski and Kleinjung [WK]. In particular, it was shown that DLP in $\mathbf{F}_{p^n}^\times$ can be solved in (expected) time $(pn)^{O(\log{n})}$. In light of these attacks, the Diffie-Hellman protocol should be avoided in fields of small characteristic.

[J] Joux, A new index calculus algorithm with complexity L(1/4+o(1)) in very small characteristic

[BGJT] Barbulescu et al., A Heuristic Quasi-Polynomial Algorithm for Discrete Logarithm in Finite Fields of Small Characteristic

[GKZ] Granger, Kleinjung and Zumbrägel, On the discrete logarithm problem infinite fields of fixed characteristic

[WK] Wesolowski and Kleinjung Discrete logarithms in quasi-polynomial time in finite fields of fixed characteristic


Security implication of deriving key with fixed salt for files authentication Context:
I need to calculate MAC for a collection of files just for future integrity and authentication verification.

This is the conceptual order of steps:

Derive a 64 bytes key from user input password, using PBKDF2 (with sha512) with 10k iterations and fixed salt.
Then, use this derived key to calculate the MAC using HMAC+BLAKE2b(512) and store the output for possible future verification.

PBKDF2 is used instead of HKDF because I can't ensure that the input will have enough entropy.

The key derivation step happens once (on app initialization) and later used multiple times to calculate MAC of arbitrary number of files. Generating an random IV is not possible because I don't want (as far as possible) generate a derived key for every file. Having duplicated MAC digests for duplicated files it is not an issue.

Question: For that purpose, are there some security implications having that salt as a fixed byte string?

Answer: As @SEJPM pointed me, the general security model of MAC algorithms assumes that the keys will be reused for calculate arbitrary number of MAC's, so this scheme should be secure.

For that purpose, are there some security implications having that
  salt as a fixed byte string?

The key re-use is fine here, because the standard model for MACs allows the attacker to request an arbitrary (polynomially bounded) amount of authenticated messages while still not being able to forge new MACs.

As a bonus, you may want to consider using the built-in MAC mode for Blake2, because it reduces code complexity and improves speed while providing a comparable security level (thanks to Richie here)


Efficient peer to peer untrusted signature aggregation Suppose I had a peer to peer system, there are a few writers with the same signing key, and all readers have the verification key.
A naive system is that each document $d_1..d_n$ gets signed $s_i=sign(d_i)$. This would allow anybody to verify that every documents is written by authorized writers.
However it would be inefficient for a new user to join this group, as they need to verify every document, taking $O(n)$ time.
Now a writer can create a group signature $sign([d_1..d_n])$ in addition to the individual signatures. This means a new user can verify all documents in $O(1)$ time. This works because the writer has every document.
It will not work in a peer-to-peer system where no writer may observe the complete set of documents, for example due to being offline.
That suggests that readers need the power to merge the signature independent of the writers. Is there some system where a untrusted user can generate an aggregate signature like $sign([d_1..d_n])$ above by combining the $s_i$ values?

BLS Multi Signatures - the aggregated signature is the product of signatures
Homomorphic Signature Schemes - the aggregated hash is the product of (prime) hashes.
(not a signature) it might be worth investigating signing Homomorphic Hashes, you cannot combine them


Is calculating HMAC from hashed input a good idea? The original HMAC algorithm is as follows:

  H(K XOR opad || H(K XOR ipad || text))

What if text would replaced with H(text)? Will it weaken the HMAC algorithm?

What if text would replaced with H(text)? Will it weaken the HMAC algorithm?

Yes. It makes collision attacks on the hash function apply to the MAC, which isn't normally the case with HMAC. You can find a pair $(m, m')$ that hash to the same value, get the MAC for one of them and move it to the other.

That means that your modified HMAC construction would be insecure with a hash function $H$ that isn't collision resistant, such as MD5. Even though normal HMAC-MD5 is still believed to be secure. In fact, any hash function with a small enough output size to lack collision resistance would be insecure to use in this modified HMAC.

If you use a collision resistant hash function, such as one of the SHA-2 hash functions (notably SHA-256 and SHA-512) or SHA-3 then the modified HMAC should still be secure.


inverse problem about scalar multiplication on elliptic curve Let $E$ be an elliptic curve over a finite field $F_p$. Given $n$ be a positive integer and $Q$ be a point on $E$, assume that $Q=nP$, how can we find this $P$? We can assume that $n|p-1$. If $n$ is "small", I would imagine that it is possible using division polynomials. Is it a difficult problem if $n$ is large enough? How difficult is it?

As Samuel Neves described in the comments it is trivially possible to obtain $P$ from $Q=[n]P$, given $Q$ and the integer $n$.

Simply compute $k=n^{-1} \bmod \ell$, with $\ell=|E(\mathbb F_p)|$ being the order (= the number of points) of the curve. $\ell$ is usually known.

Then, to obtain the desired point $P$, calculate $P=[k]Q=[kn]P$ and you're done.


Supercomputer to crash hash For NVIDIA TESLA V100 I know a hashcat performance for SHA1: it is about 17000 MH/s. Performance index for V100 is FP32 5120,  FP64 2560.
But what about supercomputers? For example Summit supercomputer from USA is 200
petaFLOPS in peak. Is any was to calculate it's hash per second performance for SHA1 for example?

The number of NVIDIA TESLA V100 in the Summit supercomputer is documented, and it's reasonable to assume that most of its hashcat performance for SHA-1 would come from that: according  to this source on the Power9 CPU ISA, there is no SHA-1 instructions for the Power CPUs, and then these benchmarks give an order of magnitude on other CPUs.

Isn't that enough for answering the question?

Caveat: a truly powerful specialized SHA-1 cracker would use ASICs, like bitcoin miners do, for even more performance.


Encrypt-then-MAC paradigm I read that the Encrypt-then-MAC paradigm is provably secure.

From what I understand, when using for example AES for encryption and HMAC_SHA256 for MAC generation (and the keys $K_1 \neq K_2$), this means the following:

$ciphertext = AES_{K_1}\{plaintext\}$
$mac = HMAC\_SHA256_{K_2}\{ciphertext\}$
send: $ciphertext \;\|\; mac$

I have two questions regarding this construction:

Does it negatively affect security to calculate a hash value of the ciphertext before MAC calculation? Like exchanging step $2.$ with this: $HMAC\_SHA256_{K_2}\{SHA256(ciphertext)\}$.
What security properties are offered by this construction in general -- because I don't understand, what about this construction is provably secure.

Does it negatively affect security to calculate a hash value of the ciphertext before MAC calculation? Like exchanging step 2. with this: HMAC-SHA256(SHA256(ciphertext)).

Technically, yes, but not significantly. In order to attack the scheme you propose, the attacker would have to be able to do at least one of two things: (1) Find an attack on the (standard) HMAC-SHA256 scheme; or (2) Find a collision for SHA256. Currently, the cryptographic community believes that one can safely assume an attacker can do neither of these things. (Contrary to what some may expect, an ability to do the second does not imply an ability to do the first.)

What security properties are offered by this construction in general -- because I don't understand, what about this construction is provably secure.

What do you mean by "this construction"? Do you mean Encrypt-then-Mac, or HMAC-SHA256?

If you meant Encrypt-then-MAC, David Cary provided a link to this question, and you might find the answers helpful. To summarize, one can prove that an attacker cannot learn information about the plaintexts (aside from their lengths), and cannot create a ciphertext that will pass the MAC integrity check. Here, attackers are assumed to have the ability to conduct chosen message attacks; that is, we assume that the attacker can convince or trick one of the parties into sending some messages of the attacker's choosing, and show that having this power is not enough for the attacker to "break" the scheme. (This is very conservative: in the real world, most attackers won't have this ability.) We also assume that the encryption algorithm and the MAC algorithm are themselves secure, and use independently chosen, random keys.

If you meant HMAC-SHA256, then see the second part of my answer to another question. Proving that HMAC-SHA256 has the properties discussed there requires making some (reasonable) assumptions about SHA256.

In both cases, the proofs are not "absolute". We need to make assumptions about the underlying algorithms, and the proof only shows that the probability of the attacker succeeding is very small, provided you don't do something like use the same key to encrypt petabytes of data.

Note:
In your question, you wrote Ciphertext = AES_K(Plaintext). But this is (almost always) wrong! AES can only work on 16-byte strings. To encrypt longer strings, you need to use AES inside of some mode of operation.


First 16 characters replaced after decrypting AES encrypted string I encrypted the string below using AES

<?xml version="1.0" encoding="UTF-8" standalone="yes"?>
<ValidationRequest>
    <ID>1234567890</ID>
</ValidationRequest>

and after decryption, the first 16 characters of the xml was replaced with special characters as shown below:

Q)ZvZ~J+/De*.0" encoding="UTF-8" standalone="yes"?>
<ValidationRequest>
    <ID>1234567890</ID>
</ValidationRequest>

What went wrong?

Most likely you are using CBC mode, and most likely you did not supply the correct IV during the decryption process, resulting in improper decryption of the first block.

The IV should be supplied as part of the encryption process, and be different for every message, and be included with the ciphertext so that it is available for decryption. More than likely at least one of those did not occur.


How to store keys for a cascading encryption? What is the best way to implement a cascade encryption?

I'm trying to figure out how to cipher a string (or message) using Serpent-Twofish-AES and then store the keys.

I'll provide an explanation, then maybe someone is going to be able to explain how to resolve the issue I'm facing. I've read the TrueCrypt documentation before posting here.

Let say Anna want to send an email to Bob. Anna type a password and give it to Bob face to face.

Message being sent over internet: Hi Bob, this is Anna

I split the message into chunk.

#1: "Hi Bob,"
#2: " this i"
#3: "s Anna"

After that, each chunk is encrypted with AES then Twofish and then with Serpent.

Key #1 encrypt Chunk #1 with AES
Key #2 encrypt Chunk #1 with Twofish
Key #3 encrypt Chunk #1 with Serpent
Key #1 encrypt Chunk #2 with AES
Key #2 encrypt Chunk #2 with Twofish
Key #3 encrypt Chunk #2 with Serpent

And so on...

Then all encrypted chunk is stored somewhere...

The keys are generated based on the password Anna provided.

Where do I store the keys?

I didn't find any useful information about implementing a cascade encryption and I think this question might be good for the internet's knowledge.

The part of this answer that talks about key storage is at the end, the first part is about implementing a cascade.

There are 2 main methods for cascading block ciphers, inside of the mode and outside of the mode. Within the encryption you have your mode of operation, and you have your block cipher cascade. The first cipher in the cascade will be considered the primary cipher.

Inside the mode means replacing the block cipher inside the mode with the cascade. In this method there is the single mode of operation wrapped around the cascade. The non primary ciphers essentially act in ECB mode on the ciphertext of the primary cipher, and the ciphertext of the final cipher is the ciphertext of the mode's inner cipher.

Outside the mode means you encrypt the plaintext with each mode (and each cipher) in sequence. This allows use of multiple modes, which can either have a security or performance advantage (or both, or neither). For example, the output of AES_CFB can then be encrypted with Twofish_CBC.

Depending on the target platform and development language, either method may have an implementation advantage. Certain modes of operation such as CTR or ECB are parallelizable, whereas CBC and CFB are note. CTR also allows encryption of lengths that are not a multiple of the cipher block size without using padding or CTS. The method Truecrypt uses is optimized for filesystem encryption, and using that method may not meet your requirements (which are not specified). AES also allows high speed timing analysis/DPA resistant implementations on modern processors with AES_NI instructions.

Cascading has not officially been given anyone's seal of approval, but it does have an allure that a single cipher may be completely broken and your ciphertext remains secure. For the actual security of using it, see the answers here: Combining multiple symmetric encryption algorithms - implications? I tried not to talk about how to implement in my answer, as it was not part of the question like it is here, but the security implications are quite relevant.

As for the main point of the question, how to store keys, you would do it the same way as any other cryptosystem, you are just storing more key data in this case. Standard methods include a high entropy unguessable password hashed with a KDF to generate key data, or encrypting the keys using an asymmetric algorithm. The strength of the KDF and asymmetric key size should be at least as strong as the expected security of the cascade. (256 to 768 bits with up to 3 AES candidate algorithms). In your example a password known to both parties is used to generate the keys, so there is no storage of keys, it is generated from hashing that password in some method that generates enough bits.

My personal recommendation for balanced speed and security would be to use AES128_CTR first then encrypt with Twofish256_OCB3. This requires 384-bits of key data, which can be generated using a SHA384 or an appropriate key derivation function, but it is better to use a strong random source if possible. Getting the keys to the recipient securely is a whole different problem.


Choosing finite field size in Shamir's Secret Sharing Scheme The Wikipedia article on Shamir's Secret Sharing says to that to have information theoretical security the splitting algorithm should be evaluated using finite field arithmetic on the field $\rm{GF}(p)$ such that $p>n,p>S$ where $n$ is the number of shares and $S$ is the information to be shared. It suggests that on the one hand $p$ should be large because an attacker knows that $S\in\mathbb{Z}/p\mathbb{Z}$. It also suggests that $p$ should not be too large because an attacker knows that as $p\uparrow$ $\rm{p}\{f(x)\bmod p = f(x)\}\uparrow$. How should one choose the best value of $p$ and be confident about choice?

Charles Karney's implementation splits $S$ into $i$ pieces such that $\forall \,i,\,S_i\in\rm{GF}(257)$. I do not understand a specific reason to use $p=257$ over any other prime number. For instance the elements $S_i$ could be stored in in an 8 bit value if $p=251$ was chosen.

Actually, you can do Shamir Secret Sharing over any finite field $GF(p^k)$, for any prime $p$ and any integer $k$.  If $k=1$, you have the $GF(p)$ field you mentioned; however it works on extension fields as well. We often pick $p=2$ and $k$ a multiple of 8; this makes everything nice even number of bytes (at the cost of doing our calculations in $GF(2^k)$).  Of course, this is a choice of convenience, you can make your own choice.

As for the size of $p^k$, well, $p^k > n$ is a hard requirement; you can't give out more shares than nonzero indicies available.  As for $p^k > S$, well, that's not actually a hard requirement; you can split up $S$ into several pieces (each piece no larger than $p^k$), and share each piece separately.  For example, if the secret is a 128-bit AES key, and you're using $p = 257$, you'd split up the key into 16 pieces, each from 0-255, and generate 16 independent polynomials, and give each share holder a point on each of those 16 polynomials.  Just remember: when generating the polynomials, the polynomial you pick must be selected independently of all the other pieces; otherwise you lose the security of the system).

As for not picking $p$ (or $p^k$) too large, well, Wikipedia is wrong there; Secret Sharing is informationally secure (assuming a randomly chosen polynomial); if someone has fewer than the threshold number of shares, then they learn nothing about the secret, and that holds no matter how large we make $p^k$.  I suspect someone took the discussion about Shamir Secret Sharing over the integers (which doesn't work, in part because the integers don't form a field, as there are elements without multiplicative inverses, and in part because it's impossible to select a random polynomial with a uniform distribution over the integers), and extrapolated the problems there to finite fields (which doesn't have those issues).


Collision resistance of composed hash functions Consider the following hash function

$H^{1\circ2}(x)=H^1(H^2(x))$

I have been asked to prove that if $H^1$ is CR,  $H^{1\circ2}$ will not generally itself be CR. I am assuming  $H^2$ is not CR, this is not explicitly stated. I have seen similar questions here but they always consider a double hash with a single function, not two.

I understand that by "not generally" or similar wording it is meant that there exists at least a case where $H^{1\circ2}$ is not CR. Admittedly however I thought that since $H^1$ is hashing $H^2(x)$, this makes the resulting hash function CR as well. Is this not always the case?

Suppose you have found a collision for $H^2$, ie a pair $(x_1,x_2), x_1\neq x_2$ such that $H^2(x_1)=H=H^2(x_2)$.

Now let $F$ be a deterministic function (like $H^1$?). Does
$$(F\circ H^2)(x_1)=F(H^2(x_1))=F(H)=F(H^2(x_2))=(F\circ H^2)(x_2)$$
yield anything interesting?


Establishing a shared secret over a unsecure channel Is it possible to establish a shared secret between two devices if the devices have no prior knowledge and no secondary secure channel to exchange information?

Assume a Dolev–Yao model for the communication channel. After searching for an answer I came across this but they use a secure secondary channel to exchange information.

If it is possible, then how?
If it is not possible is there a paper or theorem that say that says why it is not possible?

No if strictly they have no prior knowledge and no secondary secure channel to exchange information. Man in the middle attack will always be possible in this case because the two parties cannot authenticate each other. If they cannot authenticate, then even if they have a value at the end, the value may not be secret nor shared with the right party.


What's the industry standard for verifying phone number ownership? What's the industry standard for generating single-use SMS codes verifying phone number ownership?

I'm currently evaluating two main alternatives, both based on sending a verification code to that phone number via SMS. How would one properly generate such code?

Obtain an OS-generated random GUID and somehow shorten it to a human-friendly code, e.g. 6-digit number.
Use a incremented, stored sequence and obfuscate it deterministically into a human-friendly code.

With option 1 my main concern is how to shorten a GUID to something human-friendly while still preserving good entropy.

Option 2 allows uniqueness if the maximum sequence value is significantly larger than the expected code count, but it's fully deterministic and that could allow attacks based on the knowledge of several subsequent codes.

The SMS code is only used to verify phone number ownership. It's not a 2-factor authentication scheme and it's hardly authentication at all, since anyone with a working phone number is authorized to access the service behind it. The only reason for it is to prevent people from putting numbers they don't own and potentially have our service spam unrelated, unaware people with text messages.

UPDATE

The original question did not reflect the actual problem, which is verifying that an anonymously supplied phone number in fact belongs to the actual supplier.

Thanks for all the replies, I believe getting a few bytes from CSPRNG mod 10^n is the appropriate method.

I don't think there is any written 'industry standard', just as in any case when generating random numbers: Just use properly-seeded CSPRNG. Closest thing we have is TOTP/HOTP.

Both of your ideas are far more complex to get right from what TOTP/HOTP roughly does: Take CSPRNG, output 4bytes, truncate to 31bits, and take modulo 1000000 (Please note that TOTP/HOTP actually have bit more to it, refer to according rfc for details). This yields very small bias, which isn't a issue.

As SEJPM noted in his comment, SMS can be captured, and especially recently, some parties who used 'best recommendations' were hacked with SMS-reset of password. Therefore you should consider TOTP/HOTP, and SMS can be implemented as a variant of HOTP (which would allow you to check if one of previous tokens was reused).

So in short: neither 1 nor 2. Use properly seeded CSPRNG (/dev/urandom or CryptGenRandom can be used), then take 31-bits and modulo them to 1000000. Better yet, allow usage of HOTP/TOTP (which does basically same thing, without relying on channel security).


What (precisely) is a block cipher? If I follow the wikipedia or crypto.stackexchange definition, any simple XOR encryption where the key is as long as the plain text should qualify as a secure block cipher.

Now I thought what would happen if I just use this together with a block cipher mode of operation? After all, they should build a secure scheme with any secure block cipher. As you can probably guess by now, the outcome of this is nowhere near being secure. (Not even considering the small key space in this particular example, that could easily be fixed, but there are very obvious connections between the plain and the cipher text.)

So my question is: What is a block-cipher, so that it qualifies for use with any of the block cipher modes of operation?

A block cipher is (or tries to be) a pseudorandom permutation on a given space. Let $\mathcal{M}$ be the set of $n$-bit blocks for a given $n$. There are $2^n$ possible block values, and a permutation on $\mathcal{M}$ sends each block value to another value. There are $2^n!$ such permutations. A block cipher is a mapping from key values (in a given key space $\mathcal{K}$) to permutations on $\mathcal{M}$.

For instance, AES-256 is a block cipher which operates on 128-bit blocks and uses a 256-bit key. Each possible key value ($2^{256}$ possibilities) selects a permutation among the $2^{128}!$ of the space of 128-bit blocks (which has size $2^{128}$).

For the block cipher $\phi$ to have any practical value, it shall be easily computed: given a key $k$ and an input block $x$, applying the permutation $\phi_k$ selected by $k$ on $x$ takes a small amount of computing power. Usually, the inverse permutation is also easily computed: given $k$ and $y$, find $x$ such that $\phi_k(x) = y$.

The main security assumption on block ciphers is indistinguishability: for whoever does not know $k$, the permutation $\phi_k$ should behave as if it had been selected at random and uniformly among the $2^n!$ possible permutations of $\mathcal{M}$. This can be illustrated with the following experiment: suppose that I give two black boxes which compute, respectively, $\phi_k$ and on inputs $x$ of your choosing, and yields the corresponding output. I do not tell you the value of $k$. At any time, when you have sent $q$ requests ($q$ block values $x$ to encrypt), your goal is to predict the output of the box on yet another input $x$ that is distinct from your previous $q$ inputs. Since $\phi_k$ is a permutation, you know that the output will be different from the $q$ previous outputs, so there are $2^n-q$ possibilities. The block cipher is "secure" if you cannot predict the output correctly with probability substantially better than $1/(2^n-q)$.

(This "black box" model is a bit simplified; in fact, I should give you two black boxes computing $\phi_k$ and $\phi_k^{-1}$ respectively, and each of your $q$ request is for one of the boxes, at your choice.)

The "black box" model explains why a simple XOR is a very poor block cipher. If you define $\phi$ such that keys are also sequences of $n$-bits, and $\phi_k(x) = k \oplus x$, then a single request to the encryption black box allows recomputing $k$ (with $k = x \oplus \phi_k(x)$) and thus predict output for all other requests with 100% accuracy.

Terminology is the following:

Known Plaintext Attack: attacker obtains $q$ pairs $(x,\phi_k(x))$ but does not get to choose $x$ or $\phi_k(x)$.
Chosen Plaintext Attack: attacker obtains $q$ pairs $(x,\phi_k(x))$ where he can choose the $x$ values at will.
Adaptive Chosen Plaintext Attack: a CPA attack where the attacker is allowed to think a lot between each two requests; meaning that when he selects the next request $x$ to send to the black box, then he can do so after due inspection of the previously obtained outputs.
Chosen Ciphertext Attack: attacker obtains $q$ pairs $(\phi_k^{-1}(y),y)$ where he can choose the $y$ values at will.
Adaptive Chosen Ciphertext Attack: a CCA attack where the attacker can think between any two successive requests.

The "gold standard" is called IND-CCA2 which means "indistinguishable from a random permutation against adaptive chosen ciphertext attacks".

(The description above is slightly simplified; true formal exposition would use Turing machines and a game between a challenger and a prover; but it should give you the intuition.)

There are limits to the indistinguishability. Indeed, if you allow $q$ to raise up to $2^n-1$ then the notion ceases to be interesting; if the attacker can send requests for all possible block values except one, then he can predict the missing one with probability 1: it is the one output that he did not get yet. Also, indistinguishability cannot hold beyond exhaustive search on the key space: if the attacker can try all possible key values, then he can look for a match with the outputs he got. Once he gets the key, he can predict with probability 1.

It is customary to study algorithms where keys are sequences of $r$ bits (e.g. $r = 256$ for AES-256). The "exhaustive search" attack has average cost $2^{r-1}$ (the attacker needs, on average, to try half the keys before hitting the right one). So, the security of any block cipher tends to break down when the attacker is "allowed" too many requests and/or too much computing power.

In practice, for a block cipher with $n$-bit blocks and $r$-bit keys, we consider an attack to be "academically successful" if it can predict the black box output with the following conditions:

Attacker can send $q$ requests to the encryption or decryption box with $q \leq 2^{n-1}$ (attacker can obtain "half of the code book").
Attacker can spend enough CPU to compute $2^{r-1}$ evaluations of the function.
Attacker also has access to $2^{r-1}$ bits of very fast RAM.
Attacker's probability to predict the next output is at least $3/4$.

With $2^{r-1}$ evaluations of the function, attacker's success with the simple exhaustive search and $2^{n-1}$ requests will be $1/2+2^{-(n-1)}$ (50% chance of having found the key through the search, and, if not, the knowledge that the next output will be in the code book half that the attacker did not get with his $q$ initial requests). Hence the $3/4$ criterion: attacker must be able to do better than this generic attack.

For instance, if you consider 3DES: block size is $n = 64$, and key size is $r = 168$ (the standard says "192 bits" but the algorithm simply ignores 24 of these bits, so for the cryptographer the key size is 168 bits). There is a known "meet-in-the-middle" attack which requires $2^{62}$ bits of storage (for $2^{56}$ words of 64 bits), computational effort equivalent to about $(2/3)·2^{112}$ evaluations of 3DES, and only 2 known plaintexts. This attack cannot be implemented with existing technology (the storage requirement would be quite expensive, since we are talking about half a millions of terabytes of fast RAM; and the CPU requirements is simply completely out of reach because it would requires way more energy than what Mankind produces as a whole). Yet it counts as a break. In that sense, 3DES is "academically broken".

Modes of operation turn a block cipher into something which can encrypt and decrypt messages of almost arbitrary length, not just single block values. Each mode of operation has its own requirements, in particular with any Initialization Vector. For instance, with CBC, in a "black box" model similar to what is described above, the encryption system must generate IV values randomly, uniformly, with values which are not predictable by the attacker (the BEAST attack on SSL/TLS builds on IV predictability, in the sense that the attacker can know the IV before choosing his plaintext for the next request).

As a generic rule, most modes of operation run into trouble when the amount of encrypted data exceeds about $2^{n/2}$ blocks. This is the threshold at which a pseudorandom permutation begins to behave differently from a pseudorandom function (a permutation is injective: it won't give you the same output with two distinct inputs; whereas a random function, on average, is not injective). This is why AES was defined with 128-bit blocks, as opposed to 3DES 64-bit blocks: to give us enough room in practical situations.


RSA message encryption question I'm very new to cryptography, I wanted to know what exactly do I have to do to encrypt a three-letter message using RSA? for example if I wanted to encrypt this message $M= \text{HCP}, p=11 q=13$.
Do I have to change the letters into numbers? ($H = 7, C=2, P=15$) and then encrypt each letter alone? or add/multiply them and encrypt them all at once?

To encrypt a message, in RSA or other encryption schemes, we convert (encode) the messages into bits/bytes arrays that are dependent on the scheme in an invertible way!
If you consider only the English letters, with $A=0,\ldots, Z=25$ then you can make the encoding of a sequence of letters $m_0,m_1,\ldots,m_t$ with
$$m = \sum_{i=0}^t 26^i \cdot m_i$$ This method is common way to encode, remember the binary encoding? A similar idea applied here, and note that the decoding is unique. Numbers are easily converted into octets (bytes) in a computer and usually byte array is processed, some schemes use words, too.
You are going to have some problems now or future;

You cannot have $m \geq n$ where $n$ is the RSA modulus. If your messages are longer than the RSA modulus, then you need to split your message into parts.
In your case, $p=11,q=13$ then $n = 143$. This can only encrypt one letter at a time. Use larger modulus, or encrypt one by one!.

We don't use RSA for encryption, we rather use it for signatures and for hybrid encryption like RSA-KEM.

RSA encryption needs proper padding like PKCS#1v.4 or OAEP to be secure against the attack, see Twenty Years of Attacks on the RSA Cryptosystem.

RSA Signing is Not RSA Decryption

For signature, one must use the Probabilistic Signature Scheme (PSS).

The padding, is not enough to be secure, one needs to have constant time implementation against the side-channel attacks.

To see how real RSA encodes see rfc8017


Detecting the amount of entropy used for random number generation I am majoring in computer science but I have recently become obsessively interested in information theory and cryptography. I have read some articles about entropy and random number generators.

I find few algorithms online to generate 128-bit entropy supported random number generator. As I can tell from other discussion in this website that random number generator does not change the entropy.

It seems that N-bit-entropy-support random number generator only depends on how many bit of initial state supported by the algorithm. If my understanding is correct, I wonder if it is possible to figure out the how many bit of entropy supported by any given random number generator if we don't know the algorithm (like testing it in a black box)?

Suppose we have some seed-extensible PRG, meaning, it can operate on seed of any length $l$, and extracts a pseudorandom string in time polynomial in $l$ and the output length. What you are asking is: given a pseudorandom string produced by this PRG, can I find the input length $l$ that was chosen?

The number of bits of entropy fed as seed to a cryptographic pseudorandom generator can be seen as the security parameter $\lambda$ for the system. The security of your PRG (assuming it is a cryptographically strong PRG) states that any adversary that runs in time polynomial in $\lambda$ cannot distinguish the pseudorandom output from a random string. In particular, if it cannot distinguish it from a random string, it cannot tell anything at all about the input length that generated it. Therefore, either you have chosen $\lambda$ so that breaking the security of the PRG takes too much time for the adversary, and he will in this case not be able to tell the seed length either, or you have set up $\lambda$ to be a too small value, in which case the adversary will indeed find out the seed length, but also break the security of your PRG.


Shamir Secret Sharing - P not prime I was wondering what will happen if I use the Shamir Secret Sharing scheme with $P$ not being a prime, let's say it is $255$. An adversary which holds $k'$ shares ($k'<$ threshold $k$  ) can attack the scheme and find the secret $S$? If he can attack the scheme, how the attack works?

There are two problems that arise when you attempt to use a composite $P$:

The first is that the attacker can gain some information about the shared secret; he can't reconstruct the entire secret, however the goal of Shamir Secret Sharing is that the attacker obtains no information.  For a simple case, consider a threshold $k=2$ case where the attacker has the single share $(3, 0)$.  That is, the attacker knows that the polynomial is a linear equation $ax + s$, with $s$ being the shared secret, and with $3a + s = 0 \bmod 255$.  What the attacker can immediately deduce is that, whatever the shared secret is, it must be a multiple of 3 (because $3a + s$ is a multiple of $3$); this happens because $3$ is a divisor of $255$.

The second issue is that the legitimate reconstructors, with $k$ different shares, cannot necessarily uniquely reconstruct the secret.  For an example, consider that case $k=2$ and we have the two shares $(1, 0)$ and $(4, 0)$.  In this case, we know we have a linear equation with $1a + s = 0 \bmod 255$ and $4a + s = 0 \bmod 255$.

Unfortunately, there are 3 possible equations that fit this criteria:

$$0 x + 0 $$

$$85 x + 170$$

$$170 x + 85$$

It is easy to see that plugging in 0, 4 into each of these equations yields the values implied by the shares.

Hence, while we know that the secret is one of $\{0, 85, 170\}$, we have no idea which one it is.


Existing dictionaries of popular words to help solve a random substitution cipher? I'm trying to find faster ways to solve this:
http://cryptogram.org/solve_cipher.html

Actually lists of common words are good, but they are often limited to 1000 words.

I found this, but I'm not sure which one to use, but the word list still seems too large.

Do you know lists of 10k, 20k, 30k words, or tools that sorts words by popularity?

One nice way to generate a word list is distilling it from a large amount of texts.

There are a few interesting effects with this creation method:

The word frequency depends a lot on the chosen texts. For example when feeding it wikipedia the language is rather formal, and common every-day words are pretty rare. It might be interesting to compare Simple Wikipedia with the normal wikipedia
For some texts you also get common misspelling of words. That's nice for some uses, but bad if you want to use the list for spell checking. Should be fine in your case

I found a nice wordlist created from the english wikipedia which lists the words ordered by frequency. So you can truncate it if you want fewer words. Unfortunately it doesn't contain the frequency of each word, but since the source is available, adding this feature shouldn't be hard.


Are there Cryptography certifications variants of CISSP? Are there Cryptography certifications variants of CISSP ( Certified Information Systems Security Professional)? Like a CISSP exams, but only for cryptography?

The EC Council offers some certification although I have no idea who they are. I think CISSP implies you know about cryptography because you get examined on it although I don't know the depth they go into.

Other than that a Uni degree in security or cryptography would fit the bill, or a certificate from Coursera or related services, although that's of course not as prestigious as CISSP.


Encryption / Decryption using AES-256 GCM I am new in cryptography and I am facing some complications in encryption-decryption. I am trying to use AES-GCM with a 256-bit AES key and a 96-bit nonce. I use an open source project (Vault) to create the encryption keys. Vault can encrypt/decrypt using the generated key.

The question is what should I have to encrypt data in a different application using the key generated by Vault (so Vault can decrypt afterward)? Is having only the encryption key enough, or should I export more data from Vault such as IV?

Thanks in advance if you have some advice and hope my question is clear

Exporting the key is sufficient.

With GCM (and block modes in general), the key and the nonce play very different roles.

The key is secret; it is known by the encryptor and the decryptor and no one else.  And, you can use the same key to encrypt multiple messages.

The nonce (or IV) need not be secret; common practice is to send it along with the encrypted message.  However, one limitation with GCM is that, while you can encrypt multiple messages with the same key, you must use a different nonce for each message that you encrypt with that same key.  And, typically, the encryptor selects the nonce when it encrypts the message.

Because of this, it doesn't make sense to ask Vault which nonce it expects to use to decrypt; the encryptor selects it (and if Vault will be able to decrypt several messages with the same key, it'll have to use different nonces anyways).


What is multi-prime RSA (RSA-MP)? I found some related question but no real explanation of what it is and when and why to use it. What are the benefits and downsides and is it recommended?

Multi-prime RSA is simply using more than 2 prime numbers in generating RSA public key - The public modulus would have more than 2 factors.

We use it because it has more efficient key-generation and decryption/signing operation, which is the benefit of it.

The downside being it might be easier to factor a multi-prime RSA public key than a dual-prime one.

It's neither recommended or recommended against, it's simply an possible option without any endorsement.


How to compute the dataset size required by dieharder tests? I am trying to use the dieharder random number test suite.
However, this suite requires massive amount of data (this paper claims 228GB for no rewinding for every test) for most of the tests. I'd like to understand how rewinding is implemented and to know how much data is required for each test. It seems related to the tsamples value but I cannot find an exact correlation.
For example, if I generate 400MiB of data using dd if=/dev/urandom of=random.dat bs=1M count=400, this produces the following (cropped) output:
$ dieharder -a -g 201 -f random.dat
#=============================================================================#
#            dieharder version 3.31.1 Copyright 2003 Robert G. Brown          #
#=============================================================================#
   rng_name    |           filename             |rands/second|
 file_input_raw|                      random.dat|  6.38e+07  |
#=============================================================================#
        test_name   |ntup| tsamples |psamples|  p-value |Assessment
#=============================================================================#
   diehard_birthdays|   0|       100|     100|0.70238534|  PASSED
# The file file_input_raw was rewound 1 times
      diehard_operm5|   0|   1000000|     100|0.74169241|  PASSED
# The file file_input_raw was rewound 2 times
  diehard_rank_32x32|   0|     40000|     100|0.03164866|  PASSED
# The file file_input_raw was rewound 2 times
    diehard_rank_6x8|   0|    100000|     100|0.18168084|  PASSED
# The file file_input_raw was rewound 3 times
   diehard_bitstream|   0|   2097152|     100|0.59056568|  PASSED
# The file file_input_raw was rewound 5 times
        diehard_opso|   0|   2097152|     100|0.19175240|  PASSED
# The file file_input_raw was rewound 6 times
        diehard_oqso|   0|   2097152|     100|0.67542036|  PASSED
# The file file_input_raw was rewound 7 times
         diehard_dna|   0|   2097152|     100|0.04906220|  PASSED
# The file file_input_raw was rewound 7 times
diehard_count_1s_str|   0|    256000|     100|0.80349572|  PASSED
# The file file_input_raw was rewound 8 times
diehard_count_1s_byt|   0|    256000|     100|0.43003125|  PASSED
# The file file_input_raw was rewound 8 times
 diehard_parking_lot|   0|     12000|     100|0.07270933|  PASSED
# The file file_input_raw was rewound 8 times
    diehard_2dsphere|   2|      8000|     100|0.92548415|  PASSED

I assume that dieharder just loops over the file, keeping its pointer position when jumping to the next test and that The file file_input_raw was rewound N times is just the total count that the pointer reached the end of the file.

I'll be so bold as to say that no one knows for sure how much data you really need. There is no guidance on the homepage, the manpage and this thread from Duke is equally unspecific. Anecdotal evidence suggests that a 'few' GB will return a sane PASS/FAIL answer, but there will still be rewinds. For a 4 GB /dev/urandom test:-
...snip
# The file file_input_raw was rewound 43 times
      rgb_lagged_sum|  27|   1000000|     100|0.75608263|  PASSED
# The file file_input_raw was rewound 46 times
      rgb_lagged_sum|  28|   1000000|     100|0.88574962|  PASSED
# The file file_input_raw was rewound 49 times
      rgb_lagged_sum|  29|   1000000|     100|0.69532845|  PASSED
# The file file_input_raw was rewound 52 times
      rgb_lagged_sum|  30|   1000000|     100|0.93874399|  PASSED
# The file file_input_raw was rewound 55 times
      rgb_lagged_sum|  31|   1000000|     100|0.59282678|  PASSED
# The file file_input_raw was rewound 58 times
      rgb_lagged_sum|  32|   1000000|     100|0.88988310|  PASSED

58 times!
In your case (input file), a rewind is just that; start again from the beginning. Eight rewinds is good. I've seen 1849 rewinds. Honestly I can't understand the reasoning behind that, as all it does is retest what's been tested. All we know for certain is that Dieharder uses a lot. Your paper and my research shows that a free run of Dieharder (with no rewinds) needs approximately 225 - 250 GB! Notice that $58 \times 4 \text{GB}= 232 \text{GB}$.
There are other tests though. A more common test in the TRNG scientific literature is NIST's Statistical Test Suite, (SP 800-22). It's sample requirements are much more predictable.
And now a warning. You have to resist manipulating any randomness tests in order to get a PASS. Tweaking test parameters or selectively choosing individual tests to produce your expected result is dangerous, as a random sample is random no matter how you test it. From the manpage:-

...where a file that is too small will "rewind" and render the test results where a rewind occurs suspect.

My version 3.31.1 will not allow the number of p samples to be changed via the -p switch.


Difference between one-way encryption, Transparent data encryption (TDE) and data encryption What is the main difference between one-way encryption, Transparent data encryption (TDE) and data encryption? If one needs to store passwords or credit card details in the DB, which one is best to use?

What I have understood from my search is that an example of one-way is hash, in this case is the password encrypted at storage or just hidden from the DBA? And that with TDE the data is encrypted at storage only, so is it more applicable to use one-way encryption rather than TDE to hide details from the DBA/users?

You are right that "one-way" thing is hash function, and in fact, it's not encryption at all! Password hashing is different from data/file hashing in that data/file hashing algorithms like SHA-256 are deterministic and (supposedly) efficient; whereas password hashing is in practice non-deterministic so as to deter various types of precomputation attacks.

The difference you'll encounter with transparent data encryption and data encryption, is that TDE don't need you to rewrite your application to enjoy the benefit brought by encryption, where as data encryption on its own, requires processing data using cipher functions. Hence the name "transparent" data encryption.

That's all you have to know for now, you're welcome to learn more if you can get your head around it.


Tackling encryption problems with "Zipf's law"? I am new to cryptography and was wondering if it would be possible to semi-reliably "decrypt" an encrypted message by using the statistical distribution of symbols (/letters/numbers) in the encrypted message in accordance with Zipf distribution.

https://en.wikipedia.org/wiki/Zipf%27s_law?

If "symbols" were "recycled" (for example, if x = 102023 , then a = 102023 later)  then this would not be possible, right? If "symbols" are not "recycled", is the code very weak?

No, it is not possible to semi-reliably "decrypt" an encrypted message by using the statistical distribution of symbols, if some modern encryption scheme is used, and its secret/private key does not leak. Modern encryption is practically immune to known distribution or other characteristic in the plaintext.

The goal of modern encryption, that it reaches in practice, is that given the ciphertext, but lacking the key (or the private key for public-key encryption), the only thing that can be determined about the plaintext is its length (and then perhaps, only the order of magnitude of that).

Modern encryption does not create a one-one match between symbols in plaintext and ciphertext (as is the case for monoalphabetic substitution, or Electronic CodeBook); that indeed would be a weakness.


Proofs of collision resistance by reduction I'm looking for examples of a proof by reduction. For example:

Let $A=(Gen, H)$ be a hash function. We define a new Hash function $A'=(Gen',H')$ with $Gen=Gen'$ by $H'_s(x)=H_s(H_s(x))$.
It should be shown that if $A$ is collision resistant, then $A'$ is collision resistant too.

I am  not  looking for a solution for this question.
I'm looking for an idea of how to construct a reduction so that I can solve this problem on my own.

When you try to reduce the security of one primitive (H') to the security of another primitive (H), you assume that there exists an adversary that could break H'. Then you show that existence of said adversary implies an adversary against H by describing an algorithm (the reduction) that uses the adversary to break H.

as a very simple example, consider the hash function $H$ and the hash function $H'(x) = H (x \oplus 1^{|x|})$ (with $\oplus$ being XOR and $1^{n}$ denoting the string of $n$ ones).

Now assume there exists an adversary $\mathcal{A}$ against the collision resistance of $H'$, i.e. there exists a ppt algorithm $\mathcal{A}$ that on input $s$ (and potentially a security parameter) will output $x$, $x'$ such that $H'(x)=H'(x')$ (with non-negligible probability).

Now your reduction needs to transform such a collision into a collision for $H$. If you look at how $H'$ is constructed, you can easily see that this can be done by computing $y = x\oplus 1^{|x|}$ and $y' = x'\oplus 1^{|x|}$ and outputting $y,y'$.

So your reduction is the algorithm that runs $\mathcal{A}$, flips all the bits in $\mathcal{A}$'s output and returns it. You can easily verify, that this reduction is successful whenever $\mathcal{A}$ is successful. As $H$ is collision resistant, the probability that $\mathcal{A}$ is successful must therefore be negligible and thus $H'$ is collision resistant.

So the problem you need to solve for your case is basically the question "How can I turn a collision of $H'$ into a collision of $H$?" When you think a moment about the way $H'$ is constructed, I am sure you will see an obvious way to do that.


Security of cloud computational protocols in UC Framework? The universal composability allows one to the analyze security of cryptographic protocols . But it does have some gaps when it comes to analyzing few protocols especially two party cases when there is no honest majority players

Now when it comes to protocols designed for cloud computing, where few parties outsource computations to a service provider.  How do we prove the security of such protocols ?

Trivial example is Alice encrypts all her data using FHE schemes and outsources to Sally . Sally should now compute any function on the encrypted data requested by the Alice.

Notice that this simple case is different from two party secure function evaluation.

Now more complex protocols would be when Alice, Bob are two users who wants to execute some function on the shared data outsourced to Sally. So how do we prove security of  protocols designed for such functionality?

I think it is still possible to use UC in this case.

Recall the setup for the UC framework. We have an ideal world and a real world. There are parties $P_1,\dots,P_n$ in each world and an environment $\mathcal{Z}$ in each. In the real world we have the adversary $\mathcal{A}$ while in the ideal world, we have an ideal functionality $\mathcal{F}$ and a simulator $\mathcal{S}$. In the real world, the parties run some protocol $\pi$ while $\mathcal{F}$ should compute the same functionality as $\pi$ in the ideal world and be secure by definition (basically it is a trusted 3rd party). See the graphic below (taken from Martin Geisler's PhD thesis)

So, in your case, you have 3 parties. $P_1=\text{Alice},P_2=\text{Bob},P_3=\text{Sally}$. I'm not going to mess with specifying the protocol $\pi$. In the ideal world we can have a very simple setup. $P_1$ and $P_2$ submit their inputs (in plaintext over a private channel) to $\mathcal{F}$ and $P_3$ issues commands to $\mathcal{F}$ with what to do with those inputs (e.g., "compute the sum", etc).

In the real world $\mathcal{A}$ is basically $P_3$, so we assume that anything $P_3$ knows, $\mathcal{A}$ also knows. That information is then leaked to $\mathcal{Z}$. Then in the ideal world, you'll have to construct $\mathcal{S}$ in such a way that $\mathcal{Z}$ cannot distinguish between the two worlds. How exactly you do this will depend greatly on $\pi$.

As an example, let's say we are just computing the sum of the inputs using Paillier. In $\pi$, $P_1$ and $P_2$ might encrypt their inputs with the Paillier public key (who knows the private key is up to you, but it shouldn't be $P_3$) and send them to $P_3$. Then, if $P_3$ decides to, it will homomorphically sum the values and send the resulting ciphertext back to $P_1$ and $P_2$. To make it general, we'll just let $\mathcal{Z}$ provide $P_1$ and $P_2$ with their inputs and with $P_3$'s choice.

In the ideal world, $P_1$ and $P_2$ pass their inputs (from $\mathcal{Z}$) to $\mathcal{F}$. Then, if $P_3$ tells $\mathcal{F}$ to compute the sum, $\mathcal{F}$ does so. Furthermore, it will leak an encryption (using the paillier public key) of the result to $\mathcal{S}$ who passes that to $\mathcal{Z}$. You can also have $\mathcal{S}$ leak encryptions of the inputs to $\mathcal{Z}$ in a similar manner.

In both worlds, $\mathcal{Z}$ sees encrypted inputs and an encrypted output (if $P_3$ decides to allow the computation). Thus the two worlds are indistinguishable (assuming IND-CPA of the cipher) and the real world is as secure as the ideal world.


Is ECB mode safe to use with RSA encryption? Firstly, bear with me, I'm relatively new to cryptography. In a recent static analysis scan of our application, one of the findings complained that we are using ECB:

  A mode of operation of a block cipher is an algorithm that describes how to repeatedly apply a cipher's single-block operation to securely transform amounts of data larger than a block. Some of the modes of operation include ECB (Electronic Codebook), CBC (Cipher Block Chaining) and CFB (Cipher Feedback).  ECB mode is inherently weak, because it results in the same ciphertext for identical blocks of plaintext. CBC mode does not have this weakness, making it the superior choice.

We are using ECB with RSA.  Our understanding is that RSA doesn't support anything other than ECB as it doesn't permit a block size bigger than the size of the key's modulus, and therefore would only ever encrypt a single block (or throw an exception if breaching block size).   Our suspicion therefore is that the static code analysis tool is searching for 'ECB' in our code base irregardless of the crypto algorithm used.

Given our choice of an RSA crypto algorithm, is there an inherent weaknesses using ECB mode?

It is highly misleading to call how RSA Encryption is used as 'ECB mode'.

With ECB mode, we break the plaintext into N bit segments, and send each one through the block cipher separately.  The block cipher is deterministic, and so if two plaintext blocks happen to be the same, so will the corresponding ciphertext blocks.

Now, with RSA encryption, we take the short message, and some randomness, stir them together (using a padding method), and send that through the RSA primitive, resulting in the ciphertext.  If we encrypt the same message again, well, we'll stir in different randomness, resulting in a different looking ciphertext.  Hence, we avoid the problems inherent with ECB mode (and thus it is rather inappropriate to call what we do with RSA 'ECB mode').

Now, some closing comments:

The above assumes that you are using a known-good RSA padding method, such as OAEP.  If you aren't, and are instead using 'textbook RSA' (which is just to take the message, interpret it as a large integer, and send that to the RSA primitive), then there are a number of security problems you can run into, in addition to determinism.  If that is the case, you definitely need to fix it.
Someone could devise a CBC-type mode for doing RSA encryption (by breaking up the message into separate blocks, and doing an "add mod N" of the ciphertext of one block to the plaintext of the next).  We never do so, because of efficiency - if we ever need to RSA encrypt a long message, a far more efficient approach would be to pick a random (say) AES key, RSA encrypt the AES key, and then AES encrypt the actual message with the AES key.  Because AES is far more efficient than RSA, this is faster (and we retain the only-someone-with-the-private-key-can-decrypt property of pure RSA).


Why use variable p, q, g for Diffie-Hellman? In the book Cryptographic Engineering, it is said that fixing p, q, g for a key negotiation protocol based on DH is a bad idea (page 228 1st ed).

But allowing for flexible p, q and g requires a lot of checks and protocol tricks (e.g. requesting a lower bound on p / q)

Why do we need this flexibility? Do we add something essential with selectable parameters?

The following are the reasons I came up with for not using static/standard DH parameters.

You might not trust the person who generated the group. They could have generated a group with a trapdoor (e.g., group order is smooth) which would allow them to break the resulting system.

The longer you use the same group, the more time an attacker has to attack the group.
E.g., if millions of people are using the same group, millions of times a day and the attacker has a database of terabytes of pairs $(g^x,x)$, they may be able to break a key establishment.

In DH, remember we must choose a random exponent. We have seen a number of recent cases were random number generators weren't as random as originally thought (e.g., Debian OpenSSL RNG). Not reusing the same group could potentially thwart bad RNGs (though if the new group is generated using the same RNG...).

You should remember though that there are also issues with generating new groups all the time, so you have to weigh the tradeoffs. I wouldn't think that there is a clear, definitive winner for how to do it that applys to all circumstances, though when done correctly either way is secure. If the group parameters were chosen by someone I trusted (e.g., NIST), then I'd personally just use the parameters they suggest.
Why would I still recommend using a standard group
Even given the potential problems I listed above, I personally would still use a standardized group generated by someone I trust because:

If they have generated it properly, you will know the order of the (sub-)group and know that it isn't smooth.
The probably of #2 is still very, very small
If your RNG is bad, there are probably so many other issues that even changing the group won't save you.
The possibility of you not checking things exactly right when generating your own group is pretty high.
Generating a new group will add significant computation time with little added security.


Hill Cipher how to encrypt and decrypt when both "I" and "J" are in plaintext In Hill Cipher, let's assume the key is "KEYWORD" and I want to encrypt "JUICE", so after encryption, I get "GXLBWU", and when decrypt ciphertext I get back "IUICEX" not "JUICE". So my questions are:

So how do a receiver know where to put "J" after decryption?
Does he just have to guess it?

"KEYWORD" is a weird format for a Hill cipher, aren't you confused with the Playfair cipher? There you work with a 5x5 matrix where I and J are often conflated into I (as 26 is one too big) and the key-square is filled with a key word.

This is what you seem to be describing.

In the Hill cipher, the key is a 2x2 matrix over some $\mathbb{Z}_n$, often with $n=26$, which is inconveniently non-prime, not a word. No I and J merging are needed there; we can choose any $n \ge 26$ and add extra characters (like spaces) for convenience.

Back to your question, which I think is probably Playfair: the convention is to remove final padding (often X or Z), needed to create bigrams and then context determines whether a received I means I or J. Spaces also need to be filled in, or maybe X is used for that too. It's one of the disadvantages of hand systems with built-in limitations like this.


SHA3 the Left & Right Encode Functions In this paper (Section 2.3.1, Pg.5), I came across the left_encode and right_encode functions, and I have some questions about the functions:

What is meant by the base256 encoding of an integer?
Do $x_1,x_2,\ldots,x_n$ all contain the same bytes, or do they contain different bytes split across them?
Does enc8 effectively mean little-endian?
After theenc8 bytes are concatenated, are they transformed back into a number or binary or...?

What is meant by the base256 encoding of an integer?

It splits an integer $x$ into bytes, a byte is 8-bit that can represent 256 numbers. That is why actually $n$ is set as the smallest positive integer satisfying $2^{8n} > x$. The bytes are little-endian encoded.

  Do $x_1,x_2,\ldots, x_n$ all contain the same bytes, or do they contain different bytes split across them?

No, the x is split into bytes.

  Does enc8 effectively mean big-endian?

A byte has no little-endian or big-endian encodings. Here, it is just a byte encoding but in reverse. Second steps do the little-endian. In the end, all bits are reversed. See a bigger example below.

  After the enc8 bytes are concatenated, are they transformed back into a number or binary or...?

It is a byte array and in general in cryptographic implementations, the programming codes are processing with byte arrays. The output of the hash function will be byte to. It is up to you to convert into hex or base64.

A nice example from cryptologie.net

left_encode:

            0001 0000 | 0011 0001 | 0111 1110 input
            0111 1110 | 1000 1100 | 0000 1000 value reversed
1100 0000 | 0111 1110 | 1000 1100 | 0000 1000 length encoded. the size 3 in reverse

right_encode:

0001 0000 | 0011 0001 | 0111 1110               input
0111 1110 | 1000 1100 | 0000 1000               value reversed
0111 1110 | 1000 1100 | 0000 1000 | 1100 0000   length encoded


What is matrix branching program? Recently I am reading something about order-revealing encryption (by Boneh at al. in EuroCrypt 2015) and encountered "matrix branching programming". It seems like it took me forever to understand this. Anyone can help me with this problem. better have a concrete example in explanations

For an easy to grasp explanation, you can have a look at the talk Obfuscation I at the Cryptography Bootcamp by Amit Sahai. Here's a link to youtube. In this context he also explains matrix branching programs, which are also used in the construction of indistuingishability obfuscation. He starts explaining them at the minute 40.

In short: You're given $2k$ of invertible matrixes $A_{x,y}$ with  $y\in\{0,1\}$, $x=0,1,\dots,k-1$. For an (previously fixed) input of $n$ bits $b_i$ ($i={0,1,\dots,n-1}$), ($k$ should be a multiple of $n$), you multiply them like this:
$$\prod_{x=0}^{k-1} A_{x,b_{x \text{ mod }n}}$$

And if you evaluate it honestly (following this rule), you either get the identity matrix or a different, fixed matrix $B$, and this is equivalent to an output of a single bit of the function, which is realized by this matrix branching program.

A nice feature is that you can realize all programs in $NC^1$ this way in poly sized matrix branching programs. But I really suggest watching the video, even if just for the matrix branching part.


Efficiency of oblivious algorithms vs non-oblivious algorithms? Recently, plenty of researchers are looking at designing efficient data-oblivious algorithms. Roughly speaking, an algorithm is said to be data-oblivious if its data access patterns are independednt of the input i.e. the data access pattern of the algorithm does not leak any information about the input of the algorithm. Few of the algorithms already looked at include sorting, BFS, minimum spanning tree and convex-hull. These oblivious algorithms have various applications for the cloud and efficient secure computation. My queires regarding the same are as follows:

Is ORAM a generic method to transform any non-oblivious algorithm to its oblivious counterpart?
Is it always possible to construct a oblivious algorithm with the same asymptotic complexity as that of its non-oblivious counterpart? Please provide me with pointers to works which discuss on the same.

Yes. There is an $\Omega(\log n)$ lower bound on ORAM. Therefore directly using ORAM to transform a non-oblivious algorithm to oblivious algorithm would incur a logN overhead. It is an open problem to design an ORAM matching the lower bound.
No. There exists algorithms that do not have more efficient solution. As an apparent example, accessing a memory cell out of N cells requires $O(1)$ time in non-oblivious case but $\Omega(\log n)$ time in oblivious case, implied by the lower bound. I cannot think of more "useful" algorithms since there are not many lower bound proven.

I'm posting two relevant citations:

Nicholas Pippenger and Michael J. Fischer. Relations Among Complexity Measures. Journal of the ACM, Vol. 26, No 2, April 1979, pp 361–381. ACM PDF
Oded Goldreich and Rafail Ostrovsky. Software protection and simulation on oblivious RAMs. Journal of the ACM, Vol. 43, No 3, May 1996, pp 431–473. doi:10.1.1.44.8961 ACM PDF

[follow up]

Adding more relevant (but incomplete list of) papers.

Goodrich, Michael T. "Randomized shellsort: A simple oblivious sorting algorithm." In Proceedings of the twenty-first annual ACM-SIAM symposium on Discrete Algorithms, pp. 1262-1277. Society for Industrial and Applied Mathematics, 2010.
Mitchell, John C., and Joe Zimmerman. "Data-oblivious data structures." In LIPIcs-Leibniz International Proceedings in Informatics, vol. 25. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2014.
Zahur, Samee, and David Evans. "Circuit structures for improving efficiency of security and privacy tools." In Security and Privacy (SP), 2013 IEEE Symposium on, pp. 493-507. IEEE, 2013.
Goodrich, Michael T., and Michael Mitzenmacher. "Privacy-preserving access of outsourced data via oblivious RAM simulation." In International Colloquium on Automata, Languages, and Programming, pp. 576-587. Springer Berlin Heidelberg, 2011.
Blanton, Marina, Aaron Steele, and Mehrdad Alisagari. "Data-oblivious graph algorithms for secure computation and outsourcing." In Proceedings of the 8th ACM SIGSAC symposium on Information, computer and communications security, pp. 207-218. ACM, 2013.
Nikolaenko, Valeria, Stratis Ioannidis, Udi Weinsberg, Marc Joye, Nina Taft, and Dan Boneh. "Privacy-preserving matrix factorization." In Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security, pp. 801-812. ACM, 2013.
Keller, Marcel, and Peter Scholl. "Efficient, oblivious data structures for MPC." In International Conference on the Theory and Application of Cryptology and Information Security, pp. 506-525. Springer Berlin Heidelberg, 2014.
Wang, Xiao Shaun, Kartik Nayak, Chang Liu, T. H. Chan, Elaine Shi, Emil Stefanov, and Yan Huang. "Oblivious data structures." In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pp. 215-226. ACM, 2014.


Is there a crytographic scheme for "ciphertext consistency verification"? I a problem that essentially boils down to the following:

There is raw data, D, encrypted with key K (call its encrypted form E). The same raw data, D, is also encrypted with key K' (call its encrypted form E'). Given E and E', and also secure hashes of K and K', it should be verified that D was properly encrypted both times.

The use case of this would be performing client-side encryption and uploading the encrypted data. If the encryption key is changed, the server should validate that the data has not been corrupted. Is there some sort of schema that fits what I am describing? I intentionally did not specify the encryption or hashing algorithms as I assume that those would be dependent on the schema, if one exists. Thanks for the help, and sorry if this is a stupid question - I am no cryptography expert.

Well, I've come up with one potential answer.  I'm not sure how practical it is, however it does indicate that their exists a solution (and maybe a better solution can be found).

After writing it up, I decided that it's not a very good answer (likely going way over your head, and certainly not something you should try to implement yourself), however I'll keep the answer just in case someone else could improve o it.

It is based on "ECElGamal on a pairing friendly curve".

In ECElGamal, we work on a curve with order $n$ and well-known generator $G$; for a secret key, we select a random value $k$ between 1 and $n-1$; we compute the public key $K = kG$ (which we can publish).

To encrypt a message to us, someone first encodes their message into an curve point $D$ somehow (it doesn't really matter how, except it needs to be invertible), and selects a random value $r$ between 1 and $n-1$, and then generates a ciphertext that consists of the two points $rG$ and $rK + D$ (remember, $K$ is our public key).

Then, to decrypt a message that consists of two points $A, B$, we compute $B - kA$ (using our private key $k$), if $A = rG$ and $B = rK + D$, the result of this is $B - kA = rK + D - k(rG) = rkG + D - krG = D$; hence, we get the encoded curve point (and so we then convert the curve point $D$ back into the original message).

Now, suppose we publish a ciphertext $(A, B)$ encrypted with public key $K$, and then publishes a ciphertext $(A', B')$ encrypted with public key $K'$; how can we check if they encrypted the same message?  Here's where the pairing-friendly part comes in: we check if:

$$e(A, K) / e(A', K') = e( G, B - B')$$

Here's how it works: if $A = rG$, $A' - r'G$, $B = rK + M$, $B' = r'K' + M$ (that is, encrypts the same message with a different $r$ and key values), then,

$e(A, K) / e(A', K') = e(rG, K) / e(r', K') = e( G, rK ) / e( G, r'K')$

$e( G, B - B') = e( G, rK - r'K') = e( G, rK) / e(G, r'K')$

That is, if the two ciphertexts encode the same message, the test passes.

So, if it solves the problem, but it does have these drawbacks:

It uses nonhybrid public key cryptography; hence it is inefficient (and each ciphertext encodes a relatively small amount of data, say, a few hundred bits).  To encode more than that, you'd have to encode each block separately, which is not going to be fun...
Worse, the "key hash" is actually the public key; what this means is that if someone has a guess to the data $D$, all they need to do is encrypt it with a random public key (doesn't matter which), and then use the above procedure to check if the two ciphertexts (the one under test, and the one they just generated) have the same plaintext.  If this is an issue, then you'd need an alternative method where the hash isn't a public key.


As an analogy to asymmetric key encryption, does the following work? If not why not? public key... a padlock (anyone can lock it)

private key... the key to the padlock (only key owner can open it)

Alice and Bob each have their own padlock and key

Anyone can get a replica of any padlock (public key) but only the padlock owner can open it (private key)

Alice sends Bob a private message:

Alice locks a box with Bob's padlock (public key)
Only Bob can unlock it.

Bob wants to be sure the box came from Alice:
(Bob gets Alice's signature)

Bob sends box to Alice locked with her padlock
Alice unlocks it, then puts Bob's padlock on instead, and sends it back to Bob
Bob sees only one padlock which he unlocks with his key. He knows that Alice had the box as only she could have taken her padlock off.

(Disclaimer: I am not qualified to speak authoritatively on cryptography - I didn't even take any undergraduate classes on cryptography as a student either)

The first part (the analogy for public-key encryption) is valid (analogising a public-key as a padlock works, but disregards the fact that a public-key (padlock) can be used to decrypt data encrypted with the private-key (the key) - which is counter-intuitive to a layperson).

As for the second part:

  Bob wants to be sure the box came from Alice: (Bob gets Alice's signature)

  Bob sends box to Alice locked with her padlock
  Alice unlocks it, then puts Bob's padlock on instead, and sends it back to Bob
  Bob sees only one padlock which he unlocks with his key. He knows that Alice had the box as only she could have taken her padlock off.

Key-exchange - or any subsequent interaction between Alice and Bob - is not necessary to prove message authenticity:

In PKI, a digital-signature is basically a message-digest (i.e. a hash like SHA-256) that has been encrypted with a private-key (rather than a public-key) - so that anyone with the public-key can decrypt the encrypted hash (and then recompute the hash and if it matches then that's proof that the message came from the holder of the private-key for the corresponding public-key), like so:

Alice sends Bob a private message.

The message is encrypted with Bob's public-key, so only Bob can decrypt it.

(Assuming Bob's private-key hasn't been leaked or discovered, of course).

While the message is encrypted with Bob's public-key, that has absolutely no bearing on the originator or attestor of the message - because anyone can encrypt anything with someone's public-key.

So Alice also adds her signature to the message, which does two things:

It means that Bob can trust that Alice is responsible for the message (that she either authored or she's attesting to it) - again, assuming Alice's key isn't leaked or discovered.
It proves that the message from Alice to Bob has not been modified (otherwise the recomputed hash wouldn't match).

Alice adds her signature by computing a hash of the message, then encrypting the hash with her private-key, so anyone with her public-key can decrypt it and see her hash.

Bob then receives the message:

The message is encrypted with Bob's public-key, so only Bob can decrypt it with his private-key.
The message has Alice's signature attached to it, so Bob can verify the authenticity and integrity of the message:

Bob has Alice's public-key and decrypts Alice's signature, revealing Alice's computed hash of the message.
Bob then computes his own hash of the message.
Bob sees that his hash - and Alice's hash match - therefore the signature is valid and Alice sent the message.

Regarding Step 3 in the scenario you've posted:

  Bob sees only one padlock which he unlocks with his key. He knows that Alice had the box as only she could have taken her padlock off.

This is not guaranteed and must not be assumed: Alice could have sent the exact same message to other people, and those other people could have encrypted the message with Bob's public-key and then forwarded it to Bob - if Bob receives one of those messages then there is absolutely no indication it actually came from Alice or that he was the original intended recipient.

This is why, for example, S/MIME for e-mail requires the entire message body and headers to be included in the message hash (in S/MIME this is actually done by copying certain headers like To:, Subject:, From:, etc into the message and then hashing and encrypting that) - so while the adage that anyone can encrypt anything with someone's public-key, so long as the message is also signed by the sender then at least this approach preserves information about the intended recipient in addition to the actual sender.

Example scenarios:

Alice wants to send a non-secret newsletter that can be redistributed by anyone:

Alice would sign her newsletter content with her private-key.
Anyone is able to redistribute (copy, forward, etc) this newsletter, and provided they keep the signature attached to the newsletter then anyone who receives it can be sure it originated with Alice.
Because anyone could simply remove Alice's signature and replace it with their own, Alice can prove she originated the message by getting a signed timestamp signature, as anyone else who subsequently signs the same message (after removing Alice's signature) would have a higher timestamp.

Note that this requires the use of a widely-trusted source of time information. Without a trusted source of timestamps the only solution in a zero-trust distributed system is by using a distributed ledger (aka blockchain) - which is another topic in itself.

Alice wants to send a secret message to a single individual recipient (Bob):

Alice would encrypt her message using Bob's public-key.
Alice should also sign the message to allow Bob to know the message came from her and to ensure the message isn't tampered with in-transit.
Note that nothing stops Bob from redistributing the message after decrypting it - encryption still relies on trust: encryption can't protect data if you can't trust the intended recipient of a secret message to actually keep it secret.

Note that there is little point to encrypting a message using PKI without also signing it because (strictly speaking) encryption doesn't ensure message integrity (i.e. changing random bytes in an encrypted message in most crypto-systems will result in changed output (usually garbled output though, but some crypto-schemes like ECB mode can be successfully attacked without knowing any of the secret keys).