Randomized algorithms and the one time pad The way I understand it, an algorithm is said to be randomized if it uses randomness as part of its logic (quoting Wikipedia). Now, in the case of encryption algorithms, I assume this means that for the same input, different outputs (i.e. ciphertexts) will be produced. The question is, what does "input" mean in this context?

In particular, does it include only the plain text to be encrypted, or does it also include the key? To give a concrete example, is the one time pad a randomized algorithm? If it is so, then "input" must mean plain text only.

To make matters more confusing (to me at least), again quoting Wikipedia: "To be semantically secure, that is, to hide even partial information about the plaintext, an encryption algorithm must be probabilistic.", where the last word is linked to the "Randomized Algorithm" page I link to in the first paragraph. So, given that the one time pad is semantically secure, is must be a randomized algorithm... right?

To add the cherry at the top of the confusion cake, there are still algorithms like, for instance, AES in CBC mode with a random IV, which will produce different outputs, when run multiple time with the same plain text, and the same key. Of course, this means that when you consider the input to one such algorithm as being the plain text only, you get the same result: different ciphertexts for the same plain text. So it would seem that the only "coherent" (lacking a better word) definition would require that input == plain text. Am I surmising correctly?

You indeed need to define what you understand by an encryption algorithm. The common way of doing this is to consider and encryption scheme as a tuple of three primitives: a key generation algorithm (upon a security level, output a randomly chosen pair of keys), an encryption algorithm to be instantiated with the generated key (that maps an input plaintext to an output ciphertext) and a corresponding decryption algorithm to be instantiated with the corresponding key.

To be semantically secure for an encryption scheme means that given an a priori information about a plaintext and the corresponding ciphertext under the encryption algorithm, no information from the plaintext can be derived that could not have been derived from the a priori information alone. (This has to be understood complexity theoretic-wise.)

Now the one-time pad encryption as you describe it does not fit the above scheme as it does not have this set of three primitives: the key (one-time pad) is to be changed for each plaintext. One could however construct a close encryption scheme this way (I assume fixed length plaintexts for simplicity, but it's not a limitation): one can see the key generation algorithm as a big table of pads indexed to somehow correspond to each one of the possible plaintexts. The encryption algorithm then lookup this table and xor it with the plaintext to produce the ciphertext. This scheme is semantically secure.

Here's is the bottom-line: an asymmetric encryption scheme has to be probabilistic since otherwise, given the encryption key (which is not the decryption key) it would be possible to distinguish, say, the encryption of the "hi bob!" message from that of the "hi alice!" message. But a symmetric encryption algorithm does not have to be probabilistic for the scheme to be semantically secure (the encryption scheme defined above is). However, if the security goal is to achieve the same for pairs of ciphertexts instead of single ciphertexts, then scheme defined above to fit the framework would not be sufficient as it would allow an adversary to distinguish between the pairs of ciphertexts corresponding to the same messages from the pairs of ciphertexts corresponding to distinct messages.

So, yes, a probabilistic encryption algorithm inputs a plaintext and outputs a ciphertext that will vary according to the random coins generated internally.


How does a client verify a server certificate? As far as I know,
when I request a certificate from Verisign (for example), and after they approved that I is me, they create a certificate (for me) that contains the digital signature and public key.
The digital signature is data that was created (not encrypted!) by their private key over my certificate data.
Now, a client connects to my site (which has an SSL certificate).

He reads the digital signature (from the certificate)
He knows which  algorithm used to create this signature, and he runs the hash again over my certificate data
Client uses his public key (in his store) of Verisign to decode (not  decrypt) the digital signature
If there is a match - all fine.
Client generates a random number, encrypts it with my public key, and my server accepts it and from now on - we are in symmetric mode.

I have the following questions:

Was I right?

Verisign creates the digital signature over my certificate data - which data?

The digital signature was created by what operation(?) over my certificate data? (Is this hashing?)

(I am not a cryptographer, but a  programmer who wants to understand this stuff.)

Was I right?

Pretty much. I want to add something to help clarify though: The Verisign public key in his store is of the Verisign CA (It is also stored in the form of a certificate). Also I think this process would qualify at decryption, no?

  Verisign creates the digital signature over my certificate data. Which data?

I'm not really sure what you mean here, but I'm guessing you are referred to the public keys store.

Basically the browser/OS have to trust a Certificate Authority (in this case Verisign). This trust is implemented by putting Verisign certificate including a public key inside the software. The corresponding private key will then be used to digitally sign certificates of websites that buy Verisign services. Because the browser have the public key, it can verify anything that Verisign signed using the corresponding key, hence the strength of this model.

A question might pop: Whose private key is then used to sign the certificate that is stored in the browser? It is usually self-signed (Use the very corresponding private key) or sign by a public key that is eventually self-signed. There is no way to verify self-signed certificate, hence the trust must be made in advance (by putting certificates in store).

  The digital signature was created by what operation(?) over my certificate data? (Is this hashing?)

What Verisign (and other CA) do is generated a private/public key pair (this process is called key ceremony). They then sign certificates of websites using the private key (Which is only done once per website), this process create a certificate that is signed by Verisign, which is then passed to the browser. If you're asking about the algorithms, basically they hash the certificate content and then encrypt the hash with the private key, so typically there's usually 2 algorithms used, one for hashing (MD5, SHA, etc.) and one for encryption (RSA, DSA, etc.)

Edit: Read comments to find out more, but I think basically this explanation is correct.


Which platforms are most vulnerable to Simple Power Analyse Attack In a "Simple Power Analyse Attack", the difference in power consumption during multiply or square operation is used.

In the RSA decryption process with the "Square and Multiply" algorithm, both square and multiply operations are executed if bit value in key is $1$ and only square operation is executed if bit value in key is $0$. We can observe on the power graph which operations were executed during decryption process. With this kind of graph it is possible to reconstruct the key.

Which platforms are most vulnerable to this kind of attack ?

Power Analysis attacks rely on the attacker being able to analyse the power used by the computing device, so such attacks work best on platforms where the attacker can analyse the power drawn by the device with cycle accuracy. This points at smart cards, which:

use an external source of power;
have very little room for some isolation circuitry which would hide the per-cycle power consumption;
work in a security model where the attacker controls the external environment (contrary to, say, encryption on a server in a remote room);
run at low clock rates, facilitating analysis;
run on an external clock, under full control of the attacker, thus again facilitating analysis (the chip will refuse to run if the clock rate is too low or too high, but simply knowing the clock signal makes correlation much easier);
are economically forced to be cheap, preventing the application of the most effective but expensive tamper resistance countermeasures.

Smart card vendors still do a lot of work on the subject, and modern, FIPS 140-2 level 3 compliant smart cards, are fairly good at defeating simple power analysis. Countermeasures are both algorithmic (e.g. blinding), software (e.g. always computing the multiplication, regardless of whether the key bit is a zero or a one, but only keeping the multiplied or unmultiplied value at the end), and hardware (isolation with some capacitors, internal clock, extra noise-inducing circuits...).


Why hash or salt when signing? EDIT: Just wondering why was this question closed as a duplicate of a question asked almost 2 years after this one...
I've seen an example of how to sign using RSA. Besides the signing itself (s = m^d mod n) it also hashes and adds an IV.
Why is that needed?

A second reason that a hash is usually present in RSA signature schemes (apart from being able to sign long messages) is to prevent existential forgery attacks. These look like this:

  Assume we have the public key $n$, $e$. Choose some random garbage $s$ (smaller than $n$), and calculate $m = s^e \mod n$ (i.e. "RSA encryption"). If you used "text book RSA signature" (without a hash and any padding), you now have a message $m$ with a fitting signature $s$.

With a hash, the signature checking equation is $H(m) \equiv s^e \mod n$ instead of $m \equiv s^e \mod n$, and this does not allow to create a message $m$ fitting to an arbitrary signature $s$ (assuming the hash function is preimage-resistant). Beware however that it is remains possible to create working $(m,s)$ pairs given the capability to obtain the signatures $s_j$ of chosen messages $m_j\ne m$, using an attack devised by Desmedt and Odlyzko (see section 3 of this paper).

(The padding scheme normally present in signatures serves the same purpose, and is designed to also resist chosen-messages attacks.)


Are there any masking methods for integer multiplication masking? I'm interested in lattice type cryptosystem such as Mod-LWR.

But I found that integer multiplication¹ is not safe for side-channel attacks.

I tried to make masking method by own method but it failed in t-test².

Are there any masking methods for integer multiplication?

¹ This is modular multiplication, but modulo is power of 2. So in 8bit multiplication, output is 8bit. I assume the multiplication itself has bitwidth of 13bit, just like a PQC candidate, SABER.

² The test is Welch's t-test. I tested my hardware (hspice converted from verilog) circuit with measuring power traces within constant period. With random input random output vs. fixed input fixed output. Power differs with input random number that used in B2A, A2B masking.

Generally speaking, there's not a way to mask the power of a circuit without dual-rail encoding.  With dual rail encoding, you pass but $x$ and $\bar{x}$ so that have skew free, self-clocking circuits; however, an separate advantage is that you mask the power.  Although this is used in asynchronous systems, it's fine in a synchronous system as well, and showed up in literature in 1955.

HSPICE does model the meantime to collisions in the circuit well, so you don't see the "hiss" of the transistors.  In fact, no models actually describe channel noise.  If you break the multiply unit into an addition-based Montgomery tree, it will be constant time and the power will likely disappear into the noise floor if you do it at either a bit or byte widths.   If you have a device physicist handy, you can likely prove that the change in power with bits is not actually able to be seen on a "unit scale".


McEliece for streaming data Under the assumption that there exists a real-world implementation of the McEliece scheme, could it be applied to streaming data as is? By that I mean in 'block cipher mode'? I've read that McEliece is very fast in encryption and decryption, hence calculating a session key for a symmetric stream cipher might be unnecessary. Since random errors are introduced into the plaintext while encrypting, could it then be used in 'block cipher mode'?

While McEliece could be used like a block cipher, in practice it would much must slower than the standard hybrid approach.  McEliece might be relatively fast compared to other public key primitives, it is still quite slow compared to a symmetric cipher.

On the Ecrypt performance page, they list the performance of McEliece on various hardware platforms; the fastest median time they list to encrypt a block of data is 48937 cycles, and to decrypt is 827864 cycles.

Now, I can't find where they list the value of $k$ they used (which the size of the message being encrypted in bits); if we assume a $k$ of 2048 (which is somewhat larger than the current recommendations), a block of data would be 256 bytes, so we're encrypting at 191 cycles per byte, and decrypting at 3233 cycles per bytes.

Obviously, a symmetric algorithm can do considerably better.

In addition, as for the block cipher mode, well, it's not as straightforward as you might have hoped; McEliece isn't a block cipher; it's nondetermanistic and it has a larger ciphertext size than plaintext size.  Straightforward ECB may sound attractive with McEliece's randomization property, however encryptions of the same text still resemble each other, and so ECB would still have problems with repeated plaintext blocks.  As for CBC, well, you probably could truncate the previous ciphertext to make it match the plaintext size when doing the exclusive-or.  You might be able to define a variant of OCB modified to work with the differing plaintext/ciphertext block sizes.  That other standard modes look pretty hopeless; CTR, CFB, OFB all have both sides run the block cipher in encrypt; this won't work both because we would lose the public key characteristic of McEliece, and in any case, they rather assume that encryption is determanistic.

In addition, McEliece has the property of expanding the ciphertext (making it perhaps 30% larger than the plaintext).  While this is not unusual for a public key algorithm (indeed, most public key algorithms expand the ciphertext rather more), for a long message this would be considerably more expansion than with a standard symmetric cipher (which generally adds a fixed amount of data for IVs, padding, and MAC tags).

As for your question about random errors, well, that's not actually a problem.  Yes, random errors are inserted during encryption, but they are removed during the decryption phase.  Hence, the decryptor gets exactly the same message that the encryptor sent, and so there's nothing prohibiting you from using some type of block cipher mode (assuming you use one that can live with McEliece's not-particularly-like-a-block-cipher characteristics).


Why CBC-MAC encrypts at each step Considering CBC-MAC as:

$\qquad H_0 = IV = 0$

$\qquad H_i = E_k(P_i \oplus H_{i-1})$

$\qquad MAC = H_n$

What are the properties that makes this "safer" (less exposed to failure) than just:

$\qquad H_0 = IV = 0$

$\qquad H_i = P_i \oplus H_{i-1}$

$\qquad MAC = E_k(H_n)$

Please use simple terms (a didactic explanation for non cryptographers is appreciated)

What are the properties that makes this "safer" (less exposed to failure) than just: [simple construction]

Well, there's an easy attack on the simple construction: Pick any message block $P$ and construct a message $M=P\|P$ (so $P$ twice). Now compute the MAC-tag of that message: $\text{MAC}=E_k(\text{IV}\oplus P\oplus P)$ which is just $E_k(\text{IV})$ because $x\oplus x=0$. Now pick any different message $P'$ and $M'=P'\|P'$ and compute the tag for that message: $\text{MAC}'=E_k(\text{IV}\oplus P'\oplus P')$ which again is $E_k(\text{IV})$. So both messages have the same tag. As soon as you see the tag for any of them, you can make somebody accept the other one as well. This is a property that we don't want from MACs.

If it helps your imagination: $P=0^n$ and $P'=1^n$, i.e. they are the message of all-zeroes and all-ones.


Is using the same key for different message HMACs insecure? When using the MAC-then-Encrypt composition, would using the same key for the HMAC in each different message be insecure?

No, with a reasonable choice of hash function, HMAC can safely authenticate many messages under the same key—it is not a one-time MAC like GHASH or Poly1305.  Of course, it may be prudent to use a message sequence number so you can reject replays (and it may be necessary for your encryption scheme, e.g. if you're using AES-CTR or ChaCha).

That said, why are you making this decision instead of using an authenticated cipher like AES-GCM or NaCl crypto_secretbox_xsalsa20poly1305?


Security of KDF1 and KDF2 (hash based KDF's) It's still common to come across implementations of KDF1 and KDF2. Basically these are KDF's that simply derive multiple keys from the key seed and a counter:

$K_i = \operatorname{KDF}(K_{master}, i) = \operatorname{H}(K_{master} | c)$

In this function $|$ means concatenation and $c$ is the encoded value of $i$ in 4 bytes using an unsigned big endian notation. KDF1 and 2 only differ with regards to the starting value of $i$.

The issue with the KDF is that a hash is not necessarily a PRF. Actually, I've only seen MD5, SHA-1 or SHA-256 being deployed.

Are there any particular attack vectors that can be used against this construction? Is there any practical/pressing need to switch to HKDF or a NIST SP 800-108 approved hashing algorithm or are the concerns purely theoretical of nature?

Please note: above only shows KDF1/2 in their least complex form, using only a single output block and with an empty $OtherInfo$.

As far as I know (which, admittedly, might be limited; I do not claim to possess encyclopedic knowledge of attacks on KDFs), there are no known practical attacks against KDF1 or KDF2 (which are also mentioned on this page, following ISO-18033-2) when instantiated with a secure hash function.

Regarding the relative security of these KDFs vs. HMAC-based KDFs like HKDF, it's worth noting that the HMAC security proof is based on the assumption that the compression function of the underlying hash is itself a PRF.  Therefore, when used with any hash function to which the standard HMAC security proof applies, it seems that KDF1 / KDF2 should also be provably secure, at least as long as the master key length equals (or is padded to) the input block size of the hash.


Best practices for IV generation What are the best practices for IV generation for AES and other algorithms?

Is RNG enough?

What if I cannot use RNG and need to use a variable that is related to some characteristic of the encrypted message? For example, file number or ObjectGUID? Will encryption of the IV do the job?

If encryption of the IV is a solution shall I use the same key that encrypts the actual message or a different key?

The requirements differ per mode of operation. AES itself is a block cipher, and as block cipher, it doesn't take an IV at all. Tweakable block ciphers may take a tweak, which may have some overlap with an IV, but AES isn't tweakable by itself.

CBC requires an unpredictable IV (to the adversary). One of the common ways is indeed to generate a 16 byte (one block) random IV. However, to do this you would require a cryptographically secure RNG, because a non-secure RNG may well be predictable given previous output.

You can use other, unique, known information as IV in some instances. However, CBC requires unpredictable data and a 16 byte IV. So e.g. a file number doesn't cut it by itself. However, you could use tricks to make it fit. For instance, you can use a secure hash on the unique data and use the leftmost 16 bytes as proto-IV. Then you can encrypt the proto-IV using the AES block cipher and use the result as IV. That way you would get an IV that is unpredictable and that doesn't have to be included with the message itself. Note that you should not perform decryption for that IV; the encrypted proto-IV is the actual IV.

Using a separate key would make your protocol ever so slightly more secure, as it brings down the chance of collisions (which an adversary might try to trigger deliberately, if possible) but it isn't required (in other words: you'd use a different key on PC's, but for embedded / lightweight systems you might a different trade off).

As indicated, creating a protocol is tricky and there may be many (other) attack vectors. Generally we try and use authenticated encryption schemes nowadays, as it at least doesn't allow for alteration of the encrypted message, which - for CBC - may also completely compromise confidentiality if plaintext or padding oracle attacks are feasible.


Blockcipher: key space define permutations of blocks An $n$-bit block cipher is a keyed function $f_k:\{0,1\}^n\rightarrow\{0,1\}^n$. There are $2^n!$ such functions. Most block ciphers seem to have only $2^n$ keys, although there is an AES mode that has a 256 bits key for a 128 bit block. This doesn't cover all of the key space though: a 128-bit key is roughly enough to fully cover a 34-bit block cipher.

For key lengths longer than block lengths, there exist a plaintext $x$ and two keys $k_0,k_1$ such that $f_{k_0}(x)=f_{k_1}(x)$. This can be seen by applying the pidgeon hole principle.
This is suggested to be dangerous, but I fail to see why.

I do not think that collisions are dangeous.  If they would, most real world ciphers would not be secure. Here is the argument:

Even if the block size is 2 times the key size, you will get  lots of collisions due to the birthday paradox.
A good cipher behaves for each fixed message like a random mapping on the key space.
Let's assume |key space|= $2^{64}$ and |message space| = $2^{128}$.
For each message $x_0$, the birthday paradox says that for $\sqrt {2^{128}}  = 2^{64}$ randomly chosen values you get a collision probability above 0.5. This means that on average at least half of the messages lead to a collision.
As you have $2^{128}$ different $x_0$, at least (on average) $2^{127}$ messages will give you such a collision.


To what extent would Bitcoin be private without address reuse? Let's say Bitcoin had these rules from the start:

An address with balance cannot more receive money
An address must use all its money in one transaction

This would prevent address re-use. To what extent would this make Bitcoin anonymous?

This would not help, and would actually make things worse. Bitcoin transactions are public, the input and output addresses are known. This can therefore be traced. Simply tracking the transaction from an initial input (say, buying currency on an exchange that complies with Anti Money Laundering (AML) laws) through each of its single outputs to a destination address would de-anonymize any destination. Since addresses can't be re-used in this scheme mixer services (money laundering addresses) become impossible, so anonymity is impossible for anyone who uses an exchange compliant with AML laws.


Compare two hashes with different salt I'm storing the salted hash of a credit card number in a database. What I'd like to be able to do is determine if two different entries in the same database correspond to the same credit card.

Specifically, let $C_1$ and $C_2$ be two credit card numbers (which may or may not be the same). Let $S_1$ and $S_2$ be two different salts. If $H_1 = hash(C_1, S_1)$, and $H_2 = hash(C_2, S_2)$, I need a function, $f$, such that $f(H_1, S_1, S_2) = f(H_2, S_1, S_2)$ if and only if (with very high probability) $C_1 = C_2$.

Can this be done securely?

Possible Solution

A friend of mine, who is a cryptographer, suggested the following:

Let $h(C, S) = g_1^{h_t(C)}g_2^{S}$ mod $p$, where $C$ is the credit card number, $h_t(C)$ is a "traditional" hash function, and $g_1$ and $g_2$ are generators that meet the Diffie-Hellman requirements, and $p$ is the corresponding prime.

If we do that, $f(H_1, S_1, S_2) = H_1g_2^{S_2}$ has the desired property.

A few questions:

Does this seem secure?
If I used a library, like the Bouncy Castle libs, to pick $p$, $g_1$, and $g_2$, would it be safe for a non-cryptographer to code this up? In other words, how easy would it be for a non-cryptographer to screw up the implementation in a non-obvious way?
Advantages or disadvantages of this compared to the two other solutions proposed below. I tend to favor this because I'm familiar with Diffie-Hellman, while the others involve some techniques with which I am not familiar. Additionally, I suspect that there are more libraries for Diffie-Hellman since it's old and popular.

Well, as others have said, you would not be able to do with a standard salted hash function.

However, if you were use a specially designed hash function (that allows this specific comparison), then it would be possible.

Here is a proof-of-concept idea, to show that it is possible:

Suppose $N$ was a large composite number of unknown factorization
Let our hash function be $h( C, Salt ) = hash(C) ^ {2hash(Salt)} \bmod N$ (where $hash$ is a function that converts strings into large integers, in a way where hashes of different strings don't have obvious relationships).  The factor 2 is there to prevent the Jacobi symbol of $h(C, Salt)$ from leaking any information.

This hash function is one-way, because reversing it is the RSA problem, and that's hard if we don't know the factorization of $N$.

And, we can compare hashes $h_1, h_2$ with salts $Salt_1, Salt_2$, we just check if $h_1 ^ {Salt_2} = h_2 ^ {Salt_1} \bmod N$.

And, if you're wondering "how do we get a value $N$ which we know is hard to factor, well, we can just grab an RSA-challenge number of the appropriate size.

Now, I'm not really advocating this method (the "hashes" are quite lengthy); however it does show that it is possible in principle.


Is this a safe way to prove the knowledge of an ECDSA Signature? I think that I've found a good solution to prove the knowledge of an ECDSA signature without revealing it.
In short terms it consists in generating an ECDSA signature using the point $R$ as generator, $s$ as private key and the result of $s*R$ as public key. So the $r$ part of the signature would be revealed but the $s$ part is still kept secret.

The usual ECDSA signature generation consists in proving that given a point $Qa$ where $Qa = da*G$ you know the number $da$ without revealing it.

To do so, the signing process works as following:

step 1. The signer calculates a new point R such that $R = k*G$ and where $k$ is a nonce that needs to be changed for every new signature.
step 2. The signer sets $r$ such that $r$ is the x coordinate of the point $R$
Step 3. The signer calculates $m$ such that $m = HASH(message)$.
Step 4. The signer calculates $s$ such that $s = k^{-1}(m+da*r)$
Finally the signature are the values $(r,s)$

The verification of the signature's authenticity is verified by ensuring that:

$R = s^{-1}m*G + s^{-1}r*Qa$

or that:

$s*R = m*G + r*Qa$

So what is done to prove the knowledge of the $s$ part from the signature such that $s*R = m*G + r*Qa$ and this without revealing $s$. This is exactly what we already did with $Qa = da*G$! The only difference is that instead of using the point $G$ as a generator we use $R$ and instead of generating a private key $da$ we use $s$

So the solution is to reveal:

$m$
$R$
$Qa'$ such that $Qa' = s*R$
$R'$ such that $R' = k'*R$ where k' is a nonce you generated
$s'$ such that $s' = k'^{-1}(m'+r'*s)$ and where $m'$ is the hash of a message you want to sign with your derived private key $s$.

The verification is done in a two step process:

step 1. verify that $Qa' = m*G + r*Qa$
step 2. verify that $s'*R' = m'*R + r'*Qa'$

Is this process vulnerable to forgery?
Are there other known proof of signature knowledge for ECDSA signatures?

Any EU-CMA-secure signature is indeed a proof of knowledge of either a signature of this document or the private key.
So, what you have done is using of second ECDSA signature as a proof of knowledge of discrete logarithm $s$. This completely makes sense, and I don't see any attacks on this.
Between, as a proof of $s$ you can use also Schnorr signature or Schnorr NIZKP - it has a property of zero-knowledge in random oracle model (while DSA has no such property).
Also, this idea of chaining signatures in this way is used in identity-based Galindo-Garcia signature, where 2 Schnorr signatures are chained.

But I can't answer you completely with a proof of security.
 At first, we need a rigorous formal model of attacker.
This cryptographic primitive (proof of knowledge of signature) is not very widespread and seldom considered.
Some works are devoted to this problem though, you can look here: https://link.springer.com/chapter/10.1007/978-3-540-47942-0_9# .
 Aldo, DSA signature has poor provable security in general (compare to Schnorr one).
E.g., if you used Schnorr signatures in this way - I would exactly say that it's secure (because Galinda-Garcia identity-based scheme is provably secure).
And, this solution could be safe on practice, but it lacks ZKP property for sure, so researchers mostly devote their efforts on other constructions, which provide ZKP.

Don't consider my answer as complete and accurate, this is just general abstract thoughts. I hope it will help you a bit.


Is is safe to use MtEtM? (MAC-then-Encrypt and Encrypt-than-MAC) Assuming I am using different secrets/keys for each MAC pass, does running both MtE and EtM creates any vulnerability?
This is what I mean about doing MtEtM:
K0 ≠ K1 ≠ K2
addMAC(msg, K) = msg || MAC(msg, K)
ciphertext = addMAC(encrypt(addMAC(msg, K1), K0), K2)

If I understood correctly, EtM has the advantage of ensuring that the recipient doesn't even use the decryption key when a message is tampered. But MtE is harder to forge.
Intuitively it sounds that combining both would make the system at least a bit more secure, but I am worried about some sort of timing attack.
Also, is the use of HMACs instead of generic MACs here a potential problem?

If the MAC is theoretically secure, but its implementation has a side channel (like by Differential Power Analysis, maybe even timing) leaking information about the MACed message (but not the key), and the encryption is secure including it's implementation, then neither MtE nor MtEtM are safe (because the side channel leaks about the message), but EtM is secure (because the MAC is applied to ciphertext, which can safely leak).
Thus EtM can be secure when MtEtM is not. A better reason to prefer EtM to MtEtM is Occam's razor.


Encryption based solely on XORing with concatenated hash values I have recently read a bit about Lamport signatures (especially the approach using hash ladders to save disk space) and I found it very interesting that it entirely depends on a hash function.

So I asked myself the following question:

When you have a plaintext $p$ and hash it and concatenate it with its hash again and so on: plain -> $H(p) + H(H(p)) + H(H(H(p))) + ...$ ($n$-times)

is this a good source for randomness? Why not?
Does the attacker having a look at this output have any advantages in guessing the plaintext for large $n$?

You have some file you want to encrypt. Hash the file with a good hash function (e.g. Keccak). Then concatenate this hash with a password you choose.
From this you derive a hash concatenation like above until it is as long as the file you want to encrypt; lets call it "hashchain". Then XOR your file with the hashchain and when you are finished you write the hash of the original file to the beginning of your encrypted file. Destroy original file and hashchain.

When you want to decrypt, take your password and the hash of the original file (which we have written to the beginning of the encrypted file), concatenate and hash this until you have a file which has the size of the original file. XOR both again and you get back your file from the beginning.

Note: Using password and hash of the original file as the beginning for the hash chain makes us able to use the same password for encryption of different files.

Is there a reason why this is not secure?

I have no only superficial knowledge about cryptography, please keep this in mind when answering.

1) is this a good source for randomness? Why not?

It is certainly not a cryptographically secure PRNG. In order to be a cryptographically secure PRNG, it must not be possible to predict the next output based on the current output. With your algorithm, the next output is predictable, since it's just H(previous_output) and, according to Kerckhoff's principle, you should assume the attacker knows the hashing algorithm.

  2) Does the attacker having a look at this output have any advantages in guessing the plaintext for large n?

The attacker only has to guess or know the first block of plaintext. Once the attacker knows this, decrypting the rest of the plaintext is easy: for the first block, the ciphertext C is H(password) ^ M, so H(password) = C ^ M. So once the first block of plaintext is known, the attacker knows H(password), and can calculate H(H(password)), H(H(H(password))) etc.

  3) Why is the following encryption a bad idea? You have some file you want to enrcrypt. Hash the file with a good hash function (e.g. Keccak). Then concatenate this hash with a password you choose. From this you derive a hashconcatenation like above until it is as long as the file you want to encrypt lets call it (hashchain). Then XOR your file with the hashchain and when you are finished you write the hash of the original file to the beginning of your encrypted file. Destroy original file and hashchain.

Password have the habit of having low entropy, which makes them excellent targets to brute-force. If the first block of the file's plaintext reveals any information about whether the file is successfully decrypted, the attacker only has to calculate H(plaintext_hash || password) and xor the first block to see if the attack is successful. Most hash functions are fast, and attackers can easily try millions of passwords per second.

Even if the first block does not reveal any information, if you reuse the same password, an encryption oracle attack with a chosen plaintext can choose an all-zero plaintext. Then the first block simply becomes C = H(plaintext_hash || password) ^ 0 = H(plaintext_hash || password). Since the attacker knows the plaintext hash, the password can still be brute-forced in the same way.

Given my experience with cryptography, that's probably just the tip of the iceberg.


What is difference between Cryptographic Transformation, Encryption and Hash? I read in a book that: let $f(K,R)$ is cryptographic transformation of $R$ using $K$, $K\{R\}$ means $R$ is encrypted using $K$ and $h\{R\}$ is the hash of $R$ and then the example follows.

I want to know what is difference between cryptographic transformation of $R$ and encryption of $R$ using the same key? Aren't they same thing?

Usually a cryptographic transformation can mean anything. It is just a cryptographic function whose output is based on the input, $K$ and $R$ in this case. You could have a $MAC(K, R)$ where the transformation is a message authentication code or MAC for instance. A MAC also takes a key and a message, but its purpose is rather different.

So $K\{R\}$ is a specialization of $f$. Often $K\{R\}$ it is written down as $E(K, R)$ which would probably make this more clear (although $E_k(R)$ is also often used).

It could also be that $K\{R\}$ is the keyed encryption function, taking just the input $R$ while $f(K, R)$ is the uninitialized or stateless cipher taking both the key $K$ and the input message $R$. If the math notation is not precisely specified you may have to rely on context.


Precisely how does CBC mode use the initialization vector? As I understand it, AES in CBC mode does an XOR of the 128-bit initialization vector and the first 128 bits of plain text. Is this correct?

I am using the PHP 5.3 openssl extension in aes-256-cbc mode. I'm experimenting with a round trip, that is, encrypting and then decrypting to make sure I get back the original string.

I find that if I encrypt with one initialization vector and decrypt with another initialization vector, using the same secret key, the first 128 decrypted bits are corrupt (as expected) and the rest is the correct plain text.

I find that if I encrypt with one initialization vector, and decrypt with a barely-different initialization vector, the decryption shows barely-different plain text. That is, when I change the third byte of the initialization vector, the decrypted plain text shows the third byte corrupt and everything else correct.

This does seem to show how the initialization vector affects AES cipher-block chaining. Is the initialization vector simply XOR'd with with the first 128 bits of plain text, and that's it?

The schemas from the relevant Wikipedia page really explain it all:

As you see in the decryption schema, the IV is used for a single XOR that yields the first plaintext block; it is obvious that the IV impacts only that block. When encrypting, though, modifying the IV alters the first ciphertext block, then the second ciphertext block, and so on.

The role of CBC is to hide redundancy in plaintext blocks. A block cipher is deterministic: encrypt twice the same input block with the same key, and you get the same output. Real-world plaintext data has redundant blocks; this leads to detectable leaks if nothing is done about that, as in ECB mode (the famous penguin picture is a clear illustration of the problem). CBC solves this by "randomizing" input blocks before encryption, and this is done by XORing each block with the ciphertext from the previous block: the output of a block cipher is assumed to be randomish enough to be efficient at avoiding as most as is feasible input block repetition.

Since the first block has no "previous block", the IV is needed to get the mode started. It is a synthetic "zero-th block".

If you take CBC-encrypted data and simply flip the k-th bit in the n-th block, then, upon decryption, this will result in replacing the n-th plaintext block with garbled junk, and flipping exactly the k-th bit in the n+1-th plaintext block; nothing else is changed. (This also highlights by having a MAC is very important to deter malicious alterations; even without knowing the key, attackers can have rather precise control on what they can do to the resulting plaintext by modifying the ciphertext.)

There is a common myth about CBC being a way to make every ciphertext bit depend on all plaintext bits. This is a myth; CBC does not do that and never aimed at doing that.


Is it possible to derive the encryption method from encrypted text? Is it possible to identify the encryption method, or at least rule out some of them, by looking at the encrypted text?

For example, if you have 3 encrypted strings where the first 10 characters are the same on each of the strings.

If the encryption system is any good, then no. The output of a (symmetric) encryption algorithm is supposed to be indistinguishable from pure random. If you can distinguish encryption output from pure random with probability greater than 1/2 (i.e. you are given two strings of bits, and you can tell which one comes from an encryption system with better success on average than pure luck), then the encryption algorithm is said to be "broken". An example of such an algorithm is RC4 (not that being broken does not mean that decryption without the key is easy; RC4-protected SSL connections still appear to be mostly safe).

However, the used encryption algorithm is not generally supposed to be secret information. That algorithm exists as code or specific hardware somewhere; it is amenable to reverse engineering. It is very difficult to know how much algorithm secrecy may resist an attacker, and that's a problem since a good security policy should aim at quantifying things. Secrecy of a symmetric key can be quantified: a 128-bit key is secret up to 2127 (on average) trials. Since such a precise measure cannot be achieved for the algorithm itself, it is usually assumed that the name of the algorithm is known by everybody. Correspondingly, encrypted message formats often begin with an additional header which plainly states which algorithm is used (such a header avoids many maintenance headaches, especially when several distinct algorithms are in use).


Can we attack a hash function if we only have the input x such that y = h(x) This question deals with a "one-way" function $h$. Then, given the value $y = h(x)$, it is computationally infeasible to find $x$ directly from $y$.

  (a) Suppose that Peter computes $y = h(x)$, where $x$ is Peter's salary, in Ringgits. If John obtains $y$, how can he determine Peter's salary $x$?
  (Hint: Adapt the forward search attack to this problem).

How do I explain the attack just by using cryptanalysis and forward search attack?

  (b) Why does your attack not violate the one-way property of $h$?

Assuming he used forward search attack does not violate the one way property of $h$?

  (c) How could Peter prevent this attack? We assume that John has access to the output of the function $h$, John knows that the input includes Peter's salary, and John knows the format of the input. Also, no keys are available, so Peter cannot encrypt the output value.

Second pre-image resistant to prevent this attack?

a) You can't reverse the hash function, but you can try to hash a lot of different x', and see if h(x') = y. Assuming you have second pre-image resistance, you should then have x'= x. This is possible only because you know that Peter's salary is in a small range (e.g. [0,10000]), so you can compute every hash.

b) Well, we didn't reverse the hash, we simply use a forward search attack... There is nothing more to say.

c) You suppose that you can't use a key, so I don't see how you can prevent the attack... Maybe concatenate x with a constant length secret value, if using a secret value without encrypting x allowed.

However, if you assume that Peter has a secret key he can use, one way of preventing this type of attack would be to use a secure way to compute the tag of x. You can take a look at HMAC, which is described in the link I provide.


Efficient way to combine collection of hashes into a single hash? I have a system where each user will submit a set of data. The data will be hashed and their hash will be submitted to the server. My plan is to combine each users hash (converted to bytes XOR'd with the root hash) to generate a final hash. This is done as a means to create entropy so that the final hash can be used to generate a "random" number. It is not possible to generate a pseudo / truly random number on the system, hence the work around.

Currently, I am doing the following on the server (pseudo code) :

//hexidecimal 54673257461630679457 (large prime)

var rootHash = 0x2F6BE6DFD71F8B9A1;

submitData(var userHash){
    rootHash ^= userHash;
}

After all of the user hashes are XOR'd with the root hash, the root hash is converted into a number and then the last 10 digits of that number are used as the "random number."

Users are able to see eachother's hashes, however with a system like this, I figure even if they calculated the final number, submitting new data would change the root hash and thus change the final number generated.

I am not very experienced in this field so my question is, what are some of the cons of using a method like this, and is there a more efficient way to do this?

With the system as described, the last participant to submit its hash can trivially choose "the random number", knowing the initial value of rootHash and what hashes earlier participant submitted, by choosing the values of the hash s/he submits (s/he computes the XOR of these and $d+10^{10}r$ truncated to the hash width, where $d$ is the desired 10-digit value and $r$ is random; this insures "the random number" is $d$ ).

Even if what s/he submits has to be the hash of something (that's untold), finding a suitable something is feasible (that's expected to require a mere 5 thousand million hashes; or few hundred thousands if the last two submitters collude).

Replacing the XOR with a hash of the concatenation of the submissions do not help much (for example, it remains very easy for the last submitter to force "the random number" to be even).

A method truly solving this issue could be:

each participants draws a random $x_i$ (say, 128-bit)
each participant submits the hash of $h_i=H(x_i)$ to the server and/or each participant; that's called a commitment of $x_i$
after the above is complete each participant reveals its $x_i$
the server and/or each participant checks that $H(x_i)=h_i$ for all participants
the $x_i$ are processed just as the hashes in the question (there's no reason to initialize rootHash to an haphazard value, zero will do just as well).

This way each submitter can be convinced that whatever collusion there might exist among other participants, "the random number" is at least as unpredictable as the $x_i$ s/he submitted, if the hash is collision-resistant (implying it is wide, e.g. 256-bit). Note: if the hash was not collision-resistant, the last submitter of $x_i$ could have selected $x_i$ and $x_i'$ with equal hashes $h_i$, then knowing the $x_i$ of all other participants could decide to submit either $x_i$ or $x_i'$ so as to influence "the random number" in some controlled way.


Converting a C25519 curve into a NIST-supported curve for FIPS crypto If I have a cryptosystem based on C25519 ECC crypto, is it possible to use the same public/private key pairs for key agreement in a FIPS compliant way by deterministically converting C25519 public and private keys into keys under some other ECC curve?

In other words let's say Alice and Bob have C25519 key pairs. Alice has her public and private key and Bob's public key, and Bob has Alice's public key and his public and private. Alice and Bob want to convert their keys into NIST P-256 keys (or some other NIST curve) and then execute ECC key agreement using a FIPS compliant cryptographic module in order to run in a FIPS compliant mode of operation.

Is this possible? Is it secure?

No, conversion of an EC key pair from a curve to another of unrelated order is not possible.

One of the closest things that could be done would be that parties generate a new P256 key pair, then

certify their new P256 public key using their C25519 private key, check the other party's certificate using the other party's trusted C25519 public key, and now trust the other party's P256 public key.
or negotiate trusted symmetric session key(s) per their C25519 key pairs, and transmit their new P256 public key over a channel secured by symmetric crypto.


Why is it impossible to find the private key from the public key? From what I understand, based on the article A Beginner’s Guide: Private and Public Key Cryptography Deciphered, the public key is generated by performing $n$ tangent plus mirroring operations from the point $G$ over the elliptic curve, where $G$ is defined in secp256k1 and $n$ is a natural number that directly relates to the private key.

As I know the public key and the seed value $G$, I could start a process computing $$G + G, G + G + G, \dots$$ and comparing those results with the public key value until it matches.

If your answer would be that this process is very slow: if this process is slow, the same applies to computing the public key from the private key (because the operations are the same except for the check operation). So, how it is possible to compute the public key in a very fast way?

My question is: as I know the public key and the seed value `G', I
  could start a process computing G + G, G + G + G, and comparing those
  results with the public key value until it matches.

You can, but you have to check about 2256 values. This is an extremely big number. So it is computationally infeasible to perform this operation.

  If this process is slow, the same applies to, knowing the private key,
  and compute the public key (Because the operations are the same except
  for the check operation), so how it is possible to compute the public
  key in a very fast way?

Because we compute public key in smarter way. You are trying to check all values by continuously do + operation. But to generate public key we use * operation: public = private * G


Generally accepted algorithm for two-pass, misuse-resistant AEAD that is efficient in software I would like to know what the standard is for two-pass, nonce-misuse-resistant AEAD that is efficient in software.  Thus, AES-SIV is excluded; modes based on a stream cipher like ChaCha20 are preferred.

AES-SIV when done well can be very fast. If you have AES-NI then it is possible to get under a cycle per byte. It is not the original AES-SIV construction but rather this one based on GCM (I agree that the original AES-SIV is way too slow). I suggest also that you look at the Caesar candidates. In general, there is no "standard" yet here.


Is using AES-256 with a key of less than 256 bits of entropy still quantum-resistant? Encrypting with AES-256 is widely claimed to be post-quantum secure.

But let's take a case where you use an initial key that has less than 256 bits of real entropy. In this example, let's work with a 128-bit key that has 128 bits of real entropy. We stretch it with something commonly used, like PBKDF2 with 120,000 iterations. We use the 256-bit result as the encryption key for AES-256 to encrypt some secret.

Is the the secret still secure against brute force attacks by a quantum computer, the kind can halve (or worse) the effective security of a symmetric cipher using Grover's algorithm? (Edited to add:) We assume the attacker knows the specifics of the above scheme, but not they length of the entropy or the initial key.

Currently, the quantum attacks work on the block cipher itself. The Grover's search algorithm reduces the complexity of 256-bit key into 128-bit since it has complexity $\mathcal{O}(\sqrt{n})$ and in the case of 256-bit $\mathcal{O}(\sqrt{2^{256}}) = \mathcal{O}(2^{128})$

Since you have started with 128-bit entropy, theoretically, the quantum attacker to block cipher itself with a 256-bit key will not benefit from Grover's algorithm since Grover's algorithm will search 256-bit. Keep in mind that 256-bit space is infeasible for the quantum.

What if in an unforeseeable future, someone builds a quantum circuit for the PBKDF2 + AES combination that is the search for the 128-bit input to PBKDF2 and uses the output for the AES-256 key and perform Grover's kind of attack?

This can be done by extending the AES-256 Grover Search with a 128-Q-bit PBKDF2 Quantum circuit. Since the input is 128-bit, the search will be $\mathcal{O}(2^{64})$ to find the ciphertext.

The attacker, always, will use the weakest point!.


SHA-256 private/public coordinates to the PEM format I feel that my question might display a bit of ignorance. I have been searching for answers, but have had no luck--perhaps my assumptions are wrong. I apologize if that is the case.
Context:
I have a microcontroller communicating with a server.  Every frame is signed using a private key from an RSA/SHA-256 public/private key pair. The pair is generated externally with OpenSSL, and the public key is in the PEM format, which is something like this (it is a not a used key):
-----BEGIN PUBLIC KEY-----
MIGeMA0GCSqGSIb3DQEBAQUAA4GMADCBiAKBgHR/kzljDkbuyOWGzfxSgfrJ3xZd
GZspxrVU+2ZbkDej5KNzGXu5lJdBzATU/h/S4Y2DgwaaN0tRMxX4QeN7x90qmdkO
oUQggpbv7rvju3idBp0fDcV6M56mnkw+EeyeNjDsRqoUVD/zlQdEUUcC00iItu8N
0GH08Ex8ubBhXQ7XAgMBAAE=
-----END PUBLIC KEY-----

My issue:
Due to performance problems on the microcontroller, we had to use an external chip (for instance, ATECC608A) for all of these cryptographic processes. Also, it will be useful for production because this chip can generate its own private/public keys SHA-256 keys. When generating the SHA-256 private key, the chip returns me the public key. However, it does not return me a public key in the .pem format, but, according to the datasheet, it returns me the coordinates X and Y of the public key, which are 64 bytes.
My questions:

My first assumption that might be mistaken is this: I assume that a SHA256 pair is the same thing as RSA-SHA256. I know that there are many variants of the SHA256 algorithm, but based on what I've read, the RSA is the standard variant. So I am assuming that RSA-SHA256 is the same thing as SHA256. Am I right?

Assuming I have RSA-SHA-256, how can I convert these coordinates to .pem? On the server-side, I was using the .pem public key of the device to verify the signature. Now I am only able to share some coordinates of the public key. Is it possible to convert from coordinates to .pem? Or am I just misunderstanding a bunch of different concepts?

What you are sharing is indeed (lapo.it ASN.1 decoder) a 1023 bit public RSA key. RSA keys can be used for multiple things such as signature generation. In that case the signature algorithm may use SHA-256 to hash the message, but the key itself doesn't care about the hash function used (you won't see it in the structure in the link).

"private/public keys SHA-256 keys."

SHA-256 is a hash algorithm; it doesn't use any keys and certainly not a key pair.
OpenSSL command line only indicates the hash algorithm, but in that case it just assumes PKCS#1 v1.5 compatible RSA signature generation / verification if you use an RSA private or public key respectively; possibly other API's or command lines do the same.

However it returns me not a public key in a .pem format but, according to the datasheet, it returns me the coordinates X and Y of the public key, which are 64 bytes.

X and Y coordinates are not components of an RSA public key. Together they are usually indicating a point on an elliptic curve though. What you are likely getting is a flat representation of EC public key (usually indicated as variable name $W$). In that case they public key may consist of 2 times 32 bytes (i.e. two statically sized unsigned big integer values).

My first wrong assumption can be the fact that I am assuming that a SHA256 pair is the same thing as RSA-SHA256. I know that there are many variants of SHA256 algorithm, but from what I've read the RSA is the standard variant. So I am assuming that RSA-SHA256 is the same thing as SHA256. Am I right?

So no, there is no such thing as a SHA-256 pair. More likely it is a P-256 (or, alternatively named secp256r1) public key. Here P-256 and secp256r1 indicate the curve's domain parameters by name, i.e. a named curve.

Assuming I have the RSA-SHA-256, how can I convert these coordinates to .pem? On the server side, I was using the .pem public key of the device to verify the signature. Now I am only able to share some coordinates of the public key? It is possible to convert from coordinates to .pem? Or am I just misunderstanding a bunch of different concepts?

That's better asked at StackOverflow indicating the exact runtime & libraries that you plan to use.
The steps are:

put the numbers into the X9.62 structure;
put those into a SubjectPublicKeyInfo ASN.1 structure while indicating elliptic curve cryptography as algorithm and the domain parameters by OID;
DER encode above structure;
perform the PEM encoding to apply the "ASCII armor", i.e. make it text.

Yeah, I know, outside of your experience field, sorry.


Message security and also program copy detection Imagine I have client and server running on different machines, each as a separate software.
I want to ensure:

message authenticity, integrity and confidentiality at least of messages coming from client.
and also I want to be able to detect if someone copied my client software on different machine and is trying to make requests there

Now to solve item 1. I will use SSL with both client and server (is mutual authentication needed btw?) authentication. This solves 1, right?

To solve 2, I intend to use following protocol together with SSL:

After client connects to server using SSL, server will send some random number to client. Each client can have some ID of course.
Client must use this number in next iteraction with server. After successful interaction, server sends client different random number which the client has to use in next interaction with server and so on.

Now, idea is if someone copies my client software, her copy of the program will use the random number provided by the server - but this will make my original client go out of sync with the server (because her random number was already used) - and I will be able to detect this. Which means my goal is achieved as I listed initially. Does this achieve my item 2. in the list? If no improvements?

The goals stated can't be met according to the requirements defining traditional cryptography (including, public-key cryptography); most importantly, that all methods used except secret keys are public, and communication channels can be eavesdropped and altered (as routinely occurring on a pwned computer, or one fully under control of its rogue user).

The current question remains unclear on if the client computer(s) contain some initial secret/private key (and a certificate, if that secret is not initially also known to the server). I assume they don't. If they did, and could be trusted, and operated by trusted parties, the problem becomes trivial (see also butlast paragraph of this answer).

Goal 1

If the software is public, and there is no initial secret on the client side, then from a cryptographic standpoint, the only goal SSL/TLS (or cryptography) can reach is confidentiality of messages to the server, and authenticity+integrity of messages from the server.

For other directions: we face the problem that without an initial secret tied to a determined entity, we can't make a secret tied with a determined entity, thus can not encipher to or determine origin from a determined entity, in the sense these things have in cryptography; among the best that can be obtained:

A reverse-engineering of the software is required (and hard to some varying degree), in order to compromise the confidentiality of messages from the server that the software does not otherwise output in clear, or to compromise the authenticity+integrity of messages generated by the software itself (rather than accepted as input); otherwise said, the software is considered obscure enough to hold some secret making it a cryptographically identifiable entity.
On a trusted computer (thus excluding one pwned or under full control of a rogue user), after first running an unmodified copy of the software performing an appropriate protocol (that could be a key exchange protocol, or a certification request protocol), this computer/software can hold a secret and become a determined entity, which messages can be authenticated+integrity checked, and which can receive confidential messages that no other computer beyond the server can decipher. Notice that the server can practically not distinguish between this desired situation, and a different reality where the secret ends up shared among many rogue users (for example, the software can be run in a single VM, and the usage of that VM allowed to several rogue users one at a time, including with that VM running on their computer, and the server seeing a single IP thanks to a VPN; see also last paragraph of this answer).

Goal 2

If the software is public, and you assume that the original machine is operated (or pwned) by an adversary (including remotely), then from a cryptographic standpoint, there is no way to detect that a copy of the software is running. Among the best that can be obtained:

It is detected/prevented simultaneously running unmodified copies of the software on two machines.
It is detected/prevented alternatively running unmodified copies of the software on two machines that are not both cooperating and communicating with each other.
Reverse-engineering of the software is required (and hard to some degree) in order to run, unknown to the server, a modified copy of the software that is largely equivalent to the original program, except for functionalities that the server performs and local software cannot; in addition, the required reverse-engineering can be made cryptographically impossible (by encrypting the corresponding code) for functionalities that have not been observed running at least once on an instrumented authorized software.

The method in the question seems to be able to meet 1 and 2 for goal 2. But

The devil is in the details; in particular, the system should work reliably in case of message loss in the "server will send some random number to client" step, which can happens by accident, or be induced in many ways external to the software (as in issue #1 in this answer to a related question). Thus the server will sometime have to tolerate two distinct values in the next interaction with the client. It is hard to get that working reliably and not open to fraud allowing simultaneous use of two copies, especially by an adversary controlling both computers.
In real life, there's software cracking, thus assumptions made that the software is unmodified are unrealistic.
Pwned machines can cooperate and communicate with each other unknown to their respective honest users.
Rogue users of any machine they fully control can make these cooperate and communicate, and even pretend being pwned as an excuse if caught.

If "ignoring software cracking etc." for some wide definition of that (which can match some real-life situations where there is no competent and determined adversary with access to a working instance of the software); and, for goal 1 in both directions, an initial secret unique to each client, and usable for authentication of the client (e.g. because it is the private key to a public key system, and the corresponding public key is certified, and the private key is in trusted hardware like a TPM); and tweaking the protocol in the question as explained; then yes the protocol outlined in the question can achieve goals 1 and 2, at least within the limits I stated.

People who never wrote an hello world! program in any compiled language can install software in the free Virtualbox software in order to circumvent software copy protection. That would be applicable even if the software allowed use only on a machine with a valid SSL certificate and matching private key (which would be highly unusual, and inconvenient to normal users). The technique in the question will not prevent these people from putting that VM on a USB drive that they can move around or lend, or "put in the cloud" with some caching making it quite usable. The technique in the question will prevent multiple instances of that VM to run, and thus discourage the original owner from allowing multiple instances, for fear of being unable to use the software. In that sense, the technique is practically useful. However this is not crypto, which is on topic on CSE; this is security by obscurity, which is not.


How does asymmetric encryption work? I've always been interested in encryption but I have never found a good explanation (beginners explanation) of how encryption with public key and decryption with private key works.

How does it encrypt something with one key and decipher it with another key?

Generally speaking, the public key and its corresponding private key are linked together through their internal mathematical structure; such keys are not "just" arbitrary sequences of random bits. The encryption and decryption algorithms exploit that structure.

One possible design for a public key encryption system is that of a trapdoor permutation. A trapdoor permutation is a mathematical function which is a permutation of some space, such that computing the function in one way is easy, but the reverse is hard, unless you know some information on how the trapdoor permutation was built. Encryption is applying the function on a message, decryption is about using the trapdoor to reverse the function.

For RSA, a well-known asymmetric encryption algorithm, consider a rather big (say 300 digits or more) integer $n$. $n$ is composite: it is the product of two big prime integers $p$ and $q$. There are more such composite integers than there are particles in the observable universe, so there is no problem in generating such an integer. $n$ is called the modulus because we will compute things "modulo $n$". It turns out that:

it is easy to compute cubes modulo $n$ (given $m$, compute $m^3 \mod n$);
if $p$ and $q$ were chosen appropriately (I skip the details), raising to the cube is a permutation modulo $n$ (no two integers modulo $n$ will have the same cube, so any integer between $0$ and $n-1$ has a unique cube root modulo $n$);
computing the cube root of an integer modulo $n$ is extremely hard
... unless you know $p$ and $q$, in which case it becomes computationally easy;
recovering $p$ and $q$ from $n$ (that's factorization) is extremely hard.

So the public key is $n$, the trapdoor permutation is raising to the power 3, and the reverse is computing a cube root; knowledge of $p$ and $q$ is the private key. The private key can remain "private" even if the public key is public, because recomputing the private key from the public key is a hard problem.

There is a bit more to RSA than the description above (in particular, RSA does not necessarily uses the power 3), but the gist of the idea is there: a function which is one-way for everybody, except for the one who selected the function in the first place, with a hidden internal structure which he can use to reverse the function.

SSL (now known as TLS) is a more complex beast which usually uses some asymmetric encryption during the initial stages of the connection, so that client and server end up having a "shared secret" (a commonly known sequence of bits); the shared secret is then used to apply conventional encryption and decryption to the rest of the data ("conventional" meaning: same key to encrypt and decrypt).


Decryption honeypots When performing a key search, I've always wondered how you reliably detect a successful decryption once you hit the right key. I assume that you have to analyze the data and look for patterns: words, letter frequency, known file headers, statistical properties and so forth.

Is this a correct assumption and, if so, has anyone exploited this by enabling the introduction of decoy plaintexts in a cipher? Is there any research related to this?

Yes, that's a correct assumption: sometime statistical properties of the plaintext (like, compressibility using standard algorithms, which can be quickly approximated, then refined) are used to check that a correct key was found during brute-force search, when there is no better way, like known plaintext.

By the second Kerckhoffs's principle, if a decoy method is used, that fact is part of the algorithm, and public (the value of the decoy can be an input, considered part of the key, and either secret or public). However modern cryptographic algorithms are designed to resit any amount of known plaintext (and even chosen plaintext), and therefore do not need such decoy method in order to achieve confidentiality; which is why I doubt you'll find (recent) peer-reviewed articles about decoy in order to improve confidentiality, only as a mean to implement plausible deniability, as in TrueCrypt. In this application, decoy is used, but not for improved resistance to exhaustive key search.

Update: Sometime the key is really a passphrase stretched to a key using some password-based key derivation function. When you count brute-force search of such passphrase as key search, which is quite legitimate, a decoy (deciphering to plausible decoy plaintext with a weak decoy passphrase) is an interesting idea. One issue is that, as stated above, the adversary is assumed to know there is potentially a decoy; anyway it seems hard to hide the fact that an encryption system allows the use of decoy passphrases(s) and plaintext(s), when that system is analysed by the adversary to the point necessary to mount an efficient passphrase search. Therefore, the adversary performing passphrase search has the option to continue searching after finding decoy(s), and I do not see that the overall resistance to a given effort of passphrase search is much improved. Towards that goal, it is probably better to use a good key derivation function, using the principles pioneered by scrypt; also, that avoids the ciphertext expansion unavoidably caused by the use of decoy.


Secret community forming based on zero-knowledge proof (IOT) I want to discuss a simplistic scheme that comes to my mind, after I read about zero-knowledge proof and some fermentation time. I should mention that this is not born out of a business need or academic studies / research. So please bear my level in security in general.

Assumptions:

With n participants and m < n communities to be formed. With m > 2

Participants form a community if they have the same secret key set
in the beginning and also know their peers.
Participants form a community secretly if no one knows no
participant’s community besides his peers (We assume they do not
know about each other at the beginning).

A Counter (shared memory with initial value) or a Timer approach are considered.

Counter approach:

Procedure:

All participants hash their secret keys based on some salt. The goal is that when they broadcast the hashes, participants within a single community must broadcast no same hash values (no equal two hashes), otherwise they will be discovered by all participants (as participants within a single community).
The salt is defined as number between the current counter’s value and the next, Randomly chosen with a relatively small granularity, so that collisions of two participants within the same community is very less probable, for example if Counter is the natural numbers, the first value is 0 and if it is the current, then the next value is 1, salts for one round are derived from [0, 0.0001, 0.0002, …, 1].
After a broadcast for round j:

Participants of C(i) (Community i) hash their keys, considering all
possible salts between [0, 0.0001, 0.0002, …, 1], hence they
calculate 1000 hash value for their key and store results in a
secure internal memory.

(a random salt chosen from between the “current counter” and “current counter + 1” with a probability 0.0001 of collisions)

Each participant of C(i) picks up randomly one value from the secret
table of 1000 hashes.
Each participant in the network broadcast his calculated hash to all
participants.

In this case, other participants receive hashes when broadcasted with 0.0001 probability of discovery of a couple (same two hash values) belonging to a same community.

Participants of C(j) compare the received hashes (n-1) each hash
with other 1/0.0001 salted hashes stored in the secret cache table,
they all definitely discover their peers after some time.

Maximum Time of Discovery for all participants to their communities is:  (n) * 1000. This calculation can be done parallelly.

This way, all communities {C0, …, Cm} are formed secretly.

NB: I mentioned this in the context of IOT, but obviously it is very abstract.

The question now is: What are flaws ? and How is this problem addressed otherwise ?

Edit1:

I guess I should read about the socialist millionaire problem as I just knew about.

Edit2:

This can be perfectly achieved in a secure way using: Diffie-Hellman exchanges

How big is the secret key that defines a community?

If it is trivial, say a number between 1-100, then an attacker can easily calculate 100.000 hashes to know in which community each user is.

If the secret s is long, say 64 bytes, then I don't see the usefulness to generate 1000 hashes for each option. Then it would be best to just send your hash H(s+n), with a random nonce n you used (as knowing the nonce and the hash would not help anyone else to know the secret).


Is there any relation between two strings with the same MD5 hash? Is there any relation between two strings with the same MD5 hash?

For example these two strings:

0e306561559aa787d00bc6f70bbdfe3404cf03659e704f8534c00ffb659c4c8740cc942feb2da115a3f4155cbb8607497386656d7d1f34a42059d78f5a8dd1ef

and

e306561559aa787d00bc6f70bbdfe3404cf03659e744f8534c00ffb659c4c8740cc942feb2da115a3f415dcbb8607497386656d7d1f34a42059d78f5a8dd1ef

have the MD5 hash:

cee9a457e790cf20d4bdaa6d69f01e41

Does any regular relation between these two strings or any strings with the same MD5 exist?

In general, no: two bitstrings with the same MD5 need not be related by a simple relation (other than the obvious  have the same MD5). Argument: take $2^{128}+1$ distinct random $1024$-bit bitstrings; by the pigeonhole principle, at least two are bound to have the same MD5; since less than $2^{257}$ pairs of distinct bitstrings can be picked among $2^{128}+1$, and our colliding bitstrings where generated with $1024$ bits of entropy each, they must be unrelated in the sense that at least $1024-257=767$ bits from one can't be deduced from the other.

However, some of the efficient methods we have to generate two bitstrings with the same MD5, and all efficient methods that work for 512-bit bitstrings as in the question, produce bitstrings of the same length, and differing only by very few bits within each 512-bit block. The question's example matches that given by Tao Xie and Dengguo Feng in Construct MD5 Collisions Using Just A Single Block Of Message, 2010. That seems to be the first 512-bit MD5 colliding pair published, tough without disclosure of the method. For public method and code, see Marc Stevens, Single-block collision for MD5, 2012; (alternate link to the paper). The location of the bit differences are characteristic of the method, and the differential path it uses.

Further, for some of the first methods discovered to efficiently generate MD5 collisions, bit differences are bound to occur in two adjacent pairs of 512-bit blocks; see in particular Xiaoyun Wang and Hongbo Yu, How to Break MD5 and Other Hash Functions, in proceedings of Eurocrypt 2005.

To generate very different bitstrings with the same MD5 (including: starting with different chosen strings, and/or of different length), the best first known method required in the order of $2^{65}$ evaluations of the MD5 round function; see Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website). This would be feasible, was attempted over 11 years ago, but remains a little hard, and never was publicly done AFAIK.

Update: as pointed by otus, we now have more efficient methods allowing to generate colliding bitstrings with any chosen prefix using approximately $2^{16}$ less work (with the restriction that the bitstrings must have the same length, and be nearly identical in their last block). See Marc Stevens, Arjen Lenstra, Benne de Weger: Chosen-prefix collisions for MD5 and applications, in International Journal of Applied Cryptography, Volume 2 Issue 4, July 2012, Pages 322-359; the HashClash page on Chosen-prefix Collisions; this striking application to images.


Monoalphabetic cipher key I'm new to cryptography and have just completed homework on Monoalphabetic cipher.

I managed to decrypt the cipher text successfully but I cannot identify the key from my plaintext to ciphertext mapping table which is shown below (top is ciphertext and below in caps is what I have substituted with). No substitution were required for a, h and z. Notice r is substituted with B and y is substituted with y which I am a little confused with.

Although the decrypted message seems correct, I would like to understand what is the key for this.

a   b   c   d   e   f   g   h   i   j
    D   E   F   G   H   I       K   L
k   l   m   n   o   p   q   r   s   t
M   N   O   P   Q   R   S   B   T   U
u   v   w   x   y   z
V   W   X   Y   C

The key to a mono-alphabetic substitution cipher is a substitution table. Thus you already have (most of) the key for that cipher, it is

a   b   c   d   e   f   g   h   i   j
?   D   E   F   G   H   I   ?   K   L

k   l   m   n   o   p   q   r   s   t
M   N   O   P   Q   R   S   B   T   U

u   v   w   x   y   z
V   W   X   Y   C   ?

where the question marks are unknown parts.

Often instead of defining the table manually, some simple generation algorithm is specified, such as “Shift all characters by $n$ positions to the right”. But not every substitution table can be produced in a simple way.

However, in your case, a simple algorithm would be (assuming a $\rightarrow$ A, h $\rightarrow$ J, z $\rightarrow$ Z):

Write the ciphertext alphabet A … Z in the first row and below write the corresponding plaintext characters, that is "a, r, y" and then the remaining ones in alphabetical order:

A  B  C  D  E  F  G  H ...
a  r  y  b  c  d  e  f ...

So in some way, you can consider "ary" to be the key but knowledge of the algorithm is also required.


Finding IV in AES-128 having partial Key and plaintext Let's suppose we have the plaintext, 14/16 char of the key and the first 2 and the last 36 chars of encrypted data (that is 64 char long). What I want is to find the IV. The cipher algorithm is AES (I think 128).

As I said, both the Key and the IV are 16 char long, the plaintext is exactly 32 char long and the cyphertext produced is 64.

What tool / process can I use to find the IV knowing all of this stuff? Note that I don't know the full key, but I have a big part of it, so probably some bruteforce is needed.

The way to solve the problem is the following:

Bruteforcing the last 2 elements of the key.
With that key, trying to decrypt the second block of the ciphertext.
XORing that result with the second block of the plaintext.
Comparing the new result with the partial first part of the ciphertext.
If there is a correspondance we have found the right key (also the complete first ciphertext block), else go to step 1.

The last step is applying XOR to the decryption of the first block of the ciphertext and the first plaintext block. This should return the IV that we are looking for.

Since there is no padding (plaintext is 32 char long) this was not too difficult after a better understanding of the algorithm.


Encrypting firmware with AES and no IV I have an embedded device with a AES CBC engine on it that is used to ensure the integrity of the firmware. I know that CBC mode requires unique IVs to be any good, but I'm unsure if it makes a large difference in this scenario. The AES key is stored in hardware on chip, and before firmware is loaded, it's decrypted with the key using decrypt hardware also on the chip. If I understand this correctly, that would mean that the same key encrypting the same plaintext will always result in the same ciphertext, meaning it's deterministic. Assuming the attacker can obtain the encrypted firmware (but not the key, so he can't encrypt anything with the key), does the fact that no IV is used really make a difference?

Let me see if I have this right (and please correct me if I misunderstand; my conclusions depend on the details of this); you distribute images for your firmware device; these images are encrypted with a secret AES key (using AES in CBC mode); the device decrypts the image, and then runs that decrypted image.  The sole check to make sure that the image wasn't tampered with is the hope that a modified image would not decrypt to anything intelligible.

If the above is all true (and personally, I hope that I'm wrong and you're doing more than this), then you have bigger problems than having a fixed IV.

The problem is that you're assuming that an attacker cannot modify the image to make changes that he picked out; the problem with CBC mode is that, to a surprising extent, he can.  Here's one way he can do this: suppose you have a constant initializer in your image, as follows:

  static int important_variable = 3;

Suppose further that the attacker decides that he'd get an advantage if that important_variable was initialized to 5.  What the attacker could do is find where the constant 3 appears in the image, and (here's the tricky bit) exclusive-or the previous block in the ciphertext by 6.  To see what this does, let us review how CBC mode decryption works:

$$P_i = C_{i-1} \oplus D_k( C_i )$$

(where $C_{i-1}$, $C_i$ are the ciphertext blocks, and $P_i$ is the decrypted blocks.

Now, the attacker has no idea what the key $k$ is, however he doesn't care, he knows that $3 = C_{i-1} \oplus D_k(C_i)$.  By adjusting $C_{i-1}$ into $C'_{i-1} = C_{i-1} \oplus 6$, and making no changes to $C_i$, the modified ciphertext will decrypt there into $P'_i = C'_{i-1} \oplus D_k(C_i) = C_{i-1} \oplus 6 \oplus D_k(C_i) = 6 \oplus 3 = 5$, hence making the change he desired.

The sole disadvange (as far the attacker is concerned)?  The previous block $P_{i-1}$ will decrypt to something unpredictable (because he has no idea what $D_k(C'_{i-1})$ evaluates to), however that block might not be important.

The bottom line: if you care about integrity (as opposed to secrecy), you need to use a cryptographical primitive that gives integrity guarantees (such as a Message Authentication Code or a signature).


Convincing "someone" on the (in)validity of DH tuple without revealing $u,v$ Is there a way of convincing someone on (in)validity of Diffie Hellman tuple $<g, g^u, g^v, g^{w}>$ without giving away $u,v$.

or at least solve the Decisional Diffie Hellman Problem without revealing $u,v$.

[Considering the prover knows exactly one of $u$ or $v$]?

I would appreciate references to papers (however I am avoiding Interactive Proofs for this)

That depends on the groups you are working in.

Using a $\Sigma$-protocol

If you have a group $G$ of prime order $q$ where the DDH is hard and you have a DH tuple $(g,g^u,g^v,g^w)$ with $w\equiv uv \pmod q$, then if your prover
knows one of these values, say $u$, then we can write the DH tuple as $(g,g^u,h,h^u)$ and he is able to
convince a verifier that this is a DH tuple by means of a standard $\Sigma$-protocol, see here (Section 5)
for a concrete protocol. This proof can be made non-interactive by using the Fiat Shamir heuristic.

Gap DH Groups

If you are working in a gap Diffie Hellman group setting, i.e., a setting where the DDH is easy but the CDH is still hard, that is easy without interactive proofs. I use additive notation for groups $G_1$ and $G_2$ below as we are talking about elliptic curve groups.

For instance, take a symmetric cryptographic pairing $e:G_1\times G_1 \rightarrow G_T$ where $G_1$ is an elliptic curve group of prime order $p$ and $G_T$ a multiplicative subgroup if a finite field of the same order $p$. Then $G_1$ is a gap DH group.

Then given $(P, uP, vP, wP)\in G_1^4$ you can check if this is a DH tuple by checking if $$e(uP,vP)\stackrel{?}{=}e(wP,P).$$

Same works for an asymmetric type-2 pairing $e:G_1\times G_2\rightarrow G_T$, where you have an efficiently computable homomorphism $\psi: G_2 \rightarrow G_1$. Here $G_2$ is a gap DH group and when given a DH tuple $(P', uP', vP',wP')\in G_2^4$ you can efficiently check it by checking $$e(\psi(uP'),vP')\stackrel{?}{=}e(\psi(P'),wP').$$

Side note (which at least I find interesting)

An interesting side note is that the Chaum Pedersen signature scheme uses the first approach in DDH hard groups, where the proof is made non-interactive by using the Fiat Shamir heuristic. Here, the DH tuple to check is $(g,g^x,m,m^x)$ where $\sigma=m^x$ is a signature for $m$ w.r.t. public key $h=g^x$ and they require a non-interactive proof $\pi$ that $\log_g h=\log_m \sigma$, i.e., to prove that the signer actually knows the secret key $x$.

The BLS signature scheme essentially does the same in gap DH groups where they do not require this non-interactive proof $\pi$, but can use the pairing $e$ for checking the DH tuple. However, they have to hash the message to a group element using a secure hash function $H$, as the direct application of the Chaum Pedersen approach would make the signature scheme insecure (as otherwise one could forge signatures without the secret key). Here the DH tuple to check is $(P,xP,H(m),xH(m))$ where $xH(m)$ is a signature for $m$ w.r.t to public key $xP$.


RSA: How to compute the number of possible plaintexts if $e$ is not coprime to $\varphi(n)$? I'm studying for an exam next week, and there are two questions that me and my friend don't understand:

Question 1:
Let $p,q$ be big prime numbers and $n=pq$.
Let $e$ be a number between $1$ and $\varphi(n)$ such that $e\mid(p-1)$, $e\mid(q-1)$.
For a plaintext $M$, the ciphertext is $C=M^e \bmod n$.

How many different $M$s will be ciphered to the same $C$?
Edit: what is the maximum number of messages $M$ that will yield to the same $C$?
Why is the answer $e^2$?

Question 2:
Let $p,q$ be big prime numbers and $n=pq$.
Let $e$ be a number between $1$ and $\varphi(n)$ such that $\gcd(e,p-1)=a > 1$ and $\gcd(e,q-1)=1$.
For a plaintext $M$, the ciphertext is $C=M^e \bmod n$.

How may different $M$s will be ciphered to the same $C$?
Why is the answer $a$?

Both questions can be answered using the same kind of argument.

First, observe that in both cases we are really only interested in the number of $e$th roots of unity in $\mathbb Z/n$: Any $e$th root of unity can be multiplied to some $M$ without changing the value of $M^e\bmod n$, and two different $M$ with equal $M^e\bmod n$ differ by an $e$th root of unity. Thus we restrict our attention to the case $M=1$.

For succinctness, I will sometimes write only root for "$e$th root of unity".

The Chinese remainder theorem gives an isomorphism of rings
$$
  \pi\colon\; \mathbb Z/n \cong \mathbb Z/p \times \mathbb Z/q
  \text.
$$

The image of $x^e\bmod n$ under $\varphi$ is $(x^e\bmod p,x^e\bmod q)$.
Some element $x\in\mathbb Z/n$ is a root if and only if both components of $\varphi(x)$ are roots in $\mathbb Z/p$ and $\mathbb Z/q$.
In other words: Each root in $\mathbb Z/n$ "consists" of roots in $\mathbb Z/p$ and $\mathbb Z/q$, and vice-versa.
Thus, if $\mathbb Z/p$ has $a$ roots and $\mathbb Z/q$ has $b$, the ring $\mathbb Z/n$ has $ab$ roots.

Now note that the order of the cyclic group $(\mathbb Z/p)^\ast$ is $p-1$, thus if $e$ divides $p-1$, there must be an element $r$ of multiplicative order $e$ in $\mathbb Z/p$. Its powers $r^1,r^2,\dots,r^{e-1}$ are nontrivial $e$th roots of unity in $\mathbb Z/p$, thus (including $1$) there are $e$ roots in $\mathbb Z/p$.
There cannot be more than $e$ roots since $\mathbb Z/p$ is a field.
Of course, the same holds for $q$.

Armed with that knowledge, let's tackle question 1: If $e$ divides both $p-1$ and $q-1$, there must exist $e$ different roots in both $\mathbb Z/p$ and $\mathbb Z/q$. Thus, by the above, there are $e^2$ different $e$th roots of unity in $\mathbb Z/n$.

As to question 2: Since $(\mathbb Z/q)^\ast$ has order $q-1$ and $\gcd(e,q-1)=1$, the map $x\mapsto x^e\bmod q$ is a permutation on $\mathbb Z/q$. In particular, there are no nontrivial $e$th roots of unity in $\mathbb Z/q$.
Concerning $\mathbb Z/p$, note that the map $x\mapsto x^{e/a}\bmod p$ is a permutation since $e/a$ is coprime to $p-1$. Thus, $1=x^e=(x^a)^{e/a}$ in $\mathbb Z/p$ if and only if $x^a=1$. As $a\mid p-1$, we can apply the above results (with $a$ in place of $e$) to conclude that $\mathbb Z/p$ has $a$ roots, thus $\mathbb Z/n$ has $a\cdot 1=a$.


Time trade off, or in your case, time-memory tradeoff, works by having massive "rainbow tables" that show you ALL hashes in a hashing algorithm (probably MD5, or other low security algorithm). A "Rainbow Table" saves you time and processor power, rather than having a hash cracker eat up your ROM, but are probably many gigabytes large. The trade-off then becomes size vs. time & power. If this doesn't satisfy you, or this seems like it's missing something, there is PLENTY of research being done on hash cracking, and even a youtube channel called "Computerphile" that has a better explanation on this than me.


Usage and limitations of sponge functions for PRNG This HRNG uses SHA3 as a sponge function (in its device driver) to inflate ots raw source output to many MByte/s. They compare this output rate to the output of other HRNG which don't use a sponge function. I'm wondering if this comparison is fair and brings me to the question to which extend a sponge function should be used to inflate RNG. The goal should be to get entropy suitable for cryptographic operations (e.g. key generation).

Edit: In other words, if a sponge function could be used to inflate 300 kByte/s to 500 MByte/s without reducing the entropy, why--talking Linux--to use /dev/random in favour of /dev/urandom at all?

I'd say the comparison table is not a fair one, as it compares the Infinite Noise generator's throughput when feeding bits into a CSPRNG (Keccak) running on the host workstation and then running that CSPRNG as fast as the workstation allows. Other devices in the table achieve ~10 Mbit/sec speeds, but all of those devices in the table which had enough design documentation published on the web seem to advertise their throughput based on whitened output, but not on output expanded via a seeded CSPRNG on the host.

All of this is “much ado about nothing” however. A single 256-bit seed and a fast-key-erasure CSPRNG is all one should ever want in the real world. Don't create a persistent channel for attacker-controlled input. Or just use /dev/urandom.


How do I sign data that's been encrypted using public key? (RSA) I've received a public key to encrypt my data for the other end to decrypt using their private key. Now, they want us to sign the data as well to ensure non-repudiation.

I thought that I should only sign using a private key (which isn't in my possession). How do I sign my encrypted data?

This is impossible - the receiver knows nothing about you so there's no way he can assure that the sender is in fact you.


Hashing a hash for authentication I currently use Argon2 to derive a key (I will use a salt which I will save in a file as plaintext for when I later need to derive a key again) from a given password which I will use to encrypt a file (Algorithm: AES CBC PKCS7Padding).

When a user enters the password I need to verify it is the correct password, storing the key or the password will of course break the encryption (since if it's the key they can just decrypt, if it's the password they can derive the key again)

So from what I can see I have 2 options

Use Argon2 as a hash function instead of a KDF function and store the result (I will change the salt between the 2 Argon2 invocations), you can probably guess this will be very slow.
Hash the key with SHA-256

To verify I will just re-hash with either option 1 or option 2 and check if it matches.

Questions

Would option 2 achieve the same security as would option 1?
If I use option 2, for the salt, should I use a new generated salt specifically for that (which I will store in a file as plaintext for later verifications) or use the salt I used with the initial Argon2 KDF or use no salt?

Running Argon2 (or any other key-stretching KDF) twice to generate two different keys (or other outputs) from the same password is not a good idea, since it makes key derivation twice as slow while not making the password any harder to crack by brute force.  Or, in other words, it makes the password twice as fast to crack compared to just running the KDF once with twice as many iterations.

Hashing the key with a secure cryptographic hash, such as SHA-256, and storing the hash alongside the encrypted data is a perfectly good and secure way to implement a key check value.  You don't even need to store the entire hash; just, say, the first 32 or 64 bits of the hash should be plenty to catch any accidentally mistyped passwords.

Alternatively, you could use the Argon2 output as the input to a fast non-password-based KDF such as HKDF-Expand and use it to derive both the encryption key and a separate check value.  This is a general solution that will work whenever you want to derive multiple quasi-independent keys (or check values etc.) from the same password.  In particular, this method provides a stronger guarantee of independence than your suggestion of hashing the key: not only can the key not be calculated from the check value, but (assuming the the underlying hash function is not very badly broken) the check value also cannot be calculated from the key.


Best suitable column type for openssl $tag,$iv,$key,$encrypted? Which column type is best for storing  $tag, $iv, $key, $encryptedData  generated by openssl_encryption, and in which format I should save these values?
I am using "aes-128-gcm" cipher method.

One can store all of the information as $$IV\mathbin\|encryptedData\mathbin\|tag$$ as concatenated in a blog object (though there is a limit for the size of a column).
But not the key!

The key must never be stored with the data itself. This simply a bad way for security since there is no need to store the data as encrypted beacuse if an attacker can access the database we can assume that the data is not encrypted at all. One need to store the key elsewhere like HSM or drive from a password with a KDF.

As it is well-known for AES-GCM that one need to use an IV and Key pair only once. If a pair occurs twice the confidentiality is lost. The crib-dragging technique removes the messages but not the key. The attacker will x-or the two or more encrypted messages to the x-or of the messages
$$C_1 = M_1 \oplus keystream$$
$$C_2 = M_2 \oplus keystream$$ then
$$M_1 \oplus M_2 = C_1 \oplus C_2$$ and a passive attacker has the access $C_1 \oplus C_2$ since they are listening the channel. Now, they need to execute crib-dragging and that can be automated.

A Natural Language Approach to Automated Cryptanalysis
of Two-time Pads

Only the key stream of CTR mode of operation is revealed. AES-CTR secure against the key finding, actually more formally it is CPA secure. (The GCM forgery is another case Even a single AES-GCM nonce reuse can be catastrophic.).
To mitigate this one needs to check the IV reuse, assuming there is only one key, then using a single column for the IV is a good choice. Querying the database for the existing of the IV can prevent the issue and faster than storing all in one column.
Actually, one can use the unique rowID for the IV for the GCM if data is not updated. This is like the counter mode suggested by the NIST.
There is one big issue here, though. If one updates a row and if an attacker observed the row before and after the update then the IV reuse occurs here.  In this case, one need to generate the IV independent of the rowID and this is better since the data may be fixed today but not tomorrow.


Pre-Image Resistance of repeated, patterned SHA2-256 digests Suppose $H = \operatorname{SHA2-256}$.

Let $H_1 = H(\text{“Alpha1”})$.

Let $H_2 = H(\text{“Alpha2”})$.

…

Let $H_N = H(\text{“AlphaN”})$.

So all these digests are based off a common pre-image post-fixed with the index.

Question 1: Does knowing the values $H_1, \dotsc, H_N$ and the length of common pre-image substring "Alpha" leak any information about "Alpha"?

Question 2: Would double-hashing make any significant difference to pre-image security? E.g.: $H_i = H(H(\text{“Alpha”} \mathbin\| i))$

Question 1: Does knowing the values $H_1, \dotsc, H_N$ and the length of common pre-image substring "Alpha" leak any information about "Alpha"?

Only in the sense that it enables an adversary to test a guess for what the string might be.  In particular, suppose the random variable $X$ has some probability distribution as far as you know.  Knowing what $H(X \mathbin\| i)$ is narrows down the probability distribution on $X$ a great deal—possibly even to a unique value—and enables you to test a guess which you might not be able to do without knowing $H(X \mathbin\| i)$, but there's no way known to search for what $X$ might be cheaper than brute force.

Of course, if $X$ is simply (say) uniformly distributed among the English names for Greek letters—Alpha, Beta, Gamma, etc.—then the brute force search is already pretty cheap!  Any security arises from a distribution with many more possibilities and much lower probabilities than $1/24$.

  Question 2: Would double-hashing make any significant difference to pre-image security? E.g.: $H_i = H(H(\text{“Alpha”} \mathbin\| i))$

No; at most, it would slightly raise the false positive rate for a search.


What is the probability that $(m_1,m_2,m_3)$ is a "cover"-triple for random $m_1,m_2,m_3$? Let $H: \{0,1\}^*\to \{0,1\}^n$ be the random oracle. A "cover"-triple is a triple $(m_1,m_2,m_3)$ such that
$$\bigwedge_{i=1}^n \left( \left(H(m_1)_i=H(m_2)_i\right) \vee \left(H(m_1)_i=H(m_3)_i\right)\right)=1, $$
where $H(\cdot)_i$ denotes the $i$ bit of the output.

What is the probability that $(m_1,m_2,m_3)$ is a "cover"-triple for random $m_1,m_2,m_3$?

How am I suppose to find the $\Pr[(m_1,m_2,m_3)]$? I believe that the space I am suppose to consider is $\{0,1\}^n$ since by the definition of "cover"-triple we have $H(m_j)$ where $j=1,2,3$.

Assume $H(m_k)_i$ is uniform over $\{0,1\}$ for all $i,k$ and independent of any other $H(m_k')_{i'}~$, since you have a random oracle.

Let $H(m_1)_i=0$ (the same argument would work for it being one) then $$\mathbb{P}[H(m_2)_i\neq 0~~and~~H(m_3)_i\neq 0]$$ is $(1/2)^2$ by independence.

This gives probability $3/4$ that the $i$ bit of $m_1$ is covered by either of  the $i$ bit of $m_2$ or the $i$ bit of $m_3$ .

This would give the answer $$\frac{3^n}{4^n}$$ which goes to zero exponentially with $n.$