AES vs Blowfish taking key-length into account I understand that Blowfish is getting old, but is still a secure algorithm, and that AES is very popular, and is recommended by most people.  My question is, how do the two compare when a 256-bit key is used for AES, and a 448-bit key (the maximum according to the standard) is used for Blowfish?  Would Blowfish with a 448-bit key be more resistant to brute-force attacks? Are there any other considerations? (let's assume that we already agree that 256-bit keys are sufficiently resistent to brute-forcing).

Blowfish has a 64-bit block size whereas AES has a 128-bit block size, so you are sort of comparing apples and oranges (there are some things you can do in AES which would be unwise in Blowfish, in particular Blowfish in CTR mode can be distinguished from a random stream after only a few dozen gigabytes of output - see fgrieu's answer here, replacing 128 by 64 in the calculations).

As for strict brute force complexity, I think you've pretty much answered your own question, if we assume that 256-bit keys are sufficiently resistant to brute-forcing then using a longer key makes no sense. It's like trying to decide what's best between "infeasible" and "infeasible". But theoretically speaking, Blowfish uses all 448 bits of the key, so a brute-force attack would take on average $2^{447}$ guesses at the key, whereas AES would take $2^{255}$ guesses on average (AES-256, that is).

Now if you want to take cryptanalytic advances into account, AES-256 has a much lower margin of security (break complexity / brute-force complexity) than Blowfish, though both remain secure today. That said, it should be kept in mind that since AES is the Advanced Encryption Standard, it has received considerably more attention from cryptographers than Blowfish!


AES-CBC and IV -- Encrypting multiple blocks of a file with the same IV? I have large files which are broken into blocks of 512 KB and uploaded to a server. In my DB I store the IV, and the user knows the security key themselves.  When downloading, I use the same IV and key.

However, is it insecure running AES-CBC on each different block with the same IV? Won't this give away information -- e.g. 1 512 block encrypted will equal the next 512 block if they are both identical? And if I can't load the entire file into memory at once, is the only safe way to do it storing many IV's? (100 GB file would have 200k IV's...)

It is insecure to reuse the $IV$ with AES-CBC. At the very least, if the files have a common prefix, this will be revealed as a common prefix of the ciphertexts. For AES-CBC, the only way to ensure confidentiality is to use random $IV$s.

However, if you are not restricted to a particular CBC mode, the nonce-based Counter mode (CTR) might solve your problem. Each block is then encrypted with unique number (nonce) $N$ instead of $IV$. It does not have to be secret, moreover, it can be predictable (for example, it can be the block index).

Another option is to try modes of operation dedicated to small-block encryption.  XTS, which employs key-dependent tweaks instead of IVs and nonces, is a widely used example.


Picking a nonce in the context of CCM (CTR with CBC-MAC) mode After having read the RFC 3610: Counter with CBC-MAC (CCM) and the Wikipedia article on CTR mode, I'm not sure how a nonce should be picked.  The RFC says:

  A nonce N of 15-L octets.  Within the scope of any encryption key
     K, the nonce value MUST be unique.  That is, the set of nonce
     values used with any given key MUST NOT contain any duplicate
     values.  Using the same nonce for two different messages
     encrypted with the same key destroys the security properties of
     this mode.

If the nonce values must not contain any duplicate elements doesn't this imply that they should be known to all parties in a transaction. For instance if a client wishes to authenticate and communicate with a server, shouldn't they both have a predefined set of nonces. If not, how should they be exchanged, given that the context only allows for CTR-AES encrypted messages?

Yes, if the client and the server use the same key to encrypt their messages (instead of having separate keys for client-to-server and server-to-client communication), then you need to ensure that they cannot ever use the same nonce.

One way to do that would be to, say, let the client use only even nonce values, and let the server use only odd nonce values.  Of course, other ways of partitioning the nonce space are equally possible.


Why are ed25519 keys not recommended for encryption? Was wondering why there is no straightforward way of using ed25519 keys for encryption.
Then I found this: https://github.com/indutny/elliptic/issues/108
There it is stated that it's unlike RSA not recommendable for this purpose - one should rather derive a Symmetric key from diffie-hellman style shared secret.
It is rather used for signing. But if signing works like this:
hash = doHash(message)
signature = doAsymetricEncrypt(hash, privateKey)

hash == doAsymetricDecrypt(signature, publicKey) //true

So I would assume it should also work in this direction.
encryptedToken = doAsymetricEncrypt(token, publicKey)

token = doAsymetricDecrypt(encryptedToken, privateKey)

My current understanding of the relevant matter boils down to:

asymetric cryptography works in both directions: encrypt with private key -> decrypt with public key & encrypt with public key -> decrypt with private key
ed25519 private key is just a random 256bit number
the public key may be unambigously derived by projecting the private key number over the curve25519
ed25519 actually means the version as DSA in combination with sha-512

So I would assume that when I have the 32bytes for the private key and know that it is exactly such key. I should be able to just use it in any context regardless of using it as signature or encryption algorithm.

You seem confused about a few things.  Bear with me, this is a very common confusion!
Encryption is defined with the intent of confidentially transporting information: if you encrypt information, it is meant to be hidden until decrypted by the receiving party.  Note that in your pseudo code
hash = doHash(message)
signature = doAsymetricEncrypt(hash, privateKey)

hash == doAsymetricDecrypt(signature, publicKey) //true

... it is impossible to retrieve message from your "ciphertext" signature: you can only retrieve the hash.  Secondly, you are encrypting with a private key, and  decryption happens with the public key, which means that any party can decrypt your hash, because your publicKey is obviously public.
A digital signature is a mathematical scheme for verifying the authenticity of digital messages or documents (wikipedia).  Note that this is never defined in terms of encryption. Let me stress this: if you have a teacher that claims that "a signature is an encryption with a private key", they are wrong.  If you have a book that claims this, throw it out, burn it -- don't give it away, because it clearly causes confusion -- and get a better book.  Encryption is for confidentiality, signatures are for authenticity.
That said: the source of this confusion is in the mathematics of RSA.  In RSA (and not in ECC!), the operator for text-book signatures is the same operator as for encryption, with the key material swapped.  Note that the mathematical operation is the same thing, not that signatures "are encryption with the key swapped", although they look like they do.  Also note that this is for text-book RSA, which is never deployed as-is, but requires padding and randomization that is different between signatures and encryption.
So, while your pseudo-code might or might not work with RSA (depending on the library you use), it will not be secure at all, and will simply not work with ECC because the key material cannot be swapped, because the mathematics behind it simply do not support it.

Now, to finally answer your question, encryption with elliptic curves exists, is widely used, and is called ECIES. It indeed boils down to a Diffie-Hellman exchange and using a symmetric algorithm afterwards.  There is also ElGamal encryption, if you have very short messages.
It is another question whether it is secure to reuse the same key for ECIES and EdDSA signatures at the same time though.


BB84 - Bits needed to detect Eve's presence From Quantum Computing: A Gentle Introduction:

  In the BB84 protocol, how many bits do Alice and Bob need to compare to have a 90% chance of detecting Eve's presence?

I am having some trouble calculating this value. I understand that 50% of the time, Eve measures in the wrong basis and sends Bob a different bit than Alice sent, and after Alice and Bob compare their measuring bases, on average, Bob is left with 50% of his measured qubits. Therefore, given that Eve eavesdropped, there is a 25% probability that a given remaining bit is wrong. From this information, how would I calculate the number of bits needed to detect Eve with 90% confidence?

Remember that Alice and Bob will only compare those measured qubits that they both measured in the same basis. As you said, on average this will be about 50% of the total qubit stream, but this doesn't actually affect the calculation needed.

As you said, Eve will measure using the wrong basis about 50% of the time. However, even when she does measure using the wrong basis, there is still a 50% chance that Bob receives the correct bit-value. To be explicit, say Alice and Bob decide to compare a qubit after learning they both measured it in the standard basis. Alice had sent Bob a |1> qubit, and Eve then intercepted it, but measured it in the Hadamard basis, yielding either |+> or |->. Finally, Bob measured this state in the standard basis, and will have "correctly" measured |1> about 50% of the time.

Given that Eve measures in the correct basis and is undetectable 50% of the time, and she measures in the incorrect basis but is still undetectable about 50% of the remaining 50% of the time, it follows that she is only detectable with probability 25% on each compared qubit. So your bounds do indeed hold, if for a slightly different reason.


Is it possible to build a compact proof of the sum of all even numbers of a dataset? Suppose I have a set of numbers:

[1, 7, 6, 4, 8, 9, 4, 6, 3, 3, 1, 5, 4]

Suppose also that a verifier knows the merkle root of that set, R, but he doesn't know the set itself. Is it possible to convince him that the sum of all even numbers - i.e., 6 + 4 + 8 + 4 + 6 + 4 is 32 with a string of a small, constant size (i.e., not depending on the length of the array)?

I thought that was possible with zk-snarks, but now I'm under the impression even a zk-snark proof would be of linear size w.r.t the number of elements.

Let's ignore the zk requirement. And focus on compactness. If we have a merkel tree and I swap just one element at random so one of the hashes is invalid and doesn't match the data. We get a merkel tree with almost all valid hashes. Someone would have to verify all of them to catch the foegery. If you only sampled a few paths you would gain little confidence.
Any extra calculations you require on the tree could be done onhe forged version. I'm afraid your request is impossible.


Double-and-add/Montgomery VS blinding I'm having a hard time understanding why people use constant-time techniques to counter time-attacks, when blinding seems as good and cheaper to implement.

Why do people avoid blinding in ECC?

Good blinding requires good randomness. Randomness is a hard requirement, especially for embedded systems. In a similar vein, the DSA and ECDSA signature algorithms require a strongly random integer (called k) for each signature, and several implementations have failed to use random enough values, with hilarious consequences; the most well-known case is Sony and the signatures protecting the PS3 firmware (they used a fixed k...), but a number of Bitcoin-related "electronic wallet" applications also botched things similarly. This even prompted the specification of deterministic variants of DSA and ECDSA, to avoid the need for randomness. If good randomness cannot always be obtained for (EC)DSA signatures, then one has to assume that good randomness cannot always be obtained either for secure blinding.

Another point is that timing attacks have evolved over time. The "classical" timing attack on RSA, described by Kocher in 1996, only uses a measure of the complete computation time. However, modern, fashionable variants use accesses to cache memory or jump prediction within the CPU to obtain a lot of information from even a single run of the attacked implementation -- especially in contexts where the attacker can run his own code on the same core (hyperthreading) or in a close core (even across virtual machines). It is unclear how well blinding holds against that kind of attack. Common wisdom is that such attacks are very hard to pull off in most cases (and they have not been observed "in the wild" yet), but it is also very hard to ascertain whether they apply, or do not apply, to a particular situation. A general-purpose library has then little choice but to play safe, and go for constant-time code.

Also, in the case of binary curves (curves over a field $GF(2^m)$), Montgomery's ladder (as described by López and Dahab in 1999) can be adapted to binary curve and yields a verify efficient point multiplication algorithm that is both constant-time (provided you use constant-time conditional swaps, which is no hardship) and fast (6 field multiplications per bit). It is not easy to do better than that in all generality, especially on modern x86 hardware with the CLMUL instructions (when field multiplications are slow, point-halving is better, but not when field multiplications are very fast).

Last but not least, many implementers are motivated by the intellectual challenge of coding (especially in open-source projects), and constant-time code is a lot more fun than blinding. Blinding is crude and inelegant. Who wants to spend his weekends implementing blinding ?


Creating certificate: Where is my private key stored? I have some problems to understand the storage of my private key when a CA generates my key pair. Let's assume the CA creates my key pair, issues the certificate with my public key and signs it with the corresponding private key. So MY private key is first stored at the CA and after issuing of my certificate I will get my private key? Is that right?

Typically you send a Certificate Signing Request (CSR) to the CA. The CSR contains everything you want to be inside your certificate, including your public key. The CA takes a look, and if it likes it, creates a certificate and signs it and sends it back to you. The CA never has to see your private key.


Attack on RSA when I know $e$, ciphertexts $c_1, c_2$ of the same message $m$ with 2 coprime modules? I know that the same message $m$ was sent to two people resulting in ciphertexts $c_1, c_2$. The public keys are $n_1$ and $n_2$, $gcd(n_1, n_2) = 1$. And $e=3$ in both cases. How can I retrieve the original message without brute-forcing it?

I.e. the exponent $e$ is the same in both public keys, but the modulus $n$ is different: $n_1, n_2$.

The problem seems like a variant of Håstad's broadcast attack, except that is usually stated with $e$ ciphertexts, when here there is $2<e$ ciphertexts.

We know $m^e$ modulo $n_1$ and modulo $n_2$ (that's the givens $c_1$ and $c_2$), thus we can compute $m^e\bmod(n_1\,n_2)=y$ using the Chinese Remainder Theorem, per $y\gets(n_2^{-1}(c_1-c_2)\bmod n_1)\,n_2+c_2$

If we are lucky enough that $m<\left\lfloor\sqrt[e]{n_1\,n_2}\right\rfloor$ (roughly, $m$ of bit size less than $1/e$ of the sum of the bit sizes of the moduli), then $y$ will be exactly the $e^\text{th}$ power of some integer $x$, we can get that $x$, and it will be $m$.

If not, we can try, for incremental $i$, if any of the $y_i=i\,c_1\,c_2+y$ is exactly an $e^\text{th}$ power; that slightly extends the attack.

Note: none of this is RSA as correctly practiced. What's raised to the power $e$ modulo $n$ should not be the message, but a randomly padded message (per e.g. RSAES-OAEP) computed separately for each ciphertext sent, and almost as wide as the public modulus.


What would the implications be of a single randomly discovered SHA-256 collision? Imagine if someone messing around with hashes accidentally came across two inputs to SHA-256 that produced the same output.  Not a concerted effort, not Google/NSA or crypanalysis. No tin foil hats.  Just random chance in say a high school. And they made the two inputs public knowledge.  Whilst highly improbable, not mathematically impossible.  And just that one collision.

What would be the implications?  Would people simply say "Well it had to happen someday" and carry on as normal, keeping the hash as is? Or would SHA-256 have been "broken" and an upgrade sought?

An answer to Are there any well-known examples of SHA-256 collisions? suggests that it would be major.  Even if it happen entirely by chance?

Your question is a contradiction. If it actually is randomly discovered, then there are no implications because it is, well, random. If it were truly the result of luck, then so what? But the more likely explanation is that SHA-256 is really, very badly broken. I personally would not believe that anyone came up with such a collision by chance without testing an enormous number of possibilities.

Note however that, due to the length extension attack, a single public collision could be used to make more collisions with the same prefix. This could have security implications in practice. Additionally, if the collision came about through a non-generic attack against the hash itself, it may be possible to adjust it to find more collisions (see Luis Casillas's answer). This isn't the case if the collision was random.

Think of it another way. If I posted a list of all the passwords you have ever used online, and claimed I just got lucky and was posting random numbers from an RNG, would you believe it, or would you instead suspect that I had hacked your computer and was stalking you?


Do people sign my subkey? So, I've generated my GPG key pair. Created a subkey for signing and a subkey for encryption. Exported the whole thing, removed my master key pair to a secure place, re-imported only the subkeys. Now, I take my fingerprint and passport to a signing party and folks verify my identity and go pull my key off a keyserver, sign it, and upload it back to the key server.

After refreshing my keys I now have their signature on my private subkey?

Does that mean upon receiving a signature from someone else I need to go get my master key pair and sign it with my private subkey or?

If I lose my laptop before transferring signatures to my main keypair they are lost forever?

See this explanation. The 0x10 signature (typically belonging to a different individual) is applied to one's master/primary key, not to 0x18 subkey signature packets used for signing, encrypting, and authenticating.
Remember, CA responsibilities are decentralized with the PGP Web of Trust and the one's master/primary key can be used to sign other people's master/primary keys that also act as a reputation. By signing other people's master key(s), those people can revoke and re-issue subkeys as needed (with their reputation) without the involvement of those that have applied 0x10 signatures.
With more recent gpg code, the signing subkey will have a 0x19 backsignature when created.


Is there a cryptosystem which allows slicing and concatenating strings without decryption? I want a cryptosystem with the following four functions:

declare function encrypt(text: string, key: CryptoKey): ArrayBuffer;
declare function decrypt(ciphertext: ArrayBuffer, key: CryptoKey): string;
declare function concat(ciphertext1: ArrayBuffer, ciphertext2: ArrayBuffer): ArrayBuffer;
declare function slice(ciphertext: ArrayBuffer, start: number, end?: number): ArrayBuffer;

These functions work such that for any two strings (text1 and text2) and key the following expression is true:

decrypt(concat(encrypt(text1, key), encrypt(text2, key)), key) === text1 || text2;

And for any string (text), index into the string (i), and key, the following is true:

const ciphertext = encrypt(text, key);
decrypt(concat(slice(ciphertext, 0, i), slice(ciphertext, i)), key) === text;

Essentially, I want to arbitrarily slice and concatenate the strings represented by ciphertexts without decrypting anything. Is this kind of cryptosystem possible? Can I use homomorphic encryption to accomplish this? Are there any systems out in the wild which do something like this? I assume the length of the original text must be inferable without the key to accomplish this.

EDIT: To avoid certain trivial solutions brought up in this answer, which simply concatenate/slice ciphertexts trivially using delimiters/tokens, I would like the following to be true as well:

const ciphertext1 = encrypt(text1, key);
const ciphertext2 = encrypt(text2, key);
concat(ciphertext1, ciphertext2) === encrypt(text1 || text2, key);

const ciphertext = encrypt(text, key);
slice(ciphertext, i, j) === encrypt(text.slice(i, j), key));

// I’m using typescript as pseudocode but assuming equivalent ArrayBuffers are tripe-equals equivalent here, even though they aren’t

Unless you add further restrictions, it is possible to achieve what you are asking for, using a totally trivial construction. For example, the encrypt algorithm can output ciphertexts of the form "normal ciphertext: $c$". The concat algorithm can output ciphertexts of the form "concatenation of $c_1$ and $c_2$". To be clear, I am proposing that ciphertexts in this scheme literally start with the strings "normal ciphertext", and "concatenation of", etc. The decrypt algorithm can just parse and do the right thing for ciphertext of these different forms.

I'm sure this is not what you want. So if you don't want to trivialize the question, then you will need to add some other kind of requirement. For example:

The output of $\textsf{concat}(\textsf{Enc}_k(m_1), \textsf{Enc}_k(m_2))$ is indistinguishable from the output of $\textsf{Enc}_k(m_1 \| m_2)$.
Even with knowledge of $k$, the output of $\textsf{slice}(\textsf{Enc}_k(m), i, j)$ doesn't leak any information about $m$[$:i$] or $m$[$j:$].

There could be several reasonable ways to define away the trivial solution.

I'll also point out that this property is clearly incompatible with CCA security. The best you can hope for is CPA security.

CTR-mode encryption supports slicing, at least at the block level. If $(iv, c_1, c_2, \ldots, c_n)$ is a CTR-mode encryption of $m_1, \ldots, m_n$, then $(iv+i-1, c_i, \ldots, c_j)$ is a CTR-mode encryption of $m_i, \ldots, m_j$.

Most (all?) block cipher modes support truncation at the end, but not necessarily arbitrary slicing.

The best approach for allowing concatenation that I can think of is to just independently encrypt each block. I can't think of any approach that preserves the the additive ciphertext expansion of a typical block cipher mode.


Are XOFs and KDFs more usable than DRBGs? CSPRNGs have 2 design requirements:

output unpredictability,
back-tracing resistance.

In addition to which, NIST SP 800-90Ar1 added other features such as a) instance customization/personalization, b) operation administration (reseeding counter, etc.).

Of the three functions listed on Wikipedia page for CSPRNG, key and salt generation can be accomplished with any KDF (even ones based on plain hash functions), and nonce can be accomplished with a simple counter.

And with the introduction of dedicated-purpose XOFs in the SHA3 standard, the problem of producing arbitrary-length string from a finite-length one becomes solved along the way.

Both XOFs and KDFs are much easier to implement and use practically, so what's the point of designing DRBGs in the "NIST-SP-800-90A" way?

I don't know what the rationale behind the designs in the NIST SP800-90 standards were—internal discussions may be obtainable by public records requests—but I can hypothesize a few reasons:

Backtracking resistance.  While SP800-90C does cover KDFs (like HKDF and SP800-108), and while sponges are available now, there's more work to be done in SP800-90A to attain backtracking resistance:

A mere KDF, e.g. HMAC with a counter, does not necessarily provide backtracking resistance on its own unless you iterate it (like HKDF-Expand could be construed to do, but only for each info parameter independently).  Although it's not too difficult to show that this is safe—the expected length to cycle in the iteration of a large uniform random function is only square root of large, and it can't be much different for a pseudorandom function—application developers aren't going to prove this themselves and auditors want guidance from a standard.
A mere sponge XOF, e.g. SHAKE128, does not provide backtracking resistance on its own: if the full state is ever compromised, then you can simply evaluate Keccak in reverse until you get all the old outputs.  There are various ways you could work around this, but there's no one obvious natural way.

Hysterical raisins.  NIST SP800-90A predated sponge constructions, so the tools at hand were:

pseudorandom permutations (block ciphers) like AES
variable-input fixed-output hash functions like SHA-256
fixed-input variable-output hash functions like Salsa20 or AES-CTR
public-key cryptography for making back doors

Although Salsa20 used the model of a random permutation $\pi$ in the form $x \mapsto \pi(x) + x$ to approximate a random function, which in turn was used in ‘CTR mode’ to approximate a one-time pad, the pervasive design principle of building everything out of a single permutation—like we see now with Keccak, in SHA-3 and KangarooTwelve and Kravatte and Strobe, and even with other permutations like Gimli in libhydrogen—had yet to reach prominence.
Cost of collision resistance.  There seems to be a much higher cost to collision resistance than to preimage resistance.  But DRBGs don't need collision resistance.  So, e.g., AES-CTR_DRBG can presumably be faster than HKDF-SHA256 or SHAKE128.  (Of course, you could use a much faster Keccak sponge like the 12-round KangarooTwelve or even the 6-round Kravatte but they're not among the SHA-3 functions.)
Avenue for Dual_EC_DRBG.  It seems implausible that NIST would choose to standardize DRBG interface and security requirements only to introduce a back door—it's so foundational for so much cryptography that standardization would be well within NIST's purview even without the back door.  But the prospect of attacking this foundation could have motivated NSA to push slightly harder for NIST to standardize it.

That said, you're unlikely to get the real answer unless (a) you file a FOIA request to get the internal design discussions, or (b) someone from NIST hangs out here.


Shamir Secret Sharing Scheme - leak of information After going through some literature, I've convinced myself that to recover the exact secret using Shamirs Secret Sharing scheme, we must have S(the secret converted into a number) < p (choice of prime) and n (total number of parties) < p.

I understand that the reason for incorporating modular arithmetic and the prime p is to ensure that there isn't any leak of information. However, since the prime p is a public number, isn't there anyways a leak of information that the secret S < p? (i.e. not all real numbers have the same probability of being S)

Thanks very much in advance.

Since all the operations are with respect to the field defined by $p$, for a threshold of $t$ shares required for reconstructing the secret, any set of $t-1$ shares reveals no information about the secret, even in a probabilistic sense. This is the claim given in the original presentation of Shamir's scheme, and is in fact true due to the properties of finite groups and polynomial interpolation within them.

For a brief but illustrative example, consider the polynomial $4x^2+3x+1\in\mathbb{Z}_5$ to keep things reasonably small for a manual example. If we have three parties involved in the scheme, given two of their shares we should not be able to gain any information with respect to the secret, 1. If it is known that the shares of $P_1$ and $P_2$ are both $3$, for example, what information has been gained about the secret? Since the polynomial is of degree 2, 3 points are minimally required for using interpolation to identify the unique polynomial fitting the points. In this example it is easy to see that if the share of $P_3$ is 0 the secret revealed will be 4, and every other domain value results in a different secret value being revealed all solely dependent on the share of player three when shares for players 1 and 2 are known and fixed. Explicitly and exhaustively, given a list of potential share values for $P_3$ $[0,1,2,3,4]$ across the whole domain of possibilities, the resulting secrets revealed using this combination are $[4,0,1,2,3]$ respectively, and with equal probability since the share of $P_3$ is uniformly random. This is, once again the whole domain of possibilities and all are equally likely.

Therefore the scheme is information theoretically secure, because the property demonstrated in this brief and small example holds with respect to every combination of every proper subset of shares less than the threshold and every field of prime order, assuming of course that the scheme was set up correctly with appropriate parameters.


ECC public key encryption and authentication - ECIES with ECDSA vs ECDH with AES I'm currently working on a project where I want to establish a secure and authenticated communication channel between to entities, using Elliptic Curve Cryptography. Now I'm not really sure how to proceed after the key exchange. The current exchange looks like this:

$Alice$ sends her public key $K_A$ to $Bob$
$Bob$ sends back his public key and a signature, containing both public keys and her identity: $K_B, Sig_b(K_B, K_A, A)$
$Alice$ replies similarly with her signature: $Sig_a(K_A, K_B, B)$

As I see it, this authenticates Bob to Alice in a way that he now encrypts a message with Alice's public key and can sure that Alice is the correct recipient. So here are my assumptions at this point:

This does not guarantee to Alice that Bob is indeed the sender.
Therefore Bob would need to either sign every message to Alice, or use a shared secret.

Am I correct about that?

If so, then would there be any benefit in signing every message over generating a shared secret from the keys? I assume that a combination of ECIES and ECDSA is far more expensive than simply running AES. Since I'm working with very resource constrained devices, I'd like to keep the overhead as small as possible. Although I probably should use random padding and a KDF to increase the security in the AES scenario.

ECDH or DH for that matter doesn't provide any authentication of a user. ECDSA as a public key scheme does provide authentication, but lacks validation. You need to certify that the exchanged public keys are indeed from Alice or Bob. So Alice and Bob must let an authority certify their own public keys such that Alice trusts the authority of Bob and Bob trusts the authority of Alice. The authorities might in fact be the same authority. You can call it certificate authority.

A possible attack might be a man-in-the-middle attack where

Alice sends $K_A$ to Bob, but Martin intercepts $K_A$ and sends a newly generated key $K_{MA}$ to Bob
Bob sends back his public key and a signature, containing both public keys and her identity: $K_B,Sig_B(K_B,K_A,A)$, but Martin intercepts it and sends a newly generated key $K_{MB}$ and re-signs with its private key $Sig_{MB}(K_{MB},K_A,A)$
Alice replies similarly with her signature: $Sig_A(K_A,K_B,B)$, but Martin intercepts it and re-signs $Sig_{MA}(K_{MA},K_B,B)$ with the private key $MA$ from #1.

This is applicable to ECDH and ECDSA.


In a lattice, how can one define a good basis and a bad basis? When it comes to lattice based cryptographic systems, all the literature talks about, good bases and bad bases.

How does one define what a good basis is and what a bad basis is?

A good basis are the set of "almost" orthogonal set of vectors which have small norms. They allow us to solve certain variants of closest vector problem $\mathsf{CVP}$ very efficiently (for example, use LLL). Usually, the private keys are "good" basis.

A bad basis are those basis which are in certain sense hardest instance to solve: if you solve any problem in the worst basis setting, you can solve the problem in almost all basis defining the same lattice. For very obvious reasons, bad basis are used as the public key.

If you want more concrete understanding, I refer you to read Miccianio's work Improving lattice based cryptosystems using the hermite normal form which first proposed HNF variant of basis to be used as the public key.


Are short ElGamal keysizes acceptable (1024-bit or lower) in cases where security is only necessary in a short timeframe I am working on an efficient mental poker framework. I have implemented a functional and secure commutative encryption scheme based on ElGamal as described in:

http://groups.csail.mit.edu/cis/theses/weis-phd-thesis.pdf

However, shuffling and dealing an entire deck is causing slowdown as the number of players involved in the game increases (more players means more commutative encryptions and decryptions). Even in initial, idealized tests things are pretty slow.

The system parameters currently used are an advisable 2048-bit safe prime (from RFC 5114) but I'm wondering if these key sizes are overkill in the case of something like mental poker where decryptions of relevant cards will happen within a few minutes and after the hand the security of the previous deck is irrelevant? This got me wondering in general if key sizes are flexible depending on "how long the encryption needs to last" - are there any guidelines here? Any pitfalls I'm not considering?

This got me wondering in general if key sizes are flexible depending on "how long the encryption needs to last" - are there any guidelines here? Any pitfalls I'm not considering?

Yes, you can down-scale the bit-length, e.g. to 1536-bit and it will still likely stay somewhat secure. But do note that for discrete-logarithm over finite fields based cryptosystems there's a steep cutoff in security. Once the parameters are so small that you can break the scheme, e.g. within a week or longer on your hardware, you get "precomputed" data that allows to find any discrete logarithm of interest in a matter of seconds / minutes.

This observation was widely made first with LogJam.


Is deriving the IV from the password secure? I came across an encryption scheme to encrypt files with AES-256. You can see the initialization of the decryption routine below:

salt = scrambled_file.read(16)

key_and_iv = OpenSSL::PKCS5.pbkdf2_hmac(password, salt, 50000, 48, OpenSSL::Digest::SHA512.new)
key = key_and_iv.byteslice(0,32)
iv = key_and_iv.byteslice(32,16)

cipher= OpenSSL::Cipher::AES256.new(:CBC)
cipher.decrypt
cipher.key = key
cipher.iv = iv

decrypted_data = cipher.update(scrambled_file.read(...))

It basically takes a password and a 16-bytes random salt and pushes it through PBKDF2 (SHA512). Afterwards, the key is taken from the first 32 bytes and the IV from the 16 bytes following it.

Is it secure to derive the IV from the same hash as the key?

Yes, it is. PBKDF2 derives a DK, a "derived key", which is indistinguishable from random. This is mainly because function within PBKDF2 is HMAC, and HMAC is a PRF. Let's see the definition from Wikipedia:

  In cryptography, a pseudorandom function family, abbreviated PRF, is a collection of efficiently-computable functions which emulate a random oracle in the following way: no efficient algorithm can distinguish (with significant advantage) between a function chosen randomly from the PRF family and a random oracle (a function whose outputs are fixed completely at random).

This also means that the bytes of the derived key are independent, even from each other. So that means that as long as separate bytes from the output are used, we can split the DK value into a key and an IV.

Now, fortunately, the scheme provided uses SHA-512 as the underlying hash function. This means that no additional calculations need to be performed if we require 256-bit key material and 128 bit IV material.

If the SHA-256 hash would have been used the PBKDF2 function would require an additional run. Unfortunately, in the scheme above, an attacker would not have to perform such an additional run. This is because the attacker only has to verify the key; it can calculate the IV when it finds the key. So using a smaller hash function requires a lot more operations for the legit user, while not giving any security advantage. This is a bad property for a PBKDF - which unfortunately is present for PBKDF2.

So as long as your key and IV stay below the output size of the hash the scheme above is secure.

If you'd ever required more output than the single hash requires then it is possible to perform additional calculations using a key based key derivation function (KBKDF) such as HKDF. In that case, a good scheme would be:

derivedKey = PBKDF2(password, salt)
key = HKDF(derivedKey, "Key")
iv = HKDF(derivedKey, "IV")

That the scheme is secure doesn't mean that it is optimal. You could think of using a memory hard PBKDF such as scrypt or one of the newer Argon2 variants instead of PBKDF2. You might also have a look at authenticated ciphers such as GCM to add integrity and authenticity to your ciphertext.

Of course, the scheme does depend on the salt being a secure random value. Please make sure this is the case, otherwise, you may end up with a repeating key, IV for identical passwords, destroying security.

A high number of iterations (the "work factor") for PBKDF2 makes it harder to attack relatively weak passwords (and most passwords are relatively weak).


Mathematical structure for Sbox Recently, when I studied the permutation cipher, I saw a matrices structure which is same as permutation cipher. This method was so simple and interesting for me.

Let $m$ be $n$-bit plain text and $P=[p_1,...,p_n]$ be the permutation secret key such that $P(m_i)=m_{p_i}$.

For example, let $m=5={(101)}_2$ and $P=[2,1,3]$. So $P(5)={(011)}_2=3$. In mathematical points of view, we can do this method with matrices multiplication as fallow:

$P(m)=\left(\begin{array}{ccc}m_1&m_2&m_3\end{array}\right)\cdot\left(\begin{array}{ccc}0&1&0\\1&0&0\\0&0&1\end{array}\right)=\left(\begin{array}{ccc}m_2&m_1&m_3\end{array}\right).$

In general case, instead of using $P$ as $1\times n$ vector, we can use $n\times n$ matrices with $0,1$ elements, such that there exist only one $1$ in each column( in the position $p_i$).

This equivalent presentation make analysis and attacks so easier. Is there exist similar mathematical method for substitution cipher?

Well, at least two representations come to my mind, but I'm afraid you will not find them too useful. In general, S-boxes are designed with the goal in mind that such "mathematical" representations do not help in exposing any more structure than just writing down the table does.

If we are talking about bit strings, i.e., an S-box $S\colon\{0,1\}^n\to\{0,1\}^n$, we can interpret $\{0,1\}^n$ as a finite field $\mathbb F_{2^n}$. Over any field, polynomial interpolation works, thus there exists a unique polynomial of degree at most $2^n$ over $\mathbb F_{2^n}$ that describes the substitution $S$.
Similarly to your permutation matrix example, any map $f\colon A\to B$ of finite sets can be written as a matrix: Let $A=\{a_1,\dots,a_n\}$ and $B=\{b_1,\dots,b_m\}$ (note this fixes an order on the sets), and define $F$ to be the binary $m\times n$ matrix which has $1$ in the entry labelled $i,j$ and only if $f(a_i)=b_j$. Then $F$ applied to the $i$th unit vector gives back the $j$th unit vector, where $b_j=f(a_i)$.

Note how both representations have size exponential in the bit length of the input.


How is the re-encryption done in Path ORAM? Path ORAM block headers store nonce that is used to re-encrypt the data on access. Every time a block is accessed, the nonce is updated.

If the header itself is encrypted, how's the decryption done when the block is fetched next time?

If the header itself is NOT encrypted, isn't it trivial for an attacker to recover the nonce from the header and decrypt it, thereby beating the purpose of ORAM?

Client holds a secret key, which is used to encrypt/decrypt all blocks.  Nonce is not used as a key but randomness to make sure that all the blocks, no matter updated or not, will look fresh.


Is CBC mode with a fixed IV secure, if a counter is prepended to the plaintext? In this answer to an earlier, related question I noted that encrypting a nonce, such as a sequential counter, using the same block cipher and key as used for the message encryption itself is one of the recommended ways described in NIST SP 800-38A, Appendix C, of generating an unpredictable IV for CBC mode encryption.

I further noted that this is, in fact, mathematically equivalent to using an all-zero IV and simply prepending the nonce (padded to a full cipher block) to the plaintext before applying CBC mode encryption.

However, in the comments to another answer, it was noted that this construction is trivially CPA-insecure (as noted e.g. in section 4 of this paper by Rogaway) if the nonce may be chosen by the attacker.  (Of course, it could be argued that, if your nonces may be controlled by an attacker, you really should be using a fully nonce-misuse resistant mode like SIV instead of CBC anyway.)

That said, let's take this opportunity to hopefully settle this issue once and for all:

Assuming that the nonce values are unique and generated according to some fixed public counter sequence that is not under the attacker's control, is the encryption scheme described above (i.e. pad the nonce to a full cipher block, prepend it to the plaintext, and encrypt the result using CBC mode with an all-zero IV) actually IND-CPA secure?
If so, is there a published proof of this?  If not, is there a known attack under the IND-CPA model that doesn't assume the attacker can choose the nonces?
How does the quantitative security (e.g. attacker's advantage as a function of the number of encryption oracle queries) compare to standard CBC mode with random IVs?  AFAICT, both are basically only secure up to the birthday bound, but a more detailed analysis could be useful.
As a bonus, what if the nonce is padded to some fixed length that is less than a full cipher block?  Is the resulting scheme still IND-CPA secure (assuming that the nonce doesn't overflow, of course) and if so, how does this affect the number of messages that can be safely encrypted?

Assuming that the nonce values are unique and generated according to some fixed public counter sequence that is not under the attacker's control, is the encryption scheme described above (i.e. pad the nonce to a full cipher block, prepend it to the plaintext, and encrypt the result using CBC mode with an all-zero IV) actually IND-CPA secure?

Yes, nonce-based CBC has reasonable IND-CPA security bounds just like traditional CBC.

  If so, is there a published proof of this?  If not, is there a known attack under the IND-CPA model that doesn't assume the attacker can choose the nonces?

Yes: there is a published proof just below.  (I leave it to the asker to specify restrictions on venue that would exclude pseudonymous feathery bloviators on the internet.)

  How does the quantitative security (e.g. attacker's advantage as a function of the number of encryption oracle queries) compare to standard CBC mode with random IVs?  AFAICT, both are basically only secure up to the birthday bound, but a more detailed analysis could be useful.

Quantitatively, the security drops with the number of queries times the number of blocks, because there is a potential for a ciphertext-chaining block to coincide with a nonce.  But the security of CBC itself already drops with the square of the total number of blocks, which is larger than that already (unless every message is a single block long).

  As a bonus, what if the nonce is padded to some fixed length that is less than a full cipher block?  Is the resulting scheme still IND-CPA secure (assuming that the nonce doesn't overflow, of course) and if so, how does this affect the number of messages that can be safely encrypted?

How you format the nonce is inconsequential as long as nonces are distinct.  The crux is that in case (2) below, $m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i})$ is uniform random, so it has equal probability of coinciding with any fixed nonce.  Although stated in terms of the nonce $n_0$, the proof really assumes only that the first block fed to the cipher is unique.

Details.
An attack $A$ on a cipher is random algorithm that submits a sequence $m_0, m_1, \dots, m_{q-1}$ of $q$ queries (possibly adaptively), for messages up to $\ell$ blocks long, to an encryption oracle; for the last two queries the oracle returns the encryption of only one of them, determined by a fair coin toss, and the attack wins if it guesses correctly which face the coin landed on.  The IND-CPA advantage of an attack $A$ is defined to be $$\operatorname{Adv}^{\operatorname{IND-CPA}}_{\mathcal O}(A) := |\Pr[A(\mathcal O)] - 1/2|,$$ where $\Pr[A(\mathcal O)]$ is the success probability of $A$ on the oracle $\mathcal O$.  (The oracle is assumed to know how to count.)

Fix a block size $b$.  Each message $m_n = m_{n,0} \mathbin\| m_{n,1} \mathbin\| \cdots$ will be an integral number of $b$-bit blocks.  For a function $F$ and a block $\mathit{iv}$, define $$\operatorname{CBC}_F(\mathit{iv}, m_n) := F(\mathit{iv} \oplus m_{n,0}) \mathbin\| F(F(\mathit{iv} \oplus m_{n,0}) \oplus m_{n,1}) \mathbin\| \cdots.$$

In traditional CBC mode for a random function $F\colon \{0,1\}^b \to \{0,1\}^b$ of blocks, to answer a query for the $n^{\mathit{th}}$ message $m_n$, the encryption oracle samples $\mathit{iv}_n$ uniformly at random and reveals $$\operatorname{TCBC}_F(m_n) := \mathit{iv}_n \mathbin\| \operatorname{CBC}_F(\mathit{iv}_n, m_n).$$  The success probability $\Pr[A(\operatorname{TCBC}_F)]$ of any attack $A$ against traditional CBC is bounded by the standard CBC theorem: for uniform random $f$, $$\Pr[A(\operatorname{TCBC}_f)] \leq 1/2 + O(q^2 \ell^2/2^b).$$  To allow decryption one usually instantiates traditional CBC with $F = E_k$ for a block cipher $E$ and a uniform random key $k$; the standard permutation-for-function substitution lemma just adds $O(q^2/2^b)$ to the probability.
Define the following alternative scheme, where $G\colon \{0,1\}^b \to \{0,1\}^b$ is another random function of blocks: To answer a query for the $n^{\mathit{th}}$ message $m_n$, the oracle reveals $$\operatorname{NCBC}_{F,G}(m_n) := G(n) \mathbin\| \operatorname{CBC}_F(G(n), m_n).$$  If $F = G$, call it $\operatorname{NCBC}_F$.  Consider the following cases:

$G = g$ is a uniform random function $g$ independent of $F$.  Obviously, this is identical to traditional CBC mode for any $F$, because each output $g(n)$ is independent uniform random for distinct $n$ just like $\mathit{iv}_n$, so $$\Pr[A(\operatorname{NCBC}_{F,g})] = \Pr[A(\operatorname{TCBC}_F)].$$
$F$ and $G$ are the same uniform random function $f$.  This case is distinguishable from the preceding one only in the event that $n_0$ coincides with $m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i})$ for some $n_0$, $n_1$, $i$ among the messages submitted to the oracle, which happens with probability bounded by $O(q^2 \ell/2^b)$ where $\ell$ is the mean query length.  Thus, if $R$ is the event of this coincidence,
\begin{align*}
   \Pr[A(\operatorname{NCBC}_f)]
     &= \Pr[A(\operatorname{NCBC}_f) \mathrel| R] \Pr[R] \\
     &\quad + \Pr[A(\operatorname{NCBC}_f) \mathrel| \lnot R] \Pr[\lnot R] \\
     &\leq \Pr[R] + \Pr[A(\operatorname{NCBC}_f) \mathrel| \lnot R] \\
     &= O(q^2 \ell/2^b) + \Pr[A(\operatorname{NCBC}_{f,g})].
 \end{align*}
(Exercise for reader: Write down a concrete formula for a bound on $\Pr[R]$.  To make it simpler, replace $m_{n_1,i+1} \oplus f(\cdots \oplus m_{n_1,i})$ by, say, $m_{n_1,i+1} \oplus f(n_1\mathbin\|i)$: ensuring distinct inputs to $f$ can only raise the probability that one of the chaining values coincides with one of the nonces, and every output of $f$ on distinct inputs is independent uniform random.)
$F = G = \pi$ for a uniform random permutation $\pi$.  By a standard theorem about substituting uniform random permutations for uniform random functions, for any algorithm $A$ making $q$ queries,
\begin{align*}
   \Pr[A(\operatorname{NCBC}_\pi)]
     &\leq \Pr[A(\operatorname{NCBC}_f)] + q(q - 1)/2^{b + 1} \\
     &= \Pr[A(\operatorname{NCBC}_f)] + O(q^2/2^b).
 \end{align*}
(Alternatively, one can use the somewhat better but less standard bound $\Pr[A(\operatorname{NCBC}_\pi)] \leq \delta \cdot \Pr[A(\operatorname{NCBC}_f)]$ where $\delta = (1 - (q - 1)/2^b)^{-q/2}$.)
$F = G = E_k$ for a uniform random key $k$ and a block cipher $E$.  The distance between $\Pr[A(\operatorname{NCBC}_{E_k})]$ and $\Pr[A(\operatorname{NCBC}_\pi)]$ is the PRP advantage $\operatorname{Adv}^{\operatorname{PRP}}_E(A')$ of $A'(\phi) := A(\operatorname{NCBC}_\phi)$ to distinguish the block cipher $E$ from a uniform random permutation; presumably $E$ was chosen by years of cryptanalysis to put a confident bound on this distance for all reasonable numbers $q \ell$ of block cipher evaluations.

Thus, the success probability of an attack on nonce-based CBC making $q$ queries of mean length $\ell$ is bounded by:

\begin{align*}
  \Pr[A(\operatorname{NCBC}_{E_k})]
&\leq \Pr[A(\operatorname{NCBC}_\pi)]
    + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&\leq \Pr[A(\operatorname{NCBC}_f)]
    + O(q^2/2^b)
    + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&\leq \Pr[A(\operatorname{NCBC}_{f,g})]
    + O(q^2 \ell/2^b)
    + O(q^2/2^b)
    + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&= \Pr[A(\operatorname{TCBC}_f)]
    + O(q^2 \ell/2^b)
    + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&\leq 1/2 + O(q^2 \ell^2/2^b)
    + O(q^2 \ell/2^b)
    + \operatorname{Adv}^{\operatorname{PRP}}_E(A') \\
&= 1/2 + O(q^2 \ell^2/2^b)
    + \operatorname{Adv}^{\operatorname{PRP}}_E(A'),
\end{align*}

or

\begin{equation}
  \operatorname{Adv}^{\operatorname{IND-CPA}}_{\operatorname{NCBC}_{E_k}}
  \leq O(q^2 \ell^2/2^b)
   + \operatorname{Adv}^{\operatorname{PRP}}_E(A'),
\end{equation}

i.e. essentially the same as for traditional CBC with a block cipher $E$.


Must a key for a HMAC-SHA256 digest kept secure? I need to check integrity of high secure system value - in this case encryption key(s)

I would like to create HMAC digest of this user encryption key (key is used in application as a key for AES-256 cipher) to check it's integrity. The encryption key is derived with a KDF from his password and salt, after every user's login into the application. After user registration, I create an integrity HMAC-SHA256 digest for user's encryption key. This digest IMHO shouldn't be kept secret and will be saved with other user data. While user is logging in, I create digest and compare it with saved value of the digest. If both of digests are same, integrity is approved.

-This makes me ask: Is it required to keep keys used for HMAC-SHA256 secured or can I leave it with other user data (non-secure, "in the open")? When a hypothetical opponent gets the key, is it possible for the opponent to restore the original value of an encryption key from a HMAC-SHA256 digest?

Edit

I'm not sure, because I'm thinking; when an opponent doesn't know the "secret value" (application encryption key), the opponent is not able to create the same digest, even if he knows the HMAC-SHA256 key. Is that a correct assumption?

My question: Is required to keep a key for HMAC-SHA256 secured or can I leave it with other user data as non-secure?

If your goal is integrity and you use a
HMAC, then it is mandatory to keep the key secret. A public key in HMAC would mean anyone can create valid tags for any message - and integrity is gone.

  When hypothetical opponent gets the key, is it possible from HMAC-SHA256 digest restore original encryption key?

No, it should be impossible to find the key from any HMAC value (that would contradict the security definition).


Is it possible to create an easy to use encryption/decryption method that will never be comprimised? In the comments of the question "Why programming languages don't provide simple encryption methods?" the following statement was made:

  A well thought out, tested and understood standard that has undergone
  extensive review by the crypto community has a much better [chance] of
  avoiding compromise than a system designed by a single engineer using
  a fairly low level library.

to me such a system would have the following requirements:

Encryption would require nothing more than a string of text to encrypt and an easily programmatic producible "key".
Decryption would require nothing more than an easily programmatic producible "key".
The result would not ever be able to be determined with out access to the key even given a reasonably huge finite (IE more than we can ever expect to have available) amount of computing power.
No method of attack would ever trivialize the determining the key or the source text used for the encryption.

My opinion is that the nature of encryption is that it is impossible for a standard like this to work given an infinite amount of computing power. We may be able to do this for the computing power of today but eventually given enough power it will be trivial to decrypt any scheme if we know how the scheme works and it only requires a single key. Is such a scheme possible?

If the key is:

generated with an unpredictable truly random uniform generator (not a pseudo-random generator);
as long as the data to encrypt;
used for only one message ever;

then this is the One-Time Pad model, and you can encrypt data by a simple bitwise XOR (no need for an explicit function, just XOR).

Otherwise, there is no solution which resists attackers with infinite computational abilities. Shannon's thesis is all about that.


Public key encryption I am not getting whole idea behind Public Key Encryption technique.

As according to fact, public key encryption method uses two keys a public key known to everyone private key known only to recipient of the message

For an instance let assume, John wants to send a secure message to Jane, He uses Jane's public key to encrypt the message. Jane then uses her private key to decrypt it.

The thing i am not getting is, as far as i know if we want to encrypt any message using a key, from that same key only we can decrypt that particular message.

But in public key encryption case both keys are different than how it is possible to decrypt the message.

Please clarify my issue and guide me through if i am going anywhere wrong in understanding the whole concept

Here is a great video which shows principles for public key cryptography using colors, which makes it easy to understand for everyone:
https://www.youtube.com/watch?v=YEBfamv-_do

Now what you missed is that it is possible to generate a secret key, and give away something which enables encryption but not decryption. This is the principle of public key encryption.


Mathematical proof of a combined hash function I´ve just started with crypto and I am trying to solve an exercise sheet. I am, however, not good at mathematical proofs and got a bit stuck on a certain - probably easy - question:

I´ve got three hash functions:

$H_1:=  \{0,1\}^* \to \{0,1\}^a$
$H_2:=  \{0,1\}^* \to \{0,1\}^b$
$H_3:=\{0,1\}^* \to \{0,1\}^b$

And I have to proof that: If at least one of $H_1, H_2, H_3$ are collision resistant $M:=  \{0,1\}^* \to \{0,1\}^{a+b}$ for  $M:= H_1(x)||H_2(x)||H_3(x)$ is collision resistant, too.

Intuitively I would say that $H_2$ and $H_3$ are not collision resistant, since they are shortened to the same length $b$.

I have started with assuming that $M$ is not collision resistant by changing the definition to:

$h(x_1) = h(x_2) = h(x_3) $  for a triplet $(x_1,x_2,x_3)$.

But I am not quite sure, if this is the correct way to do it.

Can I even proof it in one go? Or do I need several steps - like proofing $H_2 = H_3$ first?

Ignoring the issue of output length I mention in the comments, you should be able to prove this without intermediate steps. Here is an outline of how I would do it.

Without loss of generality let one particular hash function be the one that is collision resistant. It doesn't matter which one. Say $H_3$.
Assume that $M$ is not collision resistant. This means, you can find $m_0\neq m_1$ such that $M(m_0)=M(m_1)$.
Show how this would lead to a collision in $H_3$ directly. This leads to a contradiction, so $M$ must be collision resistant.

This is a proof by contradiction.


Shamir's secret sharing with passwords I'm trying to design an extension to Shamir's Secret Sharing that would allow the participant to specify a password instead of remembering/storing a large integer or binary data. So far, I have two ideas, both based on some PBKDF:

Run the password through a strong PBKDF to make $k_i$ then publish $(i, f(i)⊕ k_i)$ in a public, read-only location.
Similarly, run the password through a strong PBKDF and then publish $(i, \text{AES}(\text{key}=k_i, \text{message}=f(i))$ in a public, read-only location

I like the simplicity of the first method, and rationally I haven't found anything wrong with using nothing more than XOR, but to my intuition it smells a bit fishy.

Am I divulging any information that would weaken the algorithm by using just XOR? What about with AES?

Well, the first thing comes to mind is "what if your 'read-only location' isn't quite as read-only as you had hoped; if someone could modify your $f(i) \oplus k_i$ share, could they modify the reconstructed shared secret in a controlled way.

In your first example, I believe they could.  Let us assume that we are doing Shamir's Secret Sharing over the field $GF(2^k)$; let us further assume that the attacker has $N-1$ shares (where $N$ is the number of shares we need to reconstruct the secret).  Which his $N-1$ shares, he can reconstruct that, when you add in your share $f(i)$, the reconstructed secret will be $s = c \times f(i) + d$, for some values $c, d$ he can compute (and $\times$ and $+$ are over $GF(2^k)$.

Now, $c \neq 0$, and so this doesn't give him any information about what the secret is (given that he doesn't know your share).  However, if he wants to modify the secret, say, add $t$ to is, what he can do is modify your encoded share on the read-only location, replacing $(i, f(i) \oplus k_i)$ with $(i, f(i) \oplus k_i \oplus (t \times c^{-1}))$.

Then, when you reconstruct the secret, using his N-1 shares, and your modified share, you will decode your share as $F(i) + (t \times c^{-1})$ (remember, in $GF(2^k)$, addition and exclusive-or are the same operation); then, when you combine this decrypted share with his, you're come up with $c(F(i) + tc^{-1})+d = cF(i)+d + t = s+t$, resulting in the modified shared secret that the attacker selected.

On the other hand, by using AES to encrypt the share, the attacker cannot do any such tricks.  He can modify the share so that the shared secret becomes something else, however, he has no control over what that something else might be.


What is the most common encoding of messages to polynomials? How polynomial based encryption schemes such as NTRU encode messages in to polynomials? Is there a generic conversion?

In NTRUEncrypt, a raw message m of octet string of length l octets is encoded through the following steps:

Padded it with a random salt of b byte and a few extra information to form the actual octet string M that is to be encrypted.
This M byte string is then converted to a binary string Mbin using octect-string-to-binary-string-primitive (OS2BSP).
In NTRUEncrypt, the message is actually a ternary polynomial, so for every 3 bits in Mbin, use a binary to ternary mapping as follows to convert it into a ternary string Mtrin.

{0, 0, 0} -> {0, 0}
{0, 0, 1} -> {0, 1}
{0, 1, 0} -> {0, -1}
{0, 1, 1} -> {1, 0}
{1, 0, 0} -> {1, 1}
{1, 0, 1} -> {1, -1}
{1, 1, 0} -> {-1, 0}
{1, 1, 1} -> {-1, 1}

Finally the message polynomial m(x) is to take each element in Mtrin as the corresponding coefficient.

See section 8 for more details of conversion, and section 10.2.2 for encryption procedure.
https://github.com/NTRUOpenSourceProject/ntru-crypto/blob/master/doc/EESS1-v3.1.pdf


Extended Euclidean Algorithm (back substitution) I have found from the values of P (11) and Q(7) that n=77, (p-1)(q-1)=60 and that e=43 as it is relatively prime with 60.

However, I believe the value I got for d (7) is wrong. Here is my workings out:

60x + 43y = 1

60=1(43)+17
43=2(17)+9
17=1(9)+8
9=1(8)+1

Then:

1=9 - 1(8)
1=9 - 1(17 - 1[9])
1=1(9) - 1(17) + 1(1[9])
1=1(9) + 1(1[9]) - 1(17)
1=2(9) - 1(17)

1=2(43 - 2[17]) - 1(17)
1=2(43) - 4(17) - 1(17)
1=2(43) - 5(17)

1=2(43) - 5(60 - 1[43])
1=2(43) - 5(60) + 5(1[43])
1=7(43) - 5(60)

therefore d=7, right? It seems to not work in practice and I can't figure out why :(

The issue is when I apply these values into these formulas:

$$C = M^e \bmod n$$
$$M = C^d \bmod n$$

For example, when I make M=2 (for B) the result is C = 53.0009765625...
But using the formula to decrypt it doesn't return back to the original value

I would really appreciate any advice and apologies if I have worded it badly.

$d=7$ is correct; this can easily be verified by computing:

$$43 \times 7 \bmod 60 = 301 \bmod 60 = 1$$

So, the source of the problem lies somewhere in your "practice"; as you didn't share the details of what that was, I can't point out exactly where the problem is.


Improving security of (authentication) protocol I have a basic protocol which tries to authenticate messages going from client to server. Basically it is like this:

Imagine I want to send message M to server.
Client computes a MAC over the message. The MAC is basically DES_ECB encryption of data MAC_DATA length of which is 8 bytes. MAC_DATA is obtained
by XORING the plain message M between each other. Like this

  for (int i = 0; i < dwSize; i += DppGlobals.MAC_SIZE)
  {
        for (int j = 0; j < DppGlobals.MAC_SIZE; j++)
           MAC_DATA[j] ^= plaindata[i + j];
  }

And MAC is

  CALC_MAC = DppDES.EncryptDES_ECB(MAC_DATA, WorkKey);

Finally what client sends to server is:

Client -> Server: CALC_MAC, M

Assume keys are stored securely on client and server, and also they are shared.
Now since DES is insecure I am trying to improve this protocol. My idea is
basically the client will send to server AES encryption of the data it was sending before. So client sends to server

   Client -> Server:  C

Where C = AES_ENCRYPT_CBC(CAL_MAC | M, Key, someIV);

The server will decrypt the data it receives, and perform computations like it was doing before.

So is my modified version (with AES encryption) more secure than the old(current) protocol?

Since this protocol is already implemented, the change I want to add for improving its security should desirably be minimal - to avoid introducing new bugs. Also completely rewriting and using TLS is not an option.

The original is completely broken and would be regardless of the insecurity of DES.

The ECB encryption of a single block message (with a secure cipher) would be a secure MAC, but XORing the message blocks means that an attacker can modify any block of the message simply by making the same change to another block so that they cancel out.

The modified protocol is better, but not necessarily secure. For example, if the attacker can see two messages whose last blocks are "compatible" so that switching one for the other does not affect the aggregate XOR, the attacker can make that change knowing the MAC will match. I think this scheme effectively reduces to hash-then-encrypt (with an insecure hash, even), which is not secure. Even better attacks may exist.

You would be better off with an actual MAC algorithm. For example CMAC, if it must use a block cipher.

A minimal change would be to rip out all the current MAC code and replace it with just sending M, AES-CBC-MAC(len(M) || M), where len(M) is the length of the message as a 64-bit integer and || is concatenation. This would be secure authentication, but would of course not hide the message.


Factors of the group order to secure against Pohlig-Hellman I am looking into the security of Diffie-Hellman and the discrete log in general.

To make sure an attacker can not use Pohlig-Hellman to solve the discrete log quickly we need to make sure that the order of the group, $n$, has a large prime factor.

For Diffie-Hellman in $F_p$  this would mean that we should factorize $p-1$. Since we should take $p$ to be at least $1024$ bits, how are we supposed to factor $p-1$? is this not just as hard as the RSA problem?

[Isn't this] just as hard as the RSA problem?

Oddly enough, no.  If we were given a random $p$, and were asked to see if there's a large prime factor $q$ of $p-1$, yes, that would be, on average, a hard problem.  However, that's not what we actually do.

Instead, we get to pick $p$, and so that gives us a lot of flexibility.

One way is to pick $q$ first (for example, a 256 bit prime), and then search for 1024 bit values $kq + 1$ that happen to be prime; if we call the value we find $p$, then we know that $p-1$ has a large prime factor $q$.

Alternatively, we can search for values $p$ where both $p$ and $(p-1)/2$ are both prime; this takes longer, but is still quite feasible.  And, in this case, we know that $p-1$ has a large prime factor, namely $(p-1)/2$.

You can find both these strategies being applied in practice.


Is chosen ciphertext attack used to obtain a key? I don't understand what the goals are of a Chosen Ciphertext Attack.
What I've read from Wikipedia is that it is an attack one can use to obtain the key that the crypto algorithm uses.

However, I think that every file is usually encrypted using a different key.
If so, why is the chosen ciphertext attack used ?
Maybe I don't quite understand the concept of a key...

I'm no mathematician or cryptoanalyst but a simple curious boy :)

Chosen Ciphertext Attack is typically not used to obtain a key, but rather to obtain plaintext, or partial information about plaintext. Getting at the key is sufficient, but not necessary, to claim success of a CCA attack.

Indistinguishability under Chosen Ciphertext Attack is a theoretical model of attack. The attacker is assumed to be able to obtain decryption of ciphertext s/he chooses, under the key being attacked; and succeeds if s/he manages to gets any kind of information about plaintext corresponding to ciphertext s/he did not previously submit for decryption. Formally, the attacker succeeds if s/he recognizes better than random which of two ciphertexts s/he submited for decryption was selected by a referee, who produce the result of its decryption. Of course, getting at the key allows that.

In the most stringent variant CCA2, the attack is iterative.

That model may seem of theoretical interest only: if the adversary can obtain decryption of ciphertext s/he chooses under the key considered, it may seem that all security is lost. So why care against that?

Because we can, at little cost. A simple way to achieve CCA2 security is to use authenticated encryption. Essentially, decryption is forced to fail (and the deciphered plaintext is not released) if the ciphertext was crafted or altered by a party not holding the key.
Because CCA2 security does guard against plausible attacks. I'll take the example of efail. The context is hybrid cryptography, where a message is sent symmetrically encrypted using a random message-unique key, itself sent along the message encrypted with the public key of the receiver(s). The receiver of the message (and the email program + extension used for deciphering OpenPGP or S/MIME) is tricked into leaking some of the decryption of altered ciphertext (e.g. by way of accessing an internet server at an URL in the deciphered plaintext). The alterations are focused on the symmetrically-encrypted payload, thus the decryption is carried with the original key.


Is inversion always cheap with Twisted Edwards curves? I'm reading on Jubjub, which is planned for the next upgrade of Zcash. It is based on a Twisted Edwards curve with parameters $a = -1$ and $d = −(10240/10241)$. The reading says Jubjub does not need projective coordinates because inversion is cheap.

My question is, is the "cheap inversion" property that of Twisted Edwards curves in general, or the parameter selection of Jubjub in particular?

In the particular case of jubjub, it will be used in a Rank-1 Constraint System(R1CS) where inversion is cheap, costing one multiplication.

Jubjub is an embedded curve and the main purpose of developing it, is due that you can use it in a constraint system. Outside of its applications in R1CS, inversion is not cheap.

Since inversion is cheap, we can use the affine formula directly.


Choosing between hash functions instead of providing a salt for a password hash I am working on some programs that require the users to store their passwords in my databases.

However, due to the fact that I am not sure whether salt should be stored in databases due to my approach:

(1. I am able to create a random string with the help of ASCII table)

(2. I am able to create a unique ID like a random string similar to the User's UUID under Google Firebase)

Here's my approach, the users are required to enter a "Security_String".

The allowed format only employs numbers from 1 to 5.

1 represents SHA-1

2 represents SHA-224

3 represents SHA-256

4 represents SHA-384

5 represents SHA-512

After I collect both Security_String and Password from the users, then Password undergoes a series of hashing loops based on the Security_String.

In this case, will the generated hashed password be considered safe enough? Or is it better to generate a hash password with salt by using my approach?

Also, is it better if I add another spicy ingredient called pepper during the hashing process?

Generally you don't want to switch algorithms in cryptography. You'd have to deal with different workloads. Furthermore, the choice of algorithm would be just another salt, if a tiny one. However, your approach doesn't disallow the building of 5 separate rainbow tables. So the reason for a salt isn't met.

It is unclear why you would not be able to use a general Password Based Key Derivation Function (PBKDF) / password hash. So yes, using a well known good scheme with a a salt is indeed more secure.

A pepper can certainly be helpful; if the DB is stolen minus the pepper then it will be next to impossible for an adversary to start guessing passwords without the pepper. Of course the pepper should then not be kept in the DB, because that would negate the whole idea.


The security of adding random noise many time pad In may application, I have a series of real number $\{v_1, v_2, \ldots, v_N\}, v_i\in\mathbb{R}$. To protect them, I add a random noise $r\in\mathbb{R}$ to each themselves like one-time-pad encryption scheme. But due to some more requirements of optimization we only want to generate and use a random noise $r$ instead of generating one time pad. Is this model is secure and which level of security can I obtain?

Too tricky for a comment...

Conceptually, your scheme is 110% information theoretic secure, as it's a one time pad($ \downarrow $). But since we tend to use octet based computer architecture these days, $  \mathbb{Z}  $ is more appropriate.

Note 1. Ensure $ |r| \ge |v| $.

Note 2. Don't want to patronise, but the one time pad is thee most contentious and misunderstood aspect of cryptography ever invented. Especially on this forum. Is $r$ truly random or just pseudo-random? It's worrisome that I read 'generate' in a kinda algebraic context...


Performing a cryptographically secure HMAC using multiple input parameters I'm using an HMAC as a way to generate a deterministic challenge token for an authentication system.

I've effectively got three string inputs plus a key:

Client IP address (string, eg: "127.0.0.1")
Client nonce (string, eg: "2325363F")
Linux epoch (string, eg: "594077C6")

My key is 256 bit (32 bytes) array.

How should I be performing the HMAC, is it really just a simple case of using string concatenation?

  HMAC(key,input1|input2|input3)

I'm fairly confident the above is just as secure as a hash tree or doing multiple HMAC operations, but would like to confirm my suspicions.

Yes, you can simply concatenate unless the encoding is not canonical, e.g. when the order isn't set or when the dynamic size of the fields make it possible that there is room for overlap between the fields.

It does seem that you've chosen string representations while it would be easier to use encoding to bytes directly. E.g. an IP 4 address usually consists of just 4 bytes. The seconds since the Linux epoch could be a number encoded into 32 bits. That way the chance of overlap is also zero because the field boundaries would be well defined.

Another issue is that you need to make the character encoding explicit., e.g. aways use US-ASCII or UTF-8.


How to prove correct decryption in Paillier cryptosystem Bob sends a ciphertext obtained by Paillier encryption to Alice.

Alice has the private key. She decrypts the ciphertext and returns the plaintext to Bob.

How can Alice convince Bob that the plaintext is correct to this ciphertext? Bob only has the encrypted plaintext and the public key of this encryption.

This can be done by using a zero-knowledge proof to prove that a Paillier ciphertext is an encryption of zero. Specifically, let $c$ be the original ciphertext, and let $m$ be the decryption that Alice sends back to Bob. Then, both Alice and Bob can each locally use the homomorphic property to compute a ciphertext $c'$ that is an encryption of the value encrypted in $c$ minus $m$. Note that if $c$ is an encryption of $m$, then $c'$ is an encryption of zero.

Thus, all that is needed is for Alice to prove in zero-knowledge that $c'$ is an encryption of zero (equivalently, that $c'$ is a $n^2$'d power). This can be done very efficiently, using the method described in Section 5.2 of A Generalization of Paillier’s Public-Key System with Applications to Electronic Voting by Damgard and Jurik.

In light of a comment in a different answer, it is possible for the prover to compute the randomness given the public key, if it doesn't have it. Specifically, let $c=r^N \bmod N^2$ (this is an encryption of zero). Then, compute $M= N^{-1} \bmod \phi(N)$ and $r = c^M \bmod N$. This works since $c^M = r^{N\cdot M} = r^{1+k\cdot \phi(N)}  = r \bmod N$.


Probability for success of exhaustive search on PRF keys I saw this example for exhaustive search to break the security of a PRF $F_k:\{0,1\}^n\times\{0,1\}^n\rightarrow\{0,1\}$ where the key space is of size $|\mathcal{K}|=2^n$.

The claim is that there is an adversary $\mathcal{A}$ of size $2^n\cdot\text{poly}(n)$ that computes the values of $S_k = F_k([1]_2),F_k([2]_2),\dots,F_k([2n]_2)$ for all the keys.
Queries the oracle $\mathcal{O(\cdot)}$ (which might be either $\mathcal{R(\cdot)}$ or $F_k(\cdot)$) for the same queries, i.e. $S_{\mathcal{O}}=\mathcal{O}([1]_2),\mathcal{O}([2]_2),\dots,\mathcal{O}([2n]_2)$, and returns $1$ if there exists a key $k$ for which $S_{\mathcal{O}}=S_k$, otherwise returns 0.
It also mentioned that the probability to distinguish:

$\left|\Pr_{k\leftarrow\mathcal{K}}\left[\mathcal{A}^{F_k(\cdot)}=1\right]-\Pr_{k\leftarrow\mathcal{K}}\left[\mathcal{A}^{R(\cdot)}=1\right]\right|\geq1-2^{-n}$

(Where $[x]_2$ represents the binary representation in $n$ bits of $x$.)

I understand we must calculate the PRF for several messages in order to have significant number of bits and ensure $S_{\mathcal{O}}=S_k$ does not equal by chance. But I couldn't figure out why specificly choose $2n$?
(I thought maybe we want to have somthing which depends on $n$ bits to have inverse-exponantial probaility for identical strings, but why the factor of 2 is added?)

Also, I don't understand why the probability isn't $\geq1-2^{-2n}$ since the chance for collision in random should be $2^{-2n}$?

Finally, is bruteforce attacks and exhaustive search are basically the same method with different name?

Let $q$ be the number of queries made by the attacker.
Consider that the view of $\mathcal{A}$ in the experiment is equivalent to their view in a modified experiment, where the oracle is restricted to the domain $\{1,\dots,q\}$.

Now consider, that in this modified experiment, there are exactly $2^q$ functions of the form $R : \{1,\dots,q\} \to \{0,1\}$.
If we sample one of those functions uniformly at random, what is the chance that one of the keys of the PRF will "hit" this function? Well, we can't say exactly, but we can give an upper bound. There are $2^n$ keys, which means at most, if each each of those keys hits a different function, $2^n$ functions can be hit.
This mean the probability of one of the keys hitting our uniformly sampled function is upper bounded by $$\frac{\# \text{ of keys}}{\# \text{ of functions}} = \frac{2^n}{2^q} = 2^{n-q}.$$

This means, we have
$$\Pr[\mathcal{A}^{R(\cdot)}=1] \leq 2^{n-q}$$

and also (by definition)
$$\Pr[\mathcal{A}^{F_k(\cdot)}=1] = 1.$$

Therefore
$$\left|\Pr\left[\mathcal{A}^{F_k(\cdot)}=1\right]-\Pr\left[\mathcal{A}^{R(\cdot)}=1\right]\right|\geq 1-2^{n-q}.$$

Now we need to choose a value for $q$ that makes this attack successful. If you plug in you suggested value of $q=n$, you'll notice, that we get $$1-2^{n-n}=1-2^0=1-1=0,$$
which is unfortunate.
We notice that as soon as we choose something a bit larger, say $q=n+1$ , we have a successful attack by standard definitions of PRFs:
$$1-2^{n-(n+1)}=1-2^{-1}=1-\frac{1}{2}=\frac{1}{2}$$
which is non-negligible.

However, we like to go for attacks that are successful with overwhelming probability and we like to go for simple easily recognizable negligible functions.
So we choose $q=2n$ and get
$$1-2^{n-2n}=1-2^{-n}$$
which is easy to read and readily recognizable as an overwhelming probability.


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

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

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

Clarification

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

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

Answer

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

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

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

A key-less permutation does not provide encryption

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

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


Known Plaintext attacks using standard greetings etc In all modern ciphers, even if one bit of input changes, then half of the output will change because of diffusion. Considering this, how exactly will knowing standard salutations, etc. ("Hello Alice" or other known parts of the message) be used to launch an attack. You don't know the whole PlainText but only part of the PlainText. So how exactly will it help?

Known Plaintext Attack (KPA) is the security level that is below of Chosen Plaintext Attack (CPA) that we want at least CPA from all ciphers. Actually, we want more in the modern cryptography; Ind-CPA.
The classical cryptography era contains lots of examples that can be easily broken with KPA attack; shift, permutation, Vegenere, and Hill ciphers are some examples.
In the modern era, the KPA can be used for key searching as below.

Brute-force attack; search for all keys

  # c = E(k,m) for some key k we are looking for
  for i in keys:
    if c == E(i,m):
       return i

An interesting example in the history was the RSA's DES challenges, which contains given partial information The unknown message is: on the full plaintext and the contestants are required to find the key given the full ciphertext. They used brute-force attacks similar to the above. The attack is successful since the key size of DES 56-bit.
This above can be still considered a classical way to find the key and the technological advances help to find the key. A modern novel attack is coming from Matsui and Yamagish in 1992 on their novel paper

A new method for known plaintext attack of FEAL cipher

This is now called the Lineart Attack. On attacking the DES, it requires $2^{43}$ known plaintexts by Matsui in 1994.

Linear Cryptanalysis Method for DES Cipher

If you want to learn about the Linear attack the tutorial by Heys is a good starting point.
Now back your specific question;

("Hello Alice" or other known parts of the message) be used to launch an attack. You don't know the whole PlainText but only part of the PlainText. So how exactly will it help?

First of all, with the Kerckhoff's principle, we assume that except the key we assume all known about the target system, like how the messages turned into bytes for encryption.

If the position is known as in the RSA DES challenges, then this knowledge can be easily turned into a known-plaintext if fits into one block. One needs at least 16 characters for AES and 8 for DES.
The Hello Alice is forming more than one block for DES Hello Al and ice?????. If you brute-force the DES then the first block can be used to find the key candidates, yes there be more than one candidate. Then the decryption of the next blocks can be used to pinpoint the messages.
# c = E(k,m) for some key k
# we are looking for the possibele key for full known message block m
for i in keys:
   if c == E(i,m):
      m' = D(i,c')             # c' is the other message blocks
      if m' is a valid string  # check the validity of m'
        return i

A special case if we don't have a full block, then execute the brute force by decryption, and for each possible candidate, which contains the partial information, look for the meaningful strings by decrypting the rest ciphertexts. This can be automized with tools like Linux's string command and possibly check the PKCS#5 padding at the end will eliminate most of the candidates.

If the position is not known
This is a little problem to be solved compared to brute force and really depends on the message size. If the message size is $t$ and the known message part is $l$ then one needs to look for $t-l$ positions. Therefore the cost of brute force was multiplied with $t-l$. For short messages, this is not a real problem, however when the message size is more than $2^{32}$ then the brute-force cost become $2^{80}$ for DES and $2^{160}$ for AES.


What is the main difference between finite fields and rings? In the course I'm studying, if I've understood it right, the main difference between the two is supposed to be that finite fields have division (inverse multiplication) while rings don't. But as I remember, rings also had inverse multiplication, so I can't see any difference.

What is the main difference between finite fields and rings?

Since you specified finite fields and other answers didn't talk about it, I am adding the following:

Fields are rings which are commutative and in which all nonzero elements have multiplicative inverse.

But finite fields have another important property that distinguish them from rings: every finite field is completely specified by its order, because they always have exactly $p^n$ elements for some prime $p$ and natural $n$ and any two finite fields of same order are isomorphic.

Notice, saying that two fields are isomorphic means that they are the same, but represented in two different ways.

That is not the case for rings. For instance, this answer provides examples of rings that have $4$ elements but are not isomorphic:

$\mathbb{Z}_4,~ \mathbb{F}_2[x]/(x^2+x),~ \mathbb{F}_2[x]/(x^2+x+1),~ \text{and} ~ \mathbb{F}_2[x]/(x^2)$


Operation Table for Permutation Group I cannot seem to figure out how the operation table for this permutation is formed. Is it multiplying each index and doing modulus? I can't seem to figure out.

This is a Table 4.2 found in "Cryptography and Network Security" by Forouzan

It is the permutation group operation, which is the result of first applying the first permutation (listed on the left), and then the second permutation (listed on top).

For example, the permutation listed as [3, 1, 2] is the permutation that maps the element 1 to 3, the element 2 to 1, and the element 3 to 2.

And, the permutation listed as [1, 3, 2] is the permutation that maps the element 1 to 1, the element 2 to 3 and the element 3 to 2.

So, if we combine these two permutations, applying [3, 1, 2] first, we can compute this by tracking what the permutations do to the specific elements.  For example, it maps the element 1 to 3 (which is what the first permutation does), and then mapping the resulting 3 to 2 (which is what the second permutation does).  Similarly, 2 is mapped to 1 (again, the first permutation), and then the second permutation maps the resulting 1 to 1.  And, the element 3 is mapped to 2 by the first permutation, and that is then mapped to 3 by the second.

Hence, the resulting permutation is [2, 1, 3], which is what is listed in the [3, 1 2] row and the [1, 3, 2] column.


Would using perfect S-boxes in F function of an unbalanced Feistel network produce a simple and secure cipher? When I read some articles about cryptography on wikipedia, I took note of the following statements (please, correct me, if any of these are wrong):

Perfect S-box (based on bent functions) provides maximum possible
security against linear (and differential?) cryptanalysis.
The problem with using perfect S-boxes is that an S-box constructed
purely from bent functions can not be invertible.
F function in Feistel network does not have to be neither balanced
nor invertible. One could even make an extremely unbalanced Feistel
network, where one side is only one bit, and have a bent function used as F.

From these statements it seems that using perfect S-boxes in F-function of an unbalanced Feistel network is an obvious choice for a simple and secure cipher. I understand, that someone would have come up with this long ago, if it was indeed so simple, but I can not find any information regarding possible downsides of such design.

Almost perfect nonlinear permutations of $\{0,1\}^n$ are the best known designs for addressing both linear and differential cryptanalysis simultaneously. However $n$ needs to be odd. Such sboxes could be used in an SPN or feistel setup, but since one usually likes not just even length but power of two sbox bitlengths, for efficiency and implementation considerations, it is not common.

For your $(n-1)$ to one bit, very unbalanced feistel idea, the two issues I see are:

Extremely slow diffusion due to the single bit.
Bent functions are not balanced.

There are balanced quadratic functions which are almost perfect one can use, however, to address 2.

This is an active area of research.

See here, for example, for more discussion of sboxes which are permutations.


Zero knowledge proof relation + number is binary I want to develop a ZKPK for the following problem:
$$Y=g_0^{r_Y} \prod_{i=1}^n g_i^{s_i}$$
and $$Z=h_0^{r_Z} \prod_{i=1}^n h_i^{s_i}$$
I want to proof knowledge of $r_Y,r_Z$ and $s_i$ which I have been able to do with standard proof or relations. My problem is that I need a proof that the $s_i$ are binary. I also understand how to prof that for a general el gamal encrypted number using the fact that $x^2=x \implies x \in \{0,1\}$. However I don't understand that how to combine these proofs, i.e. proof that the $s_i \in \{0,1\}$ are the same $s_i$ as in $Y$ and $Z$.

Any help is appreciated.

To prove "the same" relation, just use the same response of $\Sigma$-protocol for each $s_i$ in relations for $Y$, $Z$ and $s_i \in \{0,1\}$. This technique was suggested by Chaum, Evertse, de Graaf in Eurocrypt'87 paper.

To prove OR relation, one would split the challenge, prove the valid part and simulate the false one. See Cramer, Damgaard, Schoenmakers Crypto'94 paper. For preprint link and extended "CDS" description see Alan Sz' answer at Zero-knowledge proof of a product.

It may be practical to get some chapters (in pdf) of "Rethinking PKI" book  from credentica.com for both proofs. Warning: it takes time to read and understand that.

Yet another technique would be extending $\Sigma$-protocol into polinomials of degree higher than linear in challenge, see a paper in MFCS 2012. It fits well polinomial graph representation, but might be an overkill for this task.


What is the largest performed/possible bruteforce attack to date? I've read that cracking 128-bit key is currently out of reach of all humanity. However, I can't seem to find any information on what scope of brute force attacks have been performed or are possible at the current time. Can someone provide some information on this subject with quotable reference?

The last major effort I know of for cracking keys was the Distributed.net effort.

You can find the project page at http://www.distributed.net/RC5/en. In 2002, they cracked a 64-bit RC5 key using at total of 331,252 computers over 1,757 days. Their maximum throughput was "equivalent to 32,504 800MHz Apple PowerBook G4 laptops or 45,998 2GHz AMD Athlon XP machines or (to use some rc5-56 numbers) nearly a half million Pentium Pro 200s." as it said in their press release.

At the time, they moved on to doing a 72-bit key, which would be 256 times harder.

If we do some Moore-Law-type hand waving, we'd see a $2^7$ (128×) increase in compute power in ten years. That means that if you started today, it would only be twice as hard as breaking 64-bits was a decade ago. Doable, but not many people would actually want to bother.

Even if you're a government, buying a zero-day exploit and tailoring your own malware would be cheaper.


Can I use HMAC-SHA1 in counter mode to make a stream cipher? Say I have an embedded device which is only capable of doing HMAC-SHA1 transformations (that device is, in fact, a YubiKey).

Would it be secure to feed it like a block cipher in counter mode to get a random pad suitable as an stream cipher?

Of course, I'm talking about not repeating the counter value ever to encrypt data (so this construction would also need some random IV or treating the counter value as a nonce forever).

Yes, this would be secure. CTR (Counter) mode based on keyed function $F_K$ is secure as long as its output
$$
W_i = F_K(i)
$$
is unpredictable given previous outputs
$$
F_K(1),F_K(2),\ldots,F_K(i-1).
$$
This requirement is essentially the definition of a pseudo-random function (PRF). Most HMAC instantiations with widely used hash functions are believed to be secure PRFs (rigorous proofs are impossible for several reasons).

You may have heard of CTR mode as a blockcipher mode. This is also correct, as a secure block cipher must be a secure pseudo-random permutation (PRP), which can not be distinguished from PRF if it is queried/used fewer than $2^{n/2}$ times, where $n$ is the block size.

Block ciphers are used in CTR mode primarily due to their speed (HMAC is slower, in particular on short messages), but keyed hash functions are equally strong.

Certainly, you must ensure that your counter never repeats. You may want to follow the NIST strategy (page 18) of constructing the counter from nonce.


Truncating ciphertexts on ring-LWE schemes On the section 5.4 of the paper Improved Security for a Ring-Based Fully Homomorphic Encryption Scheme, the authors explain how to discard some bits of the ciphertexts to get smaller ciphertexts and smaller evaluation keys.

The function Discard simply takes a ciphertext $c$ and an integer $i$ (number of words to be discarded) and returns

$\lfloor w^{-i}c \rfloor$

where $w$ is the number of bits of each word.

But, since $c$ is a polynomial with integer coefficients (coefficients in $\mathbb{Z}_q$), I don't understand how this function is discarding bits. To me, it seems like it is only zeroing all the coefficients whose absolute values are smaller than $w^i$.

I also checked the reference from where this technique of truncating ciphertext was extracted, named the paper Fully Homomorphic Encryption without Modulus Switching from Classical GapSVP, but its explanation does not make sense to me as well.

So, do you know how this technique works? Could you give more details or show me what point I am interpreting wrong?

The expression $c' = \lfloor w^{-i} c \rfloor$ is a slight abuse of notation. What it technically means is to interpret each coefficient of $c$ as real number, divide by $w^i$, round the result to the nearest integer, and then interpret it as an element of $\mathbb{Z}_q$ again.

This is equivalent to expressing each $\mathbb{Z}_q$ coefficient of the ciphertext as a bitstring, and then discarding the $i$ least significant $w$-words of each bitstring. It also explains why $w^i c'$ is equal to c with the $i$ least significant $w$-words of $c$ being set to $0$, as the authors say in the next sentence of Section 5.4.

By the way, $w$ does not represent the number of bits in each word. Instead, $w$ describes the size of each word, and so the number of bits in each word is actually $log_2(w)$.

If you're interested in other examples of where the technique of discarding the lower-order bits is used, see works on the Learning with Rounding problem. (The paragraph in the middle of page 2 gives an equivalent explanation of this notation.)


Why is it not possible to tap into the HTTPS traffic specifically going from the server to the client? How I think HTTPS works when sending data from server to client:

-Server has 1 public, 1 private key.

-Client has access to the server's public key and not it's private key.

-Client has no keys of its own.

-Server uses its public key to encrypt data and sends it to the client. Client then uses the same public key to decrypt the message.

Is this how it works when the server sends data to the client? How does a server encrypt the data it sends to its clients? Are there a set of public and private keys for both devices?

I understand how the data sent from the client to server would be secure. Client encrypts data with the public key which then can only be decrypted with the private key and nothing else. But from my understanding, the client has no private and public keys of its own, so how does HTTPS work again?

I'm assuming you're talking about RSA. The more common DH algorithm uses ephemeral public and private keys generated by both the server and the client, although that's not relevant to this answer. The public and private keys are not used to exchange traffic. Instead, they're used to exchange a symmetric key which is used to encrypt data going both directions. This is what's called a hybrid cryptosystem.

Now, TLS in particular is a little more complicated than that. It uses two symmetric keys, one for each direction, in order to protect from certain kinds of attacks. however, the public key encryption is used to exchange a single master key which is used to generate the two symmetric keys, as well as some other keys used in other parts of the TLS protocol (such as MAC keys used for integrity).

For more details, see How does SSL/TLS work?