Unable to implement Client and Server Side Hashing (Validation problem)

In my answer, I'll largely reproduce / use what is written in "Method to Protect Passwords in Databases for Web Applications" by Scott Contini, you definitely should read at least section 4 for the actual guidance and the whole paper for the background and the whys.

The paper has a more distinguished approach than you, but in principle does the same. The problem with the salt is solved by storing a per-user salt in the database and upon request hash(username||domain||per-user-salt) is computed by the server and served to the client as the salt.

Now for the procedure as outlined in section 4:

Store the username, $H(s)$ and $v$ in your database upon registration / password change. $v$ is said per-user salt (which should be 128-bit random and regenerated upon password change), $H(s)$ is the fast hash of the slow hash.
The salt is as described above. Additionally store a system-level secret $\sigma$ of the same properties as $v$, regenerate it occasionally.
The client (the app) gets the username from the user (or from its storage). It now sends a request with said username to the server.
The server looks the user up. If the user does not exist, $\sigma$ replaces $v$ in the salt computation. The salt and the (system-wide) parameters of the slow hash are sent.
The client now computes the slow hash using the password and the given parameters and sends the hash.
The server hashes the received result. The user is accepted if and only if the user exists in the database (you may make a new query here) and the hashes (from the DB and the computation) match.

Oh and you may want to use a more modern hash-function than MD5 here, because if it comes out that you use MD5 people (who have heard that "MD5 is broken") will come to you and complain about why you use a broken hash function. This might cost you users, because not everybody is going to care about the (correct) explanation that the "broken-ness" of MD5 doesn't matter in this particular case. So rather use a PR-friendly hash function like SHA-256.


The last two steps is from Lagrange interpolation such that $\sum_{i\in S_x'} q_x(i)\triangle_{i,S_x'}(0)=q_x(0)$. The concept is the same as that of leaf node, but now we are at the parent node. Doing this recursively up to the root node would give the secret exponent.


Well, there are lots of one-way functions in cryptography.  For most of them, it is not known how being able to factor is of any use  in inverting them.  For example, even if you have black box that can instantly factor any number, we still don't know how to practically find a preimage for SHA-512 (where, by preimage, I mean that, given the value of a hash, can you find a string that hashes to that value).

On the other hand, there are a few one-way functions for which being able to factor allows you to find preimages.  The most common one (and the one you're probably thinking of) is RSA.  In raw RSA, you're given the values $N$ and $e$ (and these two values are jointly known as the 'RSA public key'); the one way function is $RSA_{N,e}(M) = (M^e \bmod N)$.

Now, in RSA, $N$ is a large composite number; if you don't know the factorization of $N$, it's hard to invert; that is, given a random value $X$, it is usually hard to find an $M$ such that $RSA_{N,e}(M) = X$.  However, it turns out that if you do know the factorization of $N$, it's easy.


CAs are pre-loaded on the system, but how is it able to get intermediate certs?

An X.509 certificate may contain extensions, one of them called Authority Information Access, which contains "pointers" to the certificate for the (intermediate) CA that issued it. In your case, the AIA extension is present and contains the following URL:

http://cacerts.digicert.com/DigiCertSHA2SecureServerCA.crt

Windows simply sends an HTTP GET request to that URL, and tries to interpret what it obtains as an encoded certificate. Which is the case. Windows can then verify that the intermediate certificate is indeed a valid issuer for your certificate (the signature is valid, the subject/issuer names match, the validity dates are correct, and so on...). Once it has obtained the intermediate CA cert, it repeats the process, until it hits one of the preloaded root CA.

The certificate viewer of Windows can show you such URL (see the "details" pane). Alternatively, you can decode the certificate structure to see for yourself the gory details (personally, I use my own tool called DDer).

Amusingly, this feature can be used to make, in some circumstances, a remote machine issue HTTP GET requests at URL of your choosing (but only GET, not POST, and only HTTP, not HTTPS; and you don't get to see what is obtained). For instance, if there is a Windows-based SSL server that asks for client certificates, then a malicious client may submit a phony certificate that makes the server issue on HTTP GET at a URL that will be interpreted by the server itself (and thus may contain "internal" IP addresses, or even "localhost").


Would dividing a random number by a constant "ruin" it?

It does not lower the security at all - at most, it changes the output space. If your output space is, say, the integers between $-100$ and $100$, then computing PRG$(s)/2$ for a random seed $s$ gives a value indistinguishable from a random value in the set $\{-50, -49.5, \cdots, 49.5,50\}$. Depending on which output space you consider and what you exactly mean by "dividing by 2", it can even remain a cryptographically strong PRG with the same output space: if your output space is, say, the field $\mathbb{F}_p$ with $p$ prime, then computing PRG$(s)$ and multiplying the output by $2^{-1} \bmod p$ gives a value indistinguishable from random in $\mathbb{F}_p$.

This follows immediatly from the security of the original PRG: since division by 2 is a reversible operation, any distinguishing attack on the new PRG trivially translates into a distinguishing attack against the original PRG.


Discrete log accumulator without pairings?

Sure.  Use the strong RSA assumption.  The accumulator of $x_1,\dots,x_k$ is $A = g^{x_1 x_2 \cdots x_k} \bmod n$, where $n$ is a RSA modulus and $g$ is a fixed base.  To prove that the accumulator $A$ contains $x$, exhibit a value $h$ such that $h^x=A \pmod n$.  This is secure under the strong RSA assumption, and has a discrete log "feel" to it.


Which numbers correspond to the 2048bit length? Is it prime, exponent, coefficient...?

Only the modulus really - the key size is identical to the modulus size by definition. The primes are commonly half of the key size for calculations that use 2 primes (multi-prime RSA is faster and on the uptake). The private exponent may not reach the full key size; it's between 0 and the modulus (exclusive). There is a high chance that the size is the same or slightly less than the modulus in bytes.

  How is the public key related to the private key? Is it calculated from the numbers, or is it embedded in the private key?

It's calculated during the key pair generation process - the output of which is both a private key and a public key. The private key and public key share the same modulus. Often the private key - generated by a specific tool such as OpenSSL - contains the public exponent, so you can also extract / use the public key if you have the private key.

Usually the public exponent is a known, small value - such as the fourth prime of Fermat: 0x010001. But as that may not be the case the public exponent (and thus the public key) in general isn't calculated from the private key components. If the public exponent is the same size as the private exponent then you cannot calculate it from the private key values.

  From reading another answer it sounds like the 2048 length corresponds to the modulus.
  However when I calculate the length I get 2056 ...

ASN.1 / DER encoded INTEGER values are signed, big endian. As the most significant bit of the positive modulus is always set - assuming that the key size is dividable by 8 - it will always left-pad the modulus with a padding byte set to 00. Otherwise the encoding would represent a negative value in so-called two-complement encoding - the most significant bit is seen as the sign bit: 0 for positive number representation and 1 for negative number representation.

So the signed encoding in octets of the modulus is 2048 + 8 bits or 257 bytes. But the bit length - as it is called in most programming API's - of the modulus is still 2048.

Note that OpenSSL shows the generation parameters required to use the Chinese Remainder Theorem to speed up RSA calculations. In principle a private key could also consist of just the private exponent and the modulus.


Does 3-DES take approximately the same time to encrypt 1B and 1KB?

This is both a DES (or any block cipher) and a programming concern. It is not a problem, just something to be aware of.

The reason time/character decreases with larger plaintexts is that the initial overhead and memory management takes up the bulk of time with small inputs. With large inputs (megabytes+) the time/char will stabilize to a fairly consistent number. Memory management techniques and encryption mode of operation also effect overhead. Making a copy of the plaintext instead of reading its memory space directly into the block cipher state for example.

DES processes blocks of 64-bits, which is 8 bytes at a time. So your time per character between 0 and 8 will be the same, as it is processing a single block.

There is also the accuracy of the measurements, which in Java is probably not using a high precision event timer, and will therefore be extremely inaccurate in measuring events that take small fractions of a second to complete. Try using a hand stopwatch to measure something that takes 0.02s to complete for example, you will never get a consistent or even accurate measurement.

Because block ciphers are fairly quick in processing block inputs, you will need to process several megabytes of data in order to get a more accurate time/block. Try 8 million bytes to start. You will need to increment the data size to get to around 10s of processing time before you can get an accurate time/block.


Random numbers used for ECC Diffie-Hellman

Your analysis is correct, generating a random 32 Bytes number and reducing it modulo $n$ gives an incorrect distribution (in general). I see three natural solutions to this issue: (I'm not a programmer and do not know which one would be the most suited for efficiency)

1) Generate the random number directly between $1$ and $n-1$ as you suggested

2) Generate a random $32+\kappa$ Byes number, where $\kappa$ is a security parameter (e.g. $\kappa = 10$ for 80 bits of security), and reduce it modulo $n$. This gives a distribution statistically close to uniform over $[1, n]$

Explanation: so, you have this $256$ bit modulus $n$, and you pick (say) a random $336$ bits integer. You do not obtain a uniform distribution by reducing it modulo $n$, but "almost": let us write $2^{336} = n \times N + R$, with $R < n$ ($N,R$ are the quotient and remainder of the Euclidean division by $n$). Intuitively, if we had generated our number between $1$ and $n \times N$, we would indeed have obtained a uniform distribution when reducing it modulo $n$ (as it is a multiple of $n$). The bad case happens when the random number we generate is between $n\times N + 1$ and $2^{336}$. But this happens with probability at most $R/2^{336} < 2^{256}/2^{336} = 2^{-80}$, which is extremely unlikely. Thus, by adding some security parameter to the size of the sampled bit strings, you ensure that you'll get a distribution statistically close to uniform.

As poncho pointed out in a comment, when $n$ is already chosen very close to $2^{256}$, then there is no need to add such "security bits", taking a random 256 bits number will already give something close to uniform (my answer focused on the most general case).

3) Generate 32 Bytes integers and use rejection sampling: if a number is higher than $n$, ignore it and restart until you get a number smaller than $n$. This gives a uniform distribution over $[1,n]$ and is efficient if $n$ is very close to $2^{256}-1$

Any of those solution should be a proper fix to the problem; the direct modulo reduction seem theoretically unacceptable to me (but might be accepted on the basis that it still provides some good security level in practice, enough at least to circumvent any known attack, even though it's a bit dirty).

EDIT: the case $k'=0$ when $k=n$ that you mention is not a problem as it has a negligible probability to happen.


Parallel Composition of ($\epsilon, \delta$) differential privacy

Your conjecture seems correct. If the sets are disjoint then the mapping $\bar{M} = (M_1,\dots,M_n)$ is $(\max(\epsilon_i),\max(\delta_i))$-DP. Note that for every database $D$ and any $x$, $\bar{M}(D)$ differs from $\bar{M}(D\setminus {x})$ in only one coordinate by the disjoint assumption, w.l.o.g., they differ in the $j$'th coordinate. Therefore, the difference between the density functions of $\bar{M}(D)$ and $\bar{M}(D\setminus {x})$ is the same as the difference between $M_j(D)$ and $M_j(D\setminus {x})$.


Using crypto to build a clone resistant system

That's actually a really interesting question. Mostly because I think there is no really good solution.

However, considering that we are putting more and more computing power into all devices and more and more of their value is derived from the software it seems to be very relevant for the future.

If you want something that can even remotely be called cryptography you should define your security model. Given that you are using a commodity board what is stopping your software from running on a different one of these boards? Clearly nothing, because that's how you are going to produce your devices. So the only option you really have is to keep your software secure in the first place.

I actually think solving this problem is the reason why many devices are IoT devices in the first place. It allows you to put the important parts of the software on the server and authenticate your users when they want to use it.
Let's say this is

Option 1: Keep parts of software on your own hardware and restrict access.

Now, there are a lot of other techniques that are somehow trying to achieve your goal...

Option 2: Trusted execution environment (careful, that article is basically advertisement) A way to protect your software from being extracted from the device. Something like Intel's SGX or ARM Trustzone.

Option 3: Make a mess

A combination of the following might give you sufficient security:

Whitebox crypto: Hide cryptographic keys that your software might be using. Afaik all schemes are broken. However there is no shortage of companies trying to sell it to you. (Sad, it doesn't even have its own Wikipedia article.)
PUF: To achieve hardware binding (that's the common term for making something run only on your boards) you use some hard to fake property of the hardware like the initial state of the RAM when turning the device on.
Code obfuscation: Add unnecessary abstraction and redirection and such to your code so that somebody cannot reverse engineer it with reasonable effort and remove all the safeguards you have put in.

Option 2 seems much more solid but a combination of these might help mitigate sufficiently many attacks for you to confidently deploy in a scenario where you don't have a TEE or the option to do things online.


Achieving 32-bit verification code with 16-bit CRC?

I'll assume $n$ is a multiple of 4. One option is to compute the CRC16 of the bytes $d_{4j},d_{4j+1}$ ($0\le j<n/4$), giving 2 bytes appended as $d_{n},d_{n+1}$; and the CRC16 of the bytes $d_{4j+2},d_{4j+3}$, giving 2 bytes appended as $d_{n+2},d_{n+3}$.

That

reduces the work compared to the original solution, because each byte is processed once instead of twice;
has a desirable property of CRC32: if all bits in error are within the same 32-bit segment of data+CRC (including within the same 32-bit word), then the error is detected [note: the capability to always detect short error bursts lying across data and CRC requires care in the finalization of the CRC];
detects a large number of random errors with odds comparable to a 32-bit CRC, including all errors affecting an odd number of bits.

One very negative aspect compared to a 32-bit CRC is that errors which, for hardware reasons, are bound to always affect the same single bit of a 32-bit word (or some wider multiple) are not detected far more often ($2^{-16}$) than for a 32-bit CRC ($2^{-32}$).

Therefore, that solution is fine to detect communication errors on a serial link, but poor to detect corruption of a Flash or DRAM memory (assuming there is no built-in ECC) as occurring from a defective sense amplifier, and I guess a marginal write.

In the context of detecting corruption in memory (without ECC), I would consider

computing a CRC16 of the whole data;
simultaneously counting the number of 0 bits in the data (which will fit 16 bits if $n<2^{13}$);
storing the concatenation of that along the data.

Integrity check using the count of 0 bits has the property (desirable in the context of storage in computer memory without ECC) that if an error changes all bits in error to the same value, then it is always detected (that includes errors in the count). Also, it is fast to compute even on CPUs without hardware popcount, using a small table or various bit tricks.


Single-purpose symmetric encryption scheme for single files

As you can make up from this encryption scheme, I'm using the encrypt-then-authenticate approach to enforce ciphertext integrity. In step 2 of the decryption process I perform this authentication step. If the calculated HMAC turns out to be equal to the HMAC in the file, does this mean, apart from the implied ciphertext integrity, that the supplied passphrase is certainly the same as the original passphrase used for the encryption, resulting in this ciphertext? Or should I perhaps use an additional plaintext HMAC, stored in the encrypted file header, to ensure passphrase validity.

If the HMAC verification of the ciphertext checks out, then you can be assured that the password is the same.  Of course HMAC (and any hash algorithm) has many collisions (i.e. lots of inputs that map to the same output), but the chance that you will run into one of these in a real-world scenario with decent-sized hash are near infinitesimal.  A common practice is to put a checksum (e.g. CRC32) on the plaintext to ensure that the decryption happened properly.  If you want to guard against decryption errors (usually not necessary unless you have a "can't fail" super-sensitive system), then you can add such a plaintext checksum.

  I'm unsure which cipher mode of operation would be most suitable for this kind of encryption. I couldn't find much information about this, as most recommendations are based on network-based cryptography. CBC and CTR both seem good options, and I believe the security difference are negligible, as long as the implementation is done correctly. In Cryptography Engineering, the authors used to recommended CTR, but now prefer CBC as it's easier to "get right". CTR seems more susceptible to a poorly generated IV, as it's essentially a stream cipher. Which one would you recommend?

In your scenario, since you are doing encrypt-then-sign, the mode doesn't matter so much.  CTR (a stream mode) and CBC (a block mode) have different error propagation properties, different attacks, but these are somewhat irrelevant because of the pre-decrypt verification that you are doing.  In my experience, CBC is more robust in more situations while CTR tends to be more flexible, but it doesn't matter for you.  Go with CBC if you like.  It's more important to ensure that you get a unique IV for each encryption operation.

  This question partially depends on my choice of cipher mode (question 2). Does generating a new salt and IV for each file mutation really offer a noticeable security benefit? This may sound like a stupid question, but file mutations only take place sporadically, and thus a sufficiently large IV should deter any ciphertext attacks?

You absolutely must use a different IV for each password encryption operation.  There are attacks that can be mounted against either mode if you fail to use a different IV.  If you do this, then there is no need for the salts.  Unique-per-password salts are used when encrypting or hashing individual passwords separately and help resist rainbow table and similar attacks.  Since you are encrypting and entire file at once, I'd recommend skipping the salt and just ensuring that you use a unique IV per encryption (i.e. each time you change the file, or encrypted contents in your lines 5 and 6).

  According to the Horton Principle, the MAC should "Authenticate what is being meant, not what is being said". I understand this includes the structure of the file etc., but would including salts and IV be wise as well?

As I said previously, no need for salts.  However, it is common practice to authenticate (MAC, in your case) the modification-sensitive portions of the plaintext header.  So if you had fields for version number, date, owner, etc, then you should concatenate those fields with your ciphertext and MAC the whole thing together.  You don't show anything like that above, but perhaps you should consider adding such fields for other security reasons.  Technically the IV is not modification-sensitive, but since you don't have a checksum on the plaintext, then it might be good idea to MAC the fields: 4 (IV) || 5 || 6.

  In my design I'm using the same underlying key as input for the encryption and HMAC function. Does the use of two separate salts offer any security benefit, or is reusing the same key inherently insecure anyway?

Again, neither salt is needed in this implementation.  HMAC (with a good underlying SHA like SHA256 or SHA512) and AES do not have practical cryptanalytic attacks and I don't know of any attack that can exploit either one if you were to use the same key for both, but this is generally considered bad practice.  Instead, just make 2 keys.  Or use a key derivation function (see NIST SP 800-108) to derive 2 keys from a single source of entropy/password.

Someone else already mentioned it, but is there a reason that you are using AES-CBC + HMAC instead of just AES-GCM?  AES-GCM is an authenticated, encrypted mode of AES and the authentication tag is over the ciphertext.  There are some nuances that you need to be aware of before using this mode, but it could be a simpler implementation for you.  Otherwise, AES + HMAC is fine and fairly widely used as well.


How to Understand Authenticated Key Exchange?

One way to understand this is through a rather abstract and constructive viewpoint, abstracting away specifics.

As you mentioned, a DH key exchange needs to be done in an authenticated manner otherwise man-in-the-middle attacks become possible. In other words, we needs the communication to happen on a authenticated channel.

How do we get an authenticated channel? One way is to use digital signatures. They would allow to verify that the message comes from the legitimate sender. However we still have a problem, the verification keys needs to be transmitted somehow and so far we only have an insecure channel.

In order to resolve this problem, we send digital signatures parameters over an authenticated channel that is obtained by using certificates. If we trust certification authorities, we have indeed an authenticated channel.

Everything put together in a constructive way:

1) Using certificates we construct an authenticated channel that allows exchange of digital signature parameters

2) Using digital signatures, we construct an authenticated channel that allows key-exchange(D.H).

3) Using key exchange results we could also construct a secure channel.


Obviously the answer is about the attack potential by adversaries, such as large governments or organisations. And the truth is: we don't know. The attack on SHA-1 shows that the NSA is certainly not the only large organisation to worry about. Anybody with enough money to rent a server farm could be your adversary.
In the end, we don't really know. But there are the Lenstra equations and the site keylength.com which can be used to put in the right numbers. Entering a symmetric key size of 90 will show that 2033 is about the time that this key may be cracked using ga 50M machine, given that Moore's law holds. That's not that far away anymore. Note that single processor speed is not what Moore's law is about; it doesn't seem to be slowing down yet.
To protect against quantum computing you'd have to double the key size of symmetric algorithms in the end. But how fast quantum computers evolve is anybody's guess. Currently there have been some break-throughs with e.g. the Dutch government spending heavily on research at Delft. However a machine that could attack large keys - or anything heavier than a (normal sized) Sudoku - still seems some way off.


The reason Lamport's scheme is secure against a passive attacker is that even if they see $H^{n-1}(p)$ for a given $n$, the server would require the preimage of that hash, $H^{n-2}(p)$ on the next login.

The active attack, in comparison, allows Trudy to find an earlier iteration than the server is expecting. That allows calculating several login hashes by iteratively hashing the captured one. It is even possible to do it transparently to the user, by replacing the hash they give by the one the server is expecting.

Alice types the name and password.
Workstation sends "Alice".
Bob sends $n$. Trudy intercepts it and replaces it by for example $n' = n-10$.
Workstation computes $h = H^{n'-1}(p) = H^{n-11}(p)$. Trudy intercepts and replaces by $H^{n-1}(p) = H^{10}(h)$.
Bob hashes once, sees a match.

Now Trudy can calculate the next ten hashes that Bob expects, like the next one: $H^{n-2}(p) = H^{9}(h)$. This allows several logins as Alice.


How effective is quantum computing against elliptic curve cryptography?

Elliptic curve cryptography is not presently vulnerable to quantum computing because there are no quantum computers big and reliable enough to matter.

But it would be vulnerable to quantum computers big enough to run Shor's algorithm.  All elliptic curve cryptography* is based on the difficulty of finding a secret integer $n$ given the scalar multiple $Q = [n]P = P + \cdots + P$ of a base point $P$ on an elliptic curve, say $E/k\colon y^2 = x^3 + 486662 x^2 + x$ where $k$ is the prime field $\operatorname{GF}(2^{255} - 19)$, a curve popularly known as Curve25519.†

On a capable quantum computer, Shor's algorithm would rapidly find a period $(\delta, \gamma)$ of the function $(a, b) \mapsto [a]P - [b]Q$.  Any such period satisfies $$[a - b n]P = [a]P - [b]Q = [a + \delta]P - [b + \gamma]Q = [a + \delta - (b + \gamma)n]P$$ for any $a$ and $b$ including zero, so that $0 \equiv \delta - \gamma n \pmod \ell$, where $\ell$ is the order of $P$, from which we can trivially recover $n \equiv \delta \gamma^{-1} \pmod \ell$.

The number of qubits, and number of gates, and running time to compute this is a small polynomial function of the number of bits in the order $\ell$, which is ~256 in typical cryptography.  Most of the quantum circuit would be devoted to computing scalar multiplication, just like computing scalar multiplication on a classical computer, costing $O(\operatorname{poly} \log \ell)$ quantum gates just like it costs $O(\operatorname{poly} \log \ell)$ time and memory on a classical computer; the magic happens in the quantum Fourier transform to find a period, which costs only $O(\log \ell \cdot \log \log \ell)$ quantum gates.

The danger today is primarily for long-term secrecy of documents and conversations in the face of future quantum cryptanalysis: TLS key agreements with elliptic curve Diffie–Hellman, for example, could be attacked with Shor's algorithm, just like finite-field Diffie–Hellman, enabling retroactive decryption of TLS sessions.  (The ‘forward secrecy’ property of DH—or really, the erasure of session keys by all parties involved—is of no use if the adversary can break the key agreement cryptography.)  For authentication and signature, e.g. Ed25519 signatures, the danger is not so much as long as you have an upgrade path for changing the signature scheme by the time Shor-capable quantum computers become feasible.

* I am not addressing isogeny-based cryptography, such as SIDH or CSIDH or SIKE, which also involve elliptic curves but which are all based on problems other than elliptic curve discrete logs—problems that are conjectured to remain infeasible to break even if Shor-capable quantum computers were practical.

† This is not the only way to attack elliptic curve cryptography.  There are many other issues to worry about, as catalogued in SafeCurves.  But in a well-designed protocol with a well-designed curve, the best known way to break the cryptography is to compute discrete logs.


Recommended way of adding a pepper/secret key to password before hashing?

Given the clarified answer, I suggest you do the following:

$T = F_k(\text{password})$

$Y = H(T, \text{salt})$

where $F$ is a PRF (pseudorandom function) and $H$ is a slow hash.  Here $k$ is the secret key (the "pepper").

You can instantiate $F$ with AES-CMAC or SHA256-HMAC (or any other good PRF).
When you use $F$, feed the secret key $k$ (the pepper) into the key input of the PRF, and feed the password into the message input for the PRF.  (This corresponds to your option 1.  I do not recommend using your option 2, and definitely not option 3.)

You can instantiate $H$ with a slow hash like bcrypt, scrypt, or PBKDF2.
When you use $H$, feed $T$ into the password input for the slow hash, and feed the salt into the salt input for the slow hash.

Finally, store $Y$ and the salt in your database of hashed passwords.

This scheme ensures that if the key $k$ (the "pepper") is kept secret and is not known to the adversary, then the adversary will not be able to recover any of the passwords.  It also ensures that if the key $k$ does become known to the adversary, the best the adversary can do is a dictionary attack on the passwords -- but this will be slowed down because of the slow hash.  Consequently, if $k$ does become known to the adversary, this scheme should be no worse than just using scrypt/bcrypt/PBKDF2 without a pepper.


Perfect Secrecy in Symmetric Key Systems

In general, no. Consider the following perfectly secret probabilistic encryption scheme. Encrypt exactly like a one-time pad. Then, with probability 1/4 add a 0-bit after the ciphertext, and with probability 3/4 add a 1-bit after the ciphertext. For decryption, first throw away the last bit, and then decrypt as in the one-time pad. The ciphertexts in the ciphertext space are now not equiprobable.

Having said this, Shannon's theorem says that when the message space, ciphertext space and key spaces are all the same size, then a scheme is perfectly secret if and only if every key is chosen with the same probability and every plaintext and ciphertext have a single key mapping one to the other. A simple corollary from this theorem says that in this case (where all spaces are the same size) then the ciphertext values are all equiprobable.


Why are some key stretching methods better than others?

On the non technical side, the main reason for choosing PBKDF2 or BCrypt is that they're commonly used. This means they have seen more analysis, reducing the risk of a dumb mistake and it's easier to defend them when somebody questions your choice.

What I dislike about your third variant is that it does not separate the different inputs. This isn't an issue if both key and salt have fixed length, but it's ugly. PBKDF2 has similar ugly but not practically relevant properties.

PBKDF2 has pretty similar properties to your third scheme. It has the additional feature of a variable output size, but it's so badly designed that this is more of a pitfall than an advantage. But you could always combine HDKF-Extract with your scheme if you need long outputs.

Bcrypt on the other hand has an advantage over both your scheme and PBKDF2 (used with common hashes like SHA-2): It's not friendly to GPUs. If you can afford 100ms of hashing on your CPU, the cost of a GPU based password cracker computing a hash is higher for Bcrypt than for PBKDF2. When an attacker uses an ASIC or FPGA, the advantage of bcrypt is smaller and you should consider using scrypt instead.

I also think that the need for including the password on each iteration of the hash (which you pointed out as a flaw in the first scheme) is often exaggerated. Even with a short hash like MD5 exploiting this is infeasible and becomes completely ridiculous once you use a 256 bit hash like SHA-256.


Using an AES-256-GCM key as a salt to SHA-256

I'd split the key into two 256 bit keys using HKDF, and use one key for the GCM mode, and the other for the hash over the plaintext. However, I then would use HMAC rather than SHA-256 as it accepts and the key as a separate entity in the application.

The advantages of the HKDF key derivation function is that there is more "distance" between the keys used for the authenticated encryption and hash function. That said, just reusing the key is not likely to introduce direct vulnerabilities. It's also more "neat" using a KDF to derive other keys for other purposes, from a single shared secret key.

The advantage of using HMAC is that you are protected against length extension attacks. Furthermore, HMAC explicitly accepts a key rather than just data, so the key may be better protected against attacks, depending on the system that it is used on of course.

Otherwise, yes, using a hash over the shared secret and data may be used to determine uniqueness (well, with a high degree of certainty in the case of cryptographic hashes, of course), assuming that the key doesn't change during the time that this property is required. So yeah, I don't see how this would not work (but please don't view that as scientific proof).


Is it possible to break a hash-based block cipher?

This is not a "block cipher" because a block cipher is a key-dependent permutation of the space of blocks of a given size. Here, you handle data by blocks, but the "encryption" part is done by XORing with a value $H(k+n)$ which depends on the key $k$ and on the "block number" $n$. So you do not have one permutation (for a given key), but a lot of them.

Correspondingly, it is unclear what "CBC" would look like with such a beast. If you imagine it as this:

$$ C_0 = M_0 \oplus IV \oplus H(k+0) $$
$$ C_n = M_n \oplus C_{n-1} \oplus H(k+n) $$

then this is unfortunately hopelessly weak if you encrypt two distinct messages with the same key, even if you use distinct IV -- because the XORs with $IV$ and $C_{n-1}$ can be trivially cancelled by anybody ($x\oplus y \oplus y = x$ for all $x$ and $y$) and you end up with the infamous "two times pad".

As @PaŭloEbermann says, your cipher propose is a stream cipher: it is XORing with a key-dependent pseudo-random stream, generated from the key $k$ but independent of the plaintext. Here, the pseudo-random number generator is built from a hash function. There are several ways to do that, not all being good, because some well-known hash function (MD5 and the whole SHA family) suffer from something known as the length extension attack. The "safe" way to build a PRNG out of a hash function is to use HMAC, and that is called HMAC_DRBG. It is a NIST standard. The same standard defines Hash_DRBG, which is faster (and similar to your proposal) but potentially weaker because it relies on some ill-defined properties of the underlying hash function.

Of course, an IV should be added, and not with a kind-of-CBC, as explained above. Rather, replace your key $k$ with $IV||k$ (concatenation of the IV and the key). There again, subtle weaknesses may lurk.

Either way, building a (stream) cipher out of a hash function is possible, but it requires care, and often offers rather poor performance. Indeed, hash functions are fast at processing lots of input data. Here, you want it to produce lots of output data -- and for that, hash functions are not very fast. Even with SHA-1 and Hash_DRBG, the resulting cipher would be slower than a common AES.


Breaking a XOR cipher of known key length?

After more time on this challenge, here is what I've done to solve it.

Divide the text by N columns, where N is the length of your key.

Run frequency analysis on each column. Given enough data, you will most likely get a character that is present far more often than the others. Since my text was in french, it was the letter e.

For each column, find one instance of the value that is supposed to be an 'e' and XOR that data with the letter 'e' to find the Nth letter of the key.

Given enough data, you will find an 'e' for every column, giving you all the letters of the key.
Try decrypting the text with the key, and voilà, you get the original text.

Once I've made up this way of solving the puzzle, I found out that it was a really common way to solve a XOR encryption, and that tools existed that could do it for you far faster than manually.

For example, xortool : https://github.com/hellman/xortool

xortool -l 8 input.bin -c65

-l is the length of the key, -c is the hexadecimal value of the most frequent letter in the language you think the text is in.

That command is near instantaneous.


Is there something wrong with using a hash function as a PRG?

This is fine, although you should avoid these conversions to and from hexadecimal, that are no needed and may introduce side channels.

Now, since you are using JavaScript, you can simply use the WebCrypto API. Specifically crypto.GetRandomValues, which can fill an array up to 65536 bytes.


Is it safe to initialize secret keys by just reading /dev/random on Linux?

Yes, in any algorithm where keys are just random numbers, reading them from /dev/random is safe.

However, /dev/random blocks if the kernel's entropy estimate goes to zero so it is often a good idea to use a user space CSPRNG seeded from /dev/random or /dev/urandom for session keys and other similar random numbers that are used in bulk. The newer getrandom interface may be preferable when available.

Using /dev/urandom or getrandom directly is also fine, when you do not need a high rate of randomness, as they are rather slow (on Linux < 4.8 at least).


As fgrieu points out, the number to factor can be written as
$$
n = 2^{2048} + 538\cdot 2^{1024} - 67515\,.
$$
We can identify this number with the polynomial $f(x) = x^2 + 538x - 67515$,
 with $n = f(2^{1024})$. Furthermore, if we factor this polynomial as $f(x) = g(x)\cdot h(x)$ then $n = f(2^{1024}) = g(2^{1024})\cdot h(2^{1024}) = p\cdot q$ since polynomial evaluation is homomorphic.

Since this is a simple quadratic equation, it is easy enough to find that $f(x) = (x - 105)(x + 643)$. Thus, the factors are $2^{1024} - 105$ and $2^{1024} + 643$.

The Fermat factorization algorithm is particularly efficient for integers whose factors are very close together. This happens to be the case here.


Could a key derivation function be used to encrypt data with a weaker key?

Yes, with caveats.

Yes, because this is the entire stated point of password-based key derivation functions (e.g., PBKDF2 or scrypt). The caveat is that more iterations only get you so much; 100,000 iterations is only enough to increase "effective" entropy by a little over 16 bits ($100,000 \approx 2^{16}$) — to match a real 128-bit key, you'd need a password with 112 bits of entropy, which is an impractical 19-character alphanumeric password.

One approach without this caveat is to use a PBKDF to derive an actual encryption key from a key and password; this has the benefits of both systems. There's a real 128-bit (or 256-bit) secret that protects the data, which is typically invisible to a user, but you require a password to access and use that key.


Key management is always an issue, and you could write books about it.

I'd myself create two keys by splitting one off a normal symmetric key. This key I would print out on paper and store in a secure location such as a physical (fireproof) safe. I'd store the other part in another secure location, such as a bank, referring to the bank from the safe (you know where your own safe is, but will you remember the details of the bank?). To decrypt you can re-establish the key and then decrypt the password.

There are literally hundreds of other ways of accomplishing the same thing though. Which one is most secure depends on the situation and threats. In the end this is about balancing convenience and security. You can have a look at key sharing schemes to have some more ideas for splitting and securing keys. If security is a real issue you should be just using keys, no passwords - they are simply too easy to guess or too difficult to remember.

I'd not store the keys on flash - there is too much chance of it losing too much charge. Burying anything is not a good idea at all; somebody may accidentally or purposefully find it and with the amount of trash we generate, it will not be a great archeological find far into the future - please do not bury your electronics. Besides the chance of damage is just too likely when you bury anything.


Converting a C25519 curve into a NIST-supported curve for FIPS crypto

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

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

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


Are there attacks that break collision resistance but not preimage resistance?

Hash functions are usually designed to be both collision and preimage resistant. In practice, due to lower complexity, collision attacks usually come first. For instance, collisions for MD5 were theoretically constructed in 1996, and practically in 2004, whereas the first preimage attack with complexity 2^123 appeared in 2009 and has not been much improved since. MD5 could be considered preimage-resistant, but not collision-resistant at that time.

Attacks that violate collision resistance are usually based on differential cryptanalysis, whereas most of preimage attacks are based on the meet-in-the-middle principle.

It should be easy to construct artificial examples where either of properties is violated. E.g., the function F(x) = 0 for x=0,1, and F(x) = SHA-256(x) elsewhere - has trivial collisions, but most cryptographers would believe in its preimage resistance. In turn G(x) = x for even 256-bit x, and F(x) = SHA-256(x) elsewhere allows preimage recovery with probability 1/2, but it is likely to be as collision resistant as SHA-256 is.


Verifying a downloaded file with an .asc file

OK, so Paul already shows the site where they explain what you need to do. I'll explain how this helps you to verify the files you downloaded.

Lets start with the .asc version, which consists of a set of hashes and a GPG (or actually OpenPGP) signature. To verify the signature you need a public key. Now if you've already got a CentOS system you may already have it installed on your machine. If not you can download it (per instructions) and verify it with the fingerprint. The fingerprint is on a HTTPS protected page on the main site, so this way you can trust the public key. Therefore you can also verify the signature with it. To compare the fingerprint this way is slightly tricky as an attacker could have taken over the main site. Then again you only need to do this once and then keep the key on your system (so the window of attack should be minimal).

This is the difference with the sha256sum.txt. If the site or mirror is taken over then an attacker may replace the sha256sum.txt, giving you only a false sense of security. If you download this file then you should download it from the main site, preferably protected by TLS, not from a mirror.

Downloading the .asc is still preferred as it is likely signed when the build is generated, on an back-office computer.

Don't use sha1sum.txt or sha1sum.txt.asc, it's not as secure due to vulnerabilities within SHA-1.


The Input Parameter in the question is called a Label in PKCS#1v2.1; this standard states it might be empty, or be expressed in some specified syntax. I borrow Victor Shoup's explanation from Remark 3 in this paper:

  A label is a byte string that is effectively bound to the ciphertext
  in a nonmalleable way. It may contain data that is implicit from
  context and need not be encrypted, but that should nevertheless be
  bound to the ciphertext. We view a label to be a byte string that is
  meaningful to the application using the encryption scheme, and that is
  independent of the implementation of the encryption scheme. For
  example, there are key exchange protocols in which one party, say A,
  encrypts a session key K under the public key of the other party,
  say B. In order for the protocol to be secure, party A's identity
  (or public key or certificate) must be non-malleably bound to the
  ciphertext. One way to do this is simply to append this identity to
  the cleartext. However, this creates an unnecessarily large
  ciphertext, since A's identity is typically already known to B in
  the context of such a protocol. A good implementation of the labeling
  mechanism achieves the same effect, without increasing the size of the
  ciphertext. Labels may also be of arbitrary and variable length, but
  we do not impose the restriction that the encryption and decryption
  algorithms should be able to process labels as streams. Both the ECIES
  and RSA-OAEP submissions include the notion of a label (where it is
  called an encoding parameter), although absolutely no indication was
  given as to the role or function of a label. Nevertheless, it seems to
  be a potentially useful feature (..)


If it's implemented properly, it is as secure as any other form of encryption in preventing those who don't know the data from obtaining it from the encrypted data. However, it does have one fundamental limitation that, so far as we know, is inherent in the technology -- Anyone who has the same file you have can potentially prove that you have that file.

The general way such algorithms work is as follows:

The object to be encrypted is validated to ensure it is suitable for this type of encryption. This generally means, at a minimum, the the file is sufficiently long. (There is no point in encrypting, say, 3 bytes this way. Someone could trivially encrypt every 3-byte combination to create a reversing table.)
Some kind of hash of the decrypted data is created. Usually a specialized function just for this purpose is used, not a generic one like SHA-1. (For example, HMAC-SHA1 can be used with a specially-selected HMAC key not used for any other purpose.)
This hash is called the 'key'. The data is encrypted with the key (using any symmetric encryption function such as AES-CBC).
The encrypted data is then hashed (a standard hash function can be used for this purpose). This hash is called the 'locator'.
The client sends the locator to the server to store the data. If the server already has the data, it can increment the reference count if desired. If the server does not, the client uploads it. The client need not send the key to the server. (The server can validate the locator without knowing the key simply by checking the hash of the encrypted data.)
A client who needs access to this data stores the key and the locator. They send the locator to the server so the server can lookup the data for them, then they decrypt it with the key. This function is 100% deterministic, so any clients encrypting the same data will generate the same key, locator, and encrypted data.


Is MD5 second-preimage resistant when used only on FIXED length messages?

Right now, the best published attack against MD5's preimage resistance (first preimage, actually, but it applies to second preimage resistance as well) finds preimages in cost $2^{123.4}$ average cost, which is slightly better than the generic attack (average cost of $2^{128}$), but still way beyond the technologically feasible. The attack rebuilds the preimage as a two-block value (128 bytes) and can be adjusted to any larger length.

Therefore:

There is no practical attack against your 4096-byte hash tree nodes yet.
But the fact that they have a fixed 4096-byte length does not appear to improve the situation.

Still, the foundation of the security of MD5 appears somewhat flimsy, so it is not recommended (at all) for new systems. If you have severe CPU constraints, then you might want to consider the SHA-3 candidates. The 14 "round 2" candidate functions have been quite thoroughly investigated, and no break has been found in any of them; in that respect, they are all stronger than MD5, and arguably stronger than SHA-1, which has a known collision attack (but no known preimage attack). Some of them are quite fast, and competitive with MD5. Depending on your architecture (8-bit CPU, small 32-bit ARM, big modern 64-bit PC with AES-NI opcodes...), you would be most interested in BMW, ECHO, Shabal and Skein. "The" SHA-3 (Keccak) is not as fast as these (except on dedicated FPGA / ASIC).

It is usually best, for public relations, if you use a standard, recommended function. However, if you decide otherwise, using a function which has survived some scrutiny by cryptographers with no known weakness is arguably better than using a function with big weaknesses.


What are the practical differences between SCRAM and PAKE (OPAQUE) for simple authentication?

The goal of SCRAM is to determine whether the two endpoints share a common secret. SCRAM achieves this by having both parties compare/exchange $\textrm{HMAC}(s,i)$ where $s$ is the secret and $i$ is a counter/nonce. There is more to it than this, but this is the main essence. If $s$ is a high-entropy cryptographic secret, then this is fine: seeing some HMAC outputs doesn't help an eavesdropper/impostor guess other HMAC outputs.

But if the shared secret is low-entropy like a password, I would say that SCRAM by itself is not suitable. The protocol transcript of a SCRAM interaction gives an eavesdropper enough information to test offline whether their guess for $s$ is correct. So SCRAM is susceptible to offline dictionary attacks. My understanding is that usually SCRAM is run inside of some encrypted tunnel, to protect from external eavesdroppers. But if I am a passive man-in-the-middle of that encrypted tunnel (which seems reasonable since there would be no need for SCRAM if we've already authenticated the endpoints!), I'll learn enough from the SCRAM transcript to allow offline dictionary attack.

SCRAM only does authentication, but OPAQUE is a full-fledged PAKE, which gives much more functionality:

key agreement: the endpoints establish a key in the presence of an eavesdropper, if their secrets match. Note that SCRAM uses a hash function (in HMAC) as its only cryptography. it is well known that secure key agreement is not possible from hash functions alone. This fact justifies why PAKEs are more expensive / use public-key crypto techniques.
designed for low-entropy secrets: a PAKE must resist offline dictionary attacks on the shared secret. The only way that an attacker can test a guess for $s$ is to interactively run the PAKE with one of the parties (online dictionary attack).


From the sound of your questions, it almost appears that you have some confusion between the CBC-MAC key and the CBC-MAC tag.

The CBC-MAC algorithm takes the message (in this case, most likely the ciphertext) and a secret key; it outputs a tag (which can be public).  The security property of CBC-MAC is that someone who does not know the key cannot generate a valid message, tag pair, even if he sees a huge number of valid message, tag pairs (of course, he is not allowed to suggest a message, tag pair that he has been given).  Actually, it works even if he is allowed to specify the messages.

The idea is that if the receiver (Bob) gets a message and tag pair that validates, that means that the sender (Alice) must have generated it.  After all, only someone who knows the key is able to generate such a pair, and the only two are Alice and Bob (and Bob knows he'll never generate such a pair, so Alice must have sent it).

With that in mind, your questions:

  Does the second key (for CBC-MAC) need to be secret?

Absolutely; if the attacker is given that key, then all security bets are off.  He can easily generate a valid MAC tag for any message he picks.

  How to join such key with the ciphertext? By concatenating it at the end?

No, you don't send out the key with the ciphertext; it needs to be secret.  On the other hand, you can send the tag with the ciphertext; concatenating the tag at the end is one common approach.


Is it possible to cryptographically prove when was the last time a ciphertext was decrypted/encrypted?

Updated answer:

No, this is not possible with cryptography.
You have the ciphertext and you have the key.
For all anyone knows, you could have made a copy of those to some other computer and decrypted the ciphertext without telling anyone.
There's no way (with cryptography) to prove you haven't done that.

One approach would be to implement a secure service and hire an independent auditor to audit your code and architecture and certify that you appear to have set things up in a way that protects your customers' data.  You could hire an independent security pro to review your system and write a public report that customers can view.  I don't know if this would give potential customers a better sense of comfort or if it would be worth the money.

The only approach I can think of, to solve this through technical means, would be to use trusted computing.  Trusted computing relies upon trusted hardware (TPMs), and its support for remote attestation would allow you to prove to others what code you are running.  You could publish the source to your software to allow anyone to verify that your software doesn't make a copy of their keys or their data, and use remote attestation to prove that you're using that good software.

However, using trusted computing in this way is extremely complicated.  Trusted computing is bleeding-edge stuff; it's an engineering and management hassle of major proportions.  Moreover, most customers probably won't have the patience, skills, or desire to undertake all of the tasks that would be required to verify that your system works properly.

So, I think there's no technical solution for your problem.  You'll have to rely upon your customer's trust, your reputation, contractual guarantees, and other social/legal means, instead of technical solutions.

A comment: your problem is more an information security problem than a cryptography problem.  Are you familiar with IT Security?

Original answer:

I think you need to define the problem better, to identify who are the principals/participants and what is the threat model.

If the decryptor knows the ciphertext and decryption key and wants to subvert the protocol, you cannot prove that the decryptor didn't decrypt the ciphertext.

The decryptor can prove that he did decrypt the ciphertext (using a zero-knowledge proof of knowledge, possibly with some timestamping).  However, he cannot prove that he read the decrypted message or paid attention to it or acted on it, so I suspect this will be basically useless in practice.

If you can limit access to the ciphertext or the decryption key, then you can prove some partial statements.  For instance, if you don't release the ciphertext to anyone until time $t$, you can prove that no one could possibly have decrypted it before time $t$.  If you know the key, though, you won't be able to prove that you didn't release it before time $t$ (except possibly through use of TPMs / trusted computing), so you'll probably need to be trusted for this to be meaningful.

There are many other possible scenarios -- to propose a specific solution, we'll probably need to know the threat model and requirements in a bit more detail.


Proving that an encryption scheme is susceptible to certain attacks

how will having a few samples of plaintext-ciphertext pairs help Eve find out p [in the second scheme]?

Well, suppose we have four plaintext/ciphertext pairs, and lets look at what is available to the attacker.  We make the plaintexts $m_1$, $m_2$, $m_3$, $m_4$, and the corresponding ciphertexts:

$$e_1 = a m_1 + b + k_1 p$$
$$e_2 = a m_2 + b + k_2 p$$
$$e_3 = a m_3 + b + k_3 p$$
$$e_4 = a m_4 + b + k_4 p$$

for unknown values $a$, $b$, $p$, and $k_1, k_2, k_3, k_4$.

First step: can we combine these ciphertexts in a way to form three values that do not involve the unknown $b$ values?  Hint: consider $e_1 - e_2$.

Second step: can we combine the values from step 1 in a way to form two values that are both multiplies of $p$?

Third step: given two values which are multiples of $p$, what's an efficient way to recover $p$?

  With the 3rd one, I'm not seeing how her ability to choose particular plaintext and finding out their corresponding ciphertext helps her find out how to decrypt the message.

Suppose you ask for the encryptions of the values $(x,w), (y,w), (z,w)$; how could we use the previous observation to recover $p$?  (Hint: you might find it a bit easier if you assume a few more chosen texts).


How can RSA be used to compactly sign and encrypt?

Re-using RSA key pairs for both encryption and signing is catastrophic, since it leaks the private key. So two pairs of keys will be needed.
RSAES-OAEP is a system that allows RSA to encrypt short (shorter than the modulus) messages. It's slow, and the length restriction is a big limit, but it does work.
RSASSA-PSS is a system for signing messages using RSA.
So encrypt using RSAES-OAEP and the recipient's encryption public key, then sign the ciphertext using RSASSA-PSS and the sender's private key.
A better solution is to use static-ephemeral ECDH to  create a shared secret between the recipient's static key and the sender's ephemeral key, then encrypt the message using an AEAD like AES-GCM-SIV, and sign the whole ciphertext+IV+Tag using RSASSA-PSS.


Is there a name for this 'enhanced' caeser shift and if so, is it trivial to break?

So if I understand correctly, the following describes your cipher:

Take letters A-Z to be numbers 0-25.
Let Mi represent letter i of the message
Let Ci represent letter i of the ciphertext
Let n be the ceasar shift number
Let m be the skip number
Let the key be described as the tuple (n,m)
Then, Ci = (Mi + n + m*i) modulo 26

The system is a type of polyalphabetic cipher. The Trithemus cipher is the same as your system, but it always used a key of (0,1). Your system is also equivalent to a Vigenere cipher that uses a key that is the full alphabet, but rotated a skip number of letters.

I can't find any reference to historical use of this system, so very likely there is no standard name for this type of cipher.

This cipher is still easy to break, because there are strict limits on the numbers you can choose for the shift and skip.

The shift can only be from 0 to 25, because any higher numbers work the same as a number from 0 to 25.
The skip can also only be from 0 to 25, for exactly the same reason.
This means the total set of keys is 26*26 = 676

It's not hard to brute force 676 keys with a computer, but you usually don't have to. If you try all 26 skips, then you can figure out which skip is correct by doing a frequency analysis of the letters. The letter distribution that looks closest to the letter distribution of English is probably your skip. Then you just have to guess the shift based on the same frequency analysis you just did.


Steps to encrypt endorsements to a petition

This depends on the level of authenticity you want to provide with your system. A lot of public petition systems do not enforce authenticity of petitioners at all. Basically, anyone can submit a petition in behalf of their neighbor, for example, simply by introducing relatively public info about them (name, address, ID number, etc). In this case, public-key encryption seems the way to go. For example, this could be done with plain, old PGP, where the public key belongs to the government officer.

On the contrary, if you want the petitioners to actually sign the petition (digitally, obviously), then this has to be done with some sort of digital signature. I think you could implement this with designated verified signatures:

  A designated verifier signature is a signature scheme in which
  signatures can only be verified by a single designated verifier who is
  chosen by the signer.

In this case, the designated verifier could be trusted government officer receiving the petition.


Yes. Learning with Rounding (LWR) is a special case of LWE, where the errors are introduced deterministically by scaling and rounding operations. If you had an algorithm that could solve LWE, the same could be used to solve LWR.
Thus, Module-LWE is at least as secure as Module-LWR.


RSA Question- max number of ascii characters encrypted at one time

Don't do it!  It's a trap!  Applying the arcane mathemagical spell that is RSA trapdoor permutation to ASCII does not an encryption scheme make!  The RSA trapdoor permutation conceals uniform random elements of $\mathbb Z/n\mathbb Z$; to use it for anything else is a mistake, and a fool's errand clothed in naive textbook idealism.

It's like telling your class that modern aviation is built out of paper airplanes, except unlike the obscure mathematics of RSA, paper airplanes self-evidently cannot function like an Airbus A380 or even a Cessna C-34.  If this is how you are taught aeronautical engineering, I exhort you to find another instructor!

Real encryption schemes based on RSA use the fancy mathematics to conceal a 256-bit secret key for symmetric-key authenticated encryption such as AES-GCM, and use that to encrypt the message.

That preface said, taking your question at face value:

The space of ‘messages’ $M$ is set of the integers between $0$ and $N$.  Any other integer is equivalent, as far as RSA is concerned, to one between $0$ and $N$, because all arithmetic is modulo $N$; for example, $N + 1$ is equivalent to $1$, because they differ by a multiple of $N$.

So, for a modulus $N$ between $2^{15}$ and $2^{16}$, there are at least $2^{15}$ distinct messages.  How many ASCII characters are there?  How many pairs of ASCII characters are there?


Why is data signed with SHA256-RSA-PKCS and digest signed with RSA-PKCS different?

TLDR: it's the DigestInfo
The hash-and-RSA-PKCS schemes defined in Current Mechanisms 2.1.14 do the full scheme of RSASSA-PKCS1-v1_5 which is now defined in RFC8017 primarily in 9.2 as a combination of EMSA-PCKS1-v1_5 'encoding' (usually called padding) plus the RSASP1 and RSAVP1 primitives. (In prior versions the document was organized differently, but the substance was the same.) Concretely this consists of:
#1 hash the data
#2 encode the hash value, plus the hash algorithm, in an ASN.1 structure DigestInfo in DER; since each hash algorithm has constant output size, this amounts to prepending a fixed prefix depending only on the algorithm, as given in note 1
#3-5 prepend padding of the form 00 01 FF...(at least 8) 00
(8.2.1#2) treating the result as a number m, apply RSASP1 which does m ^ d mod n (or for verify 8.2.2#2 apply RSAVP1 which does s ^ e mod n; this is stated as before the three padding steps above but actually can just as well be after)
OTOTH RSA-PKCS defined in 2.1.6 for Sign/Verify does ONLY the latter two of those steps, not the first two. As the text says: "This mechanism corresponds only to the part of PKCS #1 v1.5 that involves RSA; it does not compute a message digest or a DigestInfo encoding as specified ... in PKCS #1 v1.5 ." You externally hashed the data which is the first step, but did not do the DigestInfo which is the second (required) step, and thus got the wrong result.
Except for being PKCS11 (hardware) rather than software, this is crossdupe at least:
https://stackoverflow.com/questions/521101/using-sha1-and-rsa-with-java-security-signature-vs-messagedigest-and-cipher
https://stackoverflow.com/questions/9951559/difference-between-openssl-rsautl-and-dgst
https://stackoverflow.com/questions/38767660/multiple-openssl-rsa-signing-methods-produce-different-results
https://stackoverflow.com/questions/63582544/how-does-jwt-implement-rsa256-signature-verification-in-nodejs
https://stackoverflow.com/questions/62955968/how-can-realize-openssl-pkeyutl-sign-by-java
https://stackoverflow.com/questions/48013643/get-the-sha1-hashed-value-from-xml-signature-value
https://stackoverflow.com/questions/43490188/separate-digest-signing-using-java-security-provider
https://stackoverflow.com/questions/57929493/openssl-digitally-sign-digest-only
https://stackoverflow.com/questions/9380856/openssl-signature-difference-when-using-c-routines-and-openssl
https://stackoverflow.com/questions/13419201/why-are-the-rsa-sha256-signatures-i-generate-with-openssl-and-java-different
https://stackoverflow.com/questions/15092298/signing-20-byte-message-with-256-bit-rsa-key-working-with-openssl-exe-but-not-in
https://superuser.com/questions/943972/what-is-the-difference-between-openssl-pkeyutl-sign-and-openssl-rsautl-sign


How does Hash with random cryptography work?

Like I said in the comment I think You mean hashing password with random salt.
The salt is a random string. It's good for it to be more then 128 characters.

Usually adversarys use rainbow tables for cracking hashes. Rainbow table is pretty much a list of all possible strings and their hases. Every day powerfull computers add more strings to those tables. At the moment every password that's 8 and less characters can be cracked in matter of seconds.

Let's say Alice wants to log in into website of "Bob Bank". Her browser takes her six letter password from textbox, hashes it and sends it to the server. Evil Edvard intercepts those hases and in seconds finds the password. Doesn't sound so good.

With salt situation looks better. Bank has assigned a 128 character long string when Alice was making an account. Banks server sends this string to the browser. Evil Edvard can see it. Alices browser adds this string to the password and then hashes it. But now the hash is not of 6 character password, but of 134. Edvards rainbow tables are useless. He has to make new ones. This process can take months.

If another user will also use identical password he's salt still will be different, and hash acquired by Edvard will be different. He has to compute rainbow tables


Standards for finite-field discrete log cryptography

So, why do the NIST/TLS standards not allow for cofactors greater than 2?

Actually, NIST does allow larger cofactors - see table 1 in SP800-56A - they allow the subgroup (q) to be significantly smaller than the modulus (p).

As for TLS, previous versions of TLS (1.2 and earlier) did allow the server to specify the group (and made no requirements about the cofactor).  In TLS 1.3, they allow only a handful of specific groups to be used, all with a cofactor of 2.  Is there a specific reason they should have included a group with a larger cofactor?


Why is this signature independent of the message?

Note that in the first variant given a signature and knowing the public key, the message $m$ is uniquely determined. Information-theoretically dependent means what you assume it means. An unbounded adversary who can compute all discrete logs, can thus easily figure out the unique $m$ in the first scheme.
In the second variant, the message is information-theoretically hidden (even for unbounded adversaries). Note that $m+zr$ is basically „an encryption“ with a secret key $r$ (and $r$ does not appear anywhere else). So for $v=m+zr$ you can always find a suitable $r‘$ for any possible choice of $m‘$. This information-theoretically hides the message.
The problem with your modification is as follows. In the second variant a message is $(m,r)$. If you modify it to $a^{x+xy(m+r)}$ then you can open your signature to any message $m‘$ by computing $r‘=(m+r)-m‘$ and providing $(m‘,r‘)$ as the new message. This clearly will verify. Thus, your modification does not yield an unforgeable signature scheme. For the second variant of the CL signatures, however, the scheme can be shown to be unforgeable as $z$ basically commits you to the $r$ value.


Can Paillier ,RSA or any other schemes be used for universal re-encryption like elGamal?

With Paillier, it's easy; generate a random encryption of 0 ($r^n \bmod n^2$ for random $r$ r.p to $n$), and then homomorphically add it to the encryption (that is, $C2 = C1 \cdot r^n \bmod n^2$), and you're done (and all you need is the public key).

I don't believe RSA allows this as a possibility...


How would you build routers that can route photons from Alice to Bob for QKD?

I know of three possible ways of addressing this problem (only one of which is currently practical).

Have the routers have QKD systems on each link; and so Alice does QKD with router 1, which does QKD with router 2, which does QKD with Bob.  The obvious issue with this is that router 1 and router 2 also get the keys.  This obviously doesn't work on the Internet (which you don't trust every service provider between you and Bob), it may be plausible in, say, a data center (where the same organization runs the entire network, and so does have some trust on their own infrastructure.
Have routers that don't actually measure the quantumsignal.  I have heard of two proposed subvariants of this one:

One based on mirrors that can be moved ultraquickly.  In this case, when Alice wants to talk with Bob, she informs the routers, which would quickly set their internal mirrors so that photons from Alice get reflected at Router 1 to Router 2, which reflects them to Bob.  Now, this doesn't do anything about the QKD length limitations, and I actually haven't heard this option mentioned in the last several years, and so people may have given up on it.
One based on Quantum Amplification.  In this case, Router 1 would take photons from Alice 1, and in a way that doesn't break the Quantum State, forward them to Bob in some amplified/quantum error corrected state.  We currently can't do this; this appears to be quite difficult (perhaps not much easier than building a full Quantum Computer), and I'm not exactly sure how they intend to get around the 'no cloning theorem' (which states that you cannot duplicate a quantum state, hence it's unclear how they expect to amplify one).

QKD satellite; here, there is a satelite that sends pairs of entangled photons to the two end points (and the end points use their entangled photons to agree on keying material).  There's just been given a proof-of-concept, and there are several obvious issues ("does everyone have a satelite receiver?  How do you talk between end-points that are beyond satelite range?  How do you deal with satelites that can communicate only intermittently (currently: at night, when the weather is clear, and when the LEO satellite is over the horizon)?"


You basically want a full disk encryption mode for a block cipher; XTS mode seems to be the current standard. In your case each "disk block" is actually a file offset.

Note that using a stream cipher or counter mode is NOT secure if the data is ever modified in the file, as it would violate the cardinal sin of using the same key and initialization vector to encrypt different messages. This is why fancier modes like XTS were created.

CTR mode could be secure if the file were encrypted exactly once per (key,IV) and was then read-only or append-only. However, going that route would involve a massive rewrite and data migration if your requirements ever changed. So find a respected library that implements XTS mode, do not write it yourself as you are not a cryptographer.

Failing that, I would strongly consider punting and using whatever OS-level file or volume encryption system do its job, such as EFS/BitLocker on Windows or eCryptfs/dm-crypt on Linux. All modern OS have such facilities. Even if you might need some platform specific code or configuration, it would be a massive time-saver and isolate the crypto layer from your application.


Encoding an element in $r=r'||h(r')$ way

Question1: How can we show/prove that the random element only with a negligible probability can have such structure?

If we assume the random oracle model and have $h: \{0,1\}^* \to \{0,1\}^n$ then we can state that $h(.)$ is equivalent to randomly sampling from $\{0,1\}^n$. Thus for a random element $r = r'||r''$ the probability that $r$ has the structure $r'' = h(r')$ is $\frac{1}{2^n}$ since all $2^n$ possible outputs of $h(r')$ are equally likely. Thus for $n=160$ we have a probability of $\frac{1}{2^{160}}$ which is negligible.

  Question2: Can we reduce the $h(.)$ output size to 80-bit (which is not the standard hash function output size) and set $p$ as smaller prime number (e.g. 128-bit )and prove a random value can have the above structure with only negligible probability?

Sure, the same logic as above can be applied here as well, now with the case $n=80$ and a corresponding probability of $\frac{1}{2^{80}}$ which is still negligible.

Note that the size of $r'$ is not relevant to the probability of a random element having the structure $r'||h(r')$, the probability solely depends on the size of $h(r')$.


What is the advantage of Encrypt-then-MAC over Encrypt & MAC separately the plaintext

I'll be assuming the question means Message Authentication Code (MAC) where it uses "Signature" and "Hash". MAC, signature and hash are three different things: MAC uses a secret for generation and verification, signature uses a secret for generation only, hash uses no secret.

Following comment, and most important: sending in clear a MAC of the plaintext, as in "encrypt and MAC separately" sending $\operatorname{ENC}(M)\mathbin\|\operatorname{MAC}(M)\,$, without any further specification about the MAC, would be very poor practice: depending on the MAC, that can leak some information about the message $M$. In particular, for any deterministic MAC (as HMAC is) and a fixed key, identical messages will lead to identical MACs, and are thus trivially detected, breaking IND-CPA security.

The other historically used argument for encrypt-then-MAC (against MAC-then-encrypt) is that the seemingly natural corresponding procedure on the receive side is verify-MAC-then-decrypt, implying that decryption will only be carried on ciphertext that passed an integrity test. The adversary thus can not observe use of the decryption key on ciphertext that it chooses arbitrarily, since that ciphertext won't pass the MAC test and won't be decrypted. This in turn blocks a number of attacks that submit artificial or altered ciphertext to a decryption device, and use it's observed behavior to deduce useful information, or induce some desired behavior.
One example of vulnerable decrypt-then-verify-MAC would be an implementation where decryption is followed by a padding check, insuring that the last 16-byte block of ciphertext ends with 0 to 15 byte(s) at 0x00, then (walking back) a byte at 0x80; and if not aborts the use of the received ciphertext, only performing the MAC check if it does. By observing the timing of the decryption device, an adversary could then determine if the padding check fails or succeeds. For block encryption in CBC mode, iterating that apparently minor information leak allows decryption.
Other examples can be made, including side-channel attacks by differential power analysis of the decryption, when limited valid ciphertext is available to the attacker.

One serious problem with this historical argument for encrypt-then-MAC is that it is technically valid only if there is verify-MAC-then-decrypt on the receiver side. However, it is entirely possible to run decryption and MAC verification concurrently even for ciphertext produced with encrypt-then-MAC. And such concurrency is highly desirable, for it avoids scanning the ciphertext twice, which typically would have an impact on performance, at worse would make using crypto impractical.
Also, by integrating integrity check with encryption, it is possible to get the integrity part at sizably lower computational cost than that of a MAC. For these reasons, state of the art is authenticated encryption, such as AES-GCM-SIV. Thus in modern practice we do not encrypt-then-MAC, and even more seldom verify-MAC-then-decrypt, making this historical argument pointless. Authenticated encryption does secrecy, authentication & integrity in one primitive, no necessarily with a separate generic MAC.


Decrypt (homomorphically and symmetrically) encrypted data using (homomorphically) encrypted key?

Yes, this is possible as long as the homomorphic cipher supports all operations necessary to implement the symmetric encryption algorithm. So for a partially homomorphic cipher like Paillier, this will not be possible. With a fully-homomorphic cipher (or somewhat homomorphic cipher configured with sufficient multiplicative depth), this is very feasible, even for standard symmetric algorithms like AES.

For example see Homomorphic Evaluation of the AES Circuit. AES has become a sort of defacto standard benchmark for fully homomorphic ciphers.

See also Ciphers for MPC and FHE, where the researchers look at designing secure symmetric ciphers that are specifically optimized towards homomorphic evaluation.


Apart from the slightly unusual nomenclature, this is Shamir's secret-sharing scheme with $n=6$ and $k=3$ (i.e., the secret is shared into six pieces, any three of which can be combined to retrieve the secret).

In this case, the pieces are as follows:

$$\begin{align}(x_0, y_0) &= (10, 25) \\
(x_1, y_1) &= (20, 405) \\
(x_2, y_2) &= (30, 272) \\
(x_3, y_3) &= (40, 129) \\
(x_4, y_4) &= (50, 479) \\
(x_5, y_5) &= (60, 316)\end{align}$$

Only three of these are needed to retrieve the secret. As described in the Wikipedia article, this is done by calculating a set of Lagrange basis polynomials:

$$\begin{align}\ell_0 &= \frac{x - x_1}{x_0 - x_1} \cdot \frac{x - x_2}{x_0 - x_2} = \frac{x - 20}{10 - 20} \cdot \frac{x - 30}{10 - 30} = \frac{x^2}{200} - \frac{x}{4} + 3 \\
\ell_1 &= \frac{x - x_0}{x_1 - x_0} \cdot \frac{x - x_2}{x_1 - x_2} = \frac{x - 10}{20 - 10} \cdot \frac{x - 30}{20 - 30} = \frac{-x^2}{100} + \frac{2x}{5} - 3 \\
\ell_2 &= \frac{x - x_0}{x_2 - x_0} \cdot \frac{x - x_1}{x_2 - x_1} = \frac{x - 10}{30 - 10} \cdot \frac{x - 20}{30 - 20} = \frac{x^2}{200} - \frac{3x}{20} + 1
\end{align}$$

All you need from these polynomials are the constant terms, which are multiplied by the corresponding $y$ terms to give you the secret value:

$$\begin{align}s &= (3 \cdot 25 - 3 \cdot 405 + 1 \cdot 272) \pmod{503} \\
&= 138 \end{align}$$


This isn't specific to StrongSwan, but here is a Cisco article relating to rekeying. In this example, keys are replaced every 1,000 or 10,000 seconds. It is, obviously, best to rekey as often as possible, while taking into consideration hardware limitations. I would say that every few hours would be more than enough.

-Hope this helps.


Encryption for IOT devices with minimal overhead

For passively powered RFID tags, I settled on 160-bit ECC (Curve25519) to exchange the keys and SPECK for the actual encryption on a software platform.  If I make my own hardware, I use SIMON instead of SPECK.  For an IoT application, I see no reason not to do something similar.

If you are looking for comparisons of symmetric ciphers regarding throughput and power, I would suggest the SIMON and SPECK paper and the paper on PRESENT as both have good power tables and comparisons.


What rule(s) for a good S-box is this one violating and how does it relate to non-linearity etc.?

I have a software tool for analyzing basic differential and linear properties of s-boxes.
Submitting your s-box to my tool yields the following output:

The most probable differential characteristic(s):
1 -> 215 with probability 10/256 (xor -> xor) (weight 1 -> 6)
Linearity: 18.0 ((166, 166))

Differential probability
So we can see that the most likely difference is that a difference of 1 will output a difference of 215 with probability 10/256. The type of difference used was xor, it is possible to use other functions such as addition to attempt to find other differentials. A probability 10/256 differential is not horrible, but it could be better; For reference, the AES s-box has a max differential probability of 4/256.
Linearity
Linear cryptanalysis is analogous to differential cryptanalysis, but to many it may slightly more complex to reason about. The "linearity" value shows the distance to the nearest linear function. The more closely that the s-box approximates a linear function, the more easily it can be attacked. Again, the value for the s-box you presented is moderately good, but is again not as good as the AES s-box, which has a linearity value of 16.0.
Further Understanding
For a true understanding of the above, I recommend this resource for studying differential and linear cryptanalysis. It is a relatively gentle introduction compared to an actual paper on the subject. I developed my software for analyzing s-boxes while following these tutorials.


How to optimise a finite field multiplication?

a better way to optimize the code is to use multiplication by 2 concept(xtime).

xtime(x) is multiplication by 2 which is left-shift modulo irreducible polynomial ($x^8\oplus x^7\oplus x^6\oplus x\oplus1$ = 0x1C3)

xtime is implemented in c code with irreducible polynomial (0x1c3) as following

#define xtime(x)   ((x<<1) ^ (((x>>7) & 1) * 0xc3))

= addition modulo 2(xor in code)

The binary representation of your values is as following:

16  : 00010000

32  : 00100000

133: 10000101

148: 10010100

192: 11000000

194: 11000010

251: 11111011

16*x (mul16) is as following
16 is $2^4$ (4 times left shift)-> mul16(x)=xtime(xtime(xtime(xtime(x)))). it can be rewritten as of mul8 as following xtime(mul8(x)). mul8 is defined as nested triple time

32*x (mul32) is as following
32 is $2^5$-> mul32(x)=xtime(xtime(xtime(xtime(xtime (x)))))= xtime(mul16(x)).

133*x = (128+4+1)x = 128*x+ 4*x + x;
= ($2^7 + 2^2 +1$)x = (mul128(x)^xtime(xtime(x))^x) = (mul128(x)^mul4(x))^x)

192= (128+64)x = mul128(x)^mul64(x)
194= (192+2)x =  mul192(x)^xtime(x)

I will let you do the 148 and 251 multiplication, you can use the following code for assistance:

#include <stdio.h>
#include <stdint.h>

#define xtime(x)   ((x<<1) ^ (((x>>7) & 1) * 0xc3)) //P: x8⊕x7⊕x6⊕x⊕1
#define mul4(x)    (xtime(xtime(x)))
#define mul8(x)    (xtime(mul4(x)))
#define mul16(x)   (xtime(mul8(x)))

#define mul32(x)      (xtime(mul16(x)))
#define mul64(x)      (xtime(mul32(x)))
#define mul128(x)     (xtime(mul64(x)))&0xFF
#define mul133(x)  (mul128(x)^xtime(xtime(x))^x)&0xFF
#define mul192(x)  mul128(x)^mul64(x)&0xFF
#define mul194(x)  mul192(x)^xtime(x)&0xFF

uint8_t gmul(uint8_t a, uint8_t b) {
    uint8_t p = 0; /* the product of the multiplication */
    while (a && b) {
            if (b & 1) /* if b is odd, then add the corresponding a to p (final product = sum of all a's corresponding to odd b's) */
                p ^= a; /* since we're in GF(2^m), addition is an XOR */

            if (a & 0x80) /* GF modulo: if a >= 128, then it will overflow when shifted left, so reduce */
                a = (a << 1) ^ 0x1c3; /* XOR with the primitive polynomial x^8 + x^4 + x^3 + x + 1 (0b1_0001_1011) – you can change it but it must be irreducible */
            else
                a <<= 1; /* equivalent to a*2 */
            b >>= 1; /* equivalent to b // 2 */
    }
    return p;
}

int main(){
    // printf("%x\n",mul16(0x06)&0xFF);
    // printf("%x\n",mul32(0x06)&0xFF);

    // printf("%x\n",mul32(0x22)&0xFF);
    // printf("%x\n",gmul(0x22,32)&0xFF);

    printf("---------\n");
    printf("%x\n",mul128(0xf5)&0xFF);
    printf("%x\n",gmul(0xf5,128)&0xFF);

        printf("---------\n");
    printf("%x\n",mul64(0xf5)&0xFF);
    printf("%x\n",gmul(64,0xf5)&0xFF);

        printf("---------\n");
    printf("%x\n",mul192(0x35)&0xFF);
    printf("%x\n",gmul(192,0x35)&0xFF);

        printf("---------\n");
    printf("%x\n",mul133(0x35)&0xFF);
    printf("%x\n",gmul(133,0x35)&0xFF);

            printf("---------\n");
    printf("%x\n",mul194(0xe5)&0xFF);
    printf("%x\n",gmul(194,0xe5)&0xFF);

    return 0;
}


Recovering plaintext from AES-128 given round key 10 and ciphertext

Since this is CTF, I'll give you some detailed hints.

Normally by using only a ciphertext, you cannot determine the plaintext, since for every key the deciphered ciphertext is a valid plaintext and some of them are perfect in English or any other language. So, some other information must be given to you for verification.
16-Byte just means one block for AES.
There is a difference in key schedules between AES-128 and AES-182,AES-256.
Your CTF is not possible with the key schedules of AES-192 and AES-256
You have given only, one round key. The different key schedule of AES -128 will enable this.
Search for AES master key Round Keys ( in this site)


Division of Point in Elliptic Curve: Getting Back Point

With Elliptic Curves, we can compute the order of any point (and, in particular, the point $nP$; this is especially easy on the curves we actually use for ECC, because those curves typically have an order $hq$, for a small $h$ and a large prime $q$ (and the order of any point is a divisor of $hq$).

So, if $q$ is the order of the point $nP$, and if $n$ is relatively prime to $q$ (since we generally have $q$ prime in practice), we just compute $n^{-1} \bmod q$; we then have $(n^{-1} \bmod q)nP = P$; that is, multiplying $nP$ by the scalar $n^{-1} \bmod q$ gives us back the original point.


BGV KeyGen-- Can a maliciously-generated secret-shared key break security (e.g. SPDZ)?

Short answer: I don't know of any practical attack that exploits a malicious key generation protocol to, say, learn something about an encrypted message. However, I imagine this is highly context-dependent (e.g. it seems hard to attack SPDZ this way, there may be other applications that are vulnerable) and there is no proof that no such attack exists.

Longer answer:
A malformed public key can potentially lead to decryption errors, where the probability of an error depends on some secret information (such as a private key). This allows for selective failure attacks, where the adversary observes whether an error occurs or not to try and learn something about the secret, and makes it difficult to prove the protocol secure.

In general, these kinds of attacks can be very concerning, although in this case it appears harder to exploit.

Consider a malformed public key $pk = (a, \hat b:= b + \hat e) \in R_q^2$, where $(a,b)$ is a correct key and $\hat e$ is some maliciously chosen, large error.

The first component of an honestly generated ciphertext $(c_0,c_1) = Enc_{pk}(m)$ has the form
$$c_0 = \hat b\cdot v + p\cdot e_0 + m$$

where $v$ comes from the ring-LWE secret distribution, and $e_0$ is a noise term (both sampled during encryption).

The malicious $pk$ introduces an additional error $\hat e \cdot v$ into $c_0$. When decrypting the ciphertext, decryption will likely be correct if $\|\hat e \cdot v\|_\infty < q/p$, but otherwise an error will occur.

Now, if decryption succeeds, the adversary will learn one bit of information on the secret $v$, namely that $\|\hat e \cdot v\|_\infty < q/p$. This means we can no longer use the standard technique of showing ciphertexts are pseudorandom under ring-LWE. That's because the proof requires $v$ to be distributed like a ring-LWE secret and completely unknown to $n-1$ parties, so that $(c_0,c_1)$ looks like a valid ring-LWE sample.

Finally, note that it seems very hard to exploit this leakage in a practical attack, particularly since the $v$ value is different with every ciphertext, so the leakage can't be reused. I'd speculate that it might even be possible to prove this secure for SPDZ under some variant of ring-LWE with leaky secrets.


Chosen ciphertext insecurity in an ElGamal variant

There is no known way to compute $(g^a)^k \mod p = g^{ak} \mod p$,

given only

$g^k \mod p$ and

$g^a \mod p$

as per the Decisional Diffie–Hellman assumption. This is roughly equivalent to the discrete log problem. This is described in more detail in this paper.


The only way you will have a certain answer will be by mailing their designers.

Using multiple S-boxes increases the size of the code and decreases the possibility of working with different blocs in parallel.

Using a single S-box also simplify the way the specifications have to be written. The simpler the specifications are, the less prone to make error at the implementation step you are.

Not related to Camellia but on the same idea:

  JP Aumasson: why nobody uses SHA-3? FIPS 202, a 29-page specs written for cryptographers, not for users [source]

  JP Aumasson: seriously NIST, in 2.5 years no one had the idea that, perhaps, it would be good to simplify that thing? like, ditch the greek part [source]

However, using a single S-box implies some sort of symmetry in your bloc cipher which MIGHT be the reason why the designers of Camellia preferred to use 4 S-boxes instead of only one.


How can we tell if there is a Zero-Knowledge Proof for a given problem?

Assuming this, how would we use logic to find out if a given problem has a ZKP or if it does not?

From a theoretical standpoint, this has a rather simple answer: If the language you are trying to prove lies in IP or PSPACE then there is an (efficient) ZKP for it.

So, from a formal standpoint, a ZKP looks as follows:
There's a prover and a verifier. The prover is (in principle) computationally unbounded, the verifier is a probabilistic polynomial-time Turing-Machine. Now both sides know the specification of the language and the potential element (the "word") of the language. An interactive proof is now that the prover tries to convince the verifier that the word is in the language and has at least a 2/3 chance to succeed if it is (this is called "completeness"). On the other hand if the word is not in the language, any prover should at most have a 1/3 chance to succeed to convince the verifier that the word is in the language (this is called "soundness").

Every such interactive proof can be turned into a zero-knowledge proof.
Additionally if a language is in PSPACE there is an interactive proof for it (which can be turned into a zero knowledge proof).
Though one may want to note that neither construction is "efficient" in a practical sense.

A zero-knowledge proof has the same completeness and soundness properties as an interactive proof but additionally for each verifier there must be a simulator that when given an input word must be able to output a communication transcript that is indistinguishable from that that the given verifier would have with a real prover for every word in the language. That means that one could also have come up witht the transcript on their own and thus it doesn't leak anything only the prover could know.

Note for our local pedants: The above talks about computational zero-knowledge proofs.

  On a similar note, is there a ZKP to show that a file (that one wants for someone else to download) is not malicious?

Well, if you can come up with a protocol that would prove that to said person, you could convert it into a zero-knowledge proof. But I suppose the tricky part here is defining what "not malicious" means in a formal sense that satisfies soundness (i.e. a prover shouldn't be able to convince somebody that a file is "not malicious" even though it is).


Min Entropy Value for Health Test per NIST 800-90B for 32 bit Noise Source

Clearly the installation of health tests must come after the development of the entropy source.  As part of that development, you'd need to assess the min.entropy of your new system under whatever sampling methodology you choose. And Min Entropy H comes out of that assessment. It is "the min-entropy of the samples from a (digitized) noise source or of the output  from  an  entropy  source;  the  min-entropy  assessment  for  a  noise  source or entropy source."

NIST suggests two tracks, either:-

Confirm IIDness via permutation testing, and take min entropy as log(Pmax[]).
Estimate it on the basis of a non-IID hypothesis using the methods of § 6.3 Estimators.

It's all detailed in §6 Estimating Min-Entropy. Track 2 is known to be unreliable as our measurements of entropy of non-IID sources are still inadequate. I recommend that the tightest bounds on measuring Min Entropy H will be achieved by  evolving your sampling methodology to obtain IID samples.


Do all attacks against PKCS1 v1.5 encryption require an oracle

PKCS#1 padding succeeds in introducing enough entropy (slightly less than 64 bits at the very minimum) to make RSA encryption semantically secure. Furthermore, the number $m$ - the message used for modular exponentiation - it produces will be large enough to protect against attacks that rely on $m$ to be small. That means that the premisses for RSA modular exponentiation seem to be met.

It seems therefore unlikely that there are passive attacks on PKCS#1 v1.5 padding. Active attacks could succeed, as Bleichenbacher has shown. It may be that there are attacks on the random number generation as well, but that will require an attacker to have even higher privileges; the attacker must have access to the secure random number generator used. Usually those kind of attacks are considered attacks on the secure system creating the ciphertext itself instead of attacks on the algorithm itself.

Finally there are side channel attacks on modular exponentiation, but those are as much a problem for OAEP as for PKCS#1 v1.5 padding. They also rely on the attacker gaining more knowledge from the system than should be allowed for a secure system to exist.


"[T]he process using ZK-snark" is to express the statement being proved as an R1CS system, produce proving and verifying public keys, produce and verify a snark-proof. A large non-trivial R1CS system is often expressed in terms of "gadgets" according to high-level "circuit structure".

A popular algorithm/proof was introduced at https://eprint.iacr.org/2016/260.pdf and implemented in libsnark. Zcash-specific "circuit" is documented in their "protocol" paper.


How are secure hashing and encryption algorithms proven?

My personal opinion: "proven secure" is more of an advertising slogan than anything else. The one-time pad and certain multiparty protocols can be shown to have some kind of information-theoretic security; these are exceptions to the rule. "Don't roll your own crypto" is still sensible advice however.

For the rest of this discussion, I'll try and stick to facts.

In public-key cryptography, there are three kinds of number-theoretical primitives in common use (RSA groups, prime-order groups based on finite fields F_p, prime-order groups based on elliptic curves) for which the security properties and arguments are based on a combination of experience and heuristics. For example, RSA has been around for 35-odd years now without anyone finding a way to break it when used properly; a lot of effort has gone into factoring integers but the best number-field sieving algorithms available today are still nowhere close to factoring 4096-bit RSA moduli. Similar considerations apply to taking discrete logarithms in finite fields.

What "provable security" does is construct a layer of cryptographic components on top of these primitives and prove that a certain formal definition of breaking the components is at least as hard as breaking a certain formal notion of security on one of the primitives. For example, one can prove that if you obtain my ElGamal public key and you give me any two messages of the same length, and I give you an ElGamal encryption of one of them back, then you cannot do any better than guess at random which of your two messages I encrypted --- unless you can also solve one of cryptography's basic hard problems over the group I'm using to do my ElGamal encryption, which has been studied since around the 1980s. (This is formally called the IND-CPA to DDH reduction for ElGamal and is a staple of public-key cryptography 101 courses.)

Does this mean that ElGamal is secure for a particular application? It depends, and it says nothing about "out of band" attacks such as malware on your computer, biased randomness generators etc.

I see the role of security proofs primarily as a layer of security within the cryptographic research community. Proposals for new primitives are rare, and need a jot of justification to be accepted. However, let's say you have a particular application where you want, for example, an encryption scheme for messages where you want anyone to be able to tell just from looking at a ciphertext if the plaintext is all zeroes or not, but nothing else. A cryptographer might be able to design such a scheme for you based on existing primitives or schemes, and then prove that breaking the new scheme with the additional feature is in some way at least as hard as breaking one of the existing and well understood schemes. For example, one could adapt ElGamal and prove that if you can tell an encryption of 01 from an encryption of 10 or 11, then you can also break ElGamal directly.

Within this specific context --- proving a scheme to satisfy some formal notion under the assumption that the primitives already satisfy some formal notion --- the word "proof" in cryptography means the same as it does in mathematics. Cryptographic proofs typically do not address the following points:

Does the primitive in question really satisfy the property?
Is the formal notion of security sufficient for a particular real-world application?
Is the proof correct? The amount of proof-reading done before a paper gets into CRYPTO is much less than for most mathematical journals; mistakes do happen.

To give another example: block cipher modes of operation. The security proof for (say) Galois-Counter Mode (GCM) is that if you had a perfect block cipher B then B-GCM (with random initialisation vectors and a few other things) would give you  authenticated encryption. In contrast, ECB mode has no such security proof (and fairly obviously does NOT provide much security even with a perfect block cipher). AES is not a perfect block cipher, but a pretty good one judging by experience. But we can still say that AES-GCM is a much better choice than AES-ECB.

The original quote, in my opinion, would read better as:

"Cryptographers should not (usually) design new schemes for the sake of adding features without proving them to be at least as secure as existing ones. Everyone else should stick to standardised algorithms."