Solving a system of equations using both arithmetic and bitwise operations

So is there any method of doing this properly?

Here's the most obvious method:

Iterate through the lower 14 bits of $y$, that is, you'll perform the below steps for each of the 16384 possible settings of the lower bits of $y$
Compute what the lower 14 bits of $x$ are, using $x = A - y$ (because the subtraction is modulo $2^{64}$, we can ignore everything higher than bit 13)
Compute what the next 14 bits of $y$ must be, using $y >> 14 = (B - y) \oplus x \oplus (x << 3) \oplus y$
Compute what the next 14 bits of $x$ are, using $x = A - y$ (only this time, because we know 28 bits of $y$, we can reconstruct 28 bits of $x$)
Compute what the next 28 bits of $y$ must be...
Keep on doing this until we start predicting bits of $y$ above 63; because the right shift shifts in 0's, the prediction must be that they are all 0 (and if it predicts something else, we can reject the original guess of the lower 14 bits of $y$).

This involves iterating through 16384 different possibilities; a tad tedious by hand, but fairly trivial for a computer program...

I threw together a quick C routine to do the above search:

typedef unsigned long long num;
void solve_it(num a, num b) {
unsigned lower_14_y;

for (lower_14_y = 0; lower_14_y < (1<<14); lower_14_y++) {
    num y, x, upper_y = 0;
    int i;

    for (i=1;; i++) {
        y = (upper_y << 14) + lower_14_y;
        /* Lower i*14 bits of y are accurate */
        x = a - y;
        /* Lower i*14 bits of x are accurate */

        if (14*i >= 64) break;  /* Got all the bits */
        upper_y = (b - y) ^ x ^ (x << 3) ^ y;
    }

    if (b != y + (x ^ (x << 3) ^ y ^ (y>>14))) {
        continue;
    }
    printf( "Found solution %llx, %llx\n", x, y );
}
}

On my machine, it takes 80usec to run, and as kelalaka suspected, sometimes there aren't any solutions, and sometimes there are multiple (e.g. for a = 0x6c, b = 0xee, there are 7 solutions)


AEAD: Is it secure to decrypt the content encryption key before verifying the MAC?

No, RSA encryption does not provide authenticity, regardless of the padding. This is for the simple reason that anybody can encrypt with the public key. This is irrespective of the asymmetric algorithm used. You need to sign the data to obtain authenticity.

What AEAD does do is to protect e.g. against padding oracle attacks. These can be performed on CBC mode encryption, which could also cost you confidentiality (leaving you with nothing).

In that case however the RSA implementation must also be protected against padding oracle attacks. That basically means that OAEP (or possibly RSA-KEM) should be used instead of PKCS#1 v1.5 compatible padding. Otherwise the PKCS#1 v1.5 unpadding must be performed in such a way that padding oracle attacks are impossible.

With regards to this specific protocol it seems that signatures are handled by a separate document: JSON Web Signature (JWS). Section 11.4 is called "11.4.  Adaptive Chosen-Ciphertext Attacks" and explains the attack on PKCS#1 described above.


Why must the sender and receiver be synchronised in synchronous stream ciphers?

With a synchronous stream cipher (Sync SC), the stream is generated from the internal state, which is built from the key, and depending on the algorithm, a nonce. As the algorithm goes through its steps, the state is changed, and new stream bits are generated. If you want go get to the 11560th bit of stream, you have to start at bit 1 and go through all steps until you get the state at the right point for the bits you want, you cannot just get there in a single step.

Most Sync SCs have a large internal state built from the key, which is processed in some way defined by the algorithm, of which a small bit is exported as the stream. The processing and export is repeated to generate more stream bits.

The asynchronous stream cipher (Async SC) allows you to get there in a single step, or sometimes a little more than 1 depending on the algorithm. CTR mode on a block cipher is an example of an asynchronous, or seekable stream cipher. You use the key, the nonce, and the block number you want, and it generates the stream for that block. Salsa and ChaCha are built using a type of counter mode. CTR mode on a block cipher only requires a single encryption operation to generate any single block, regardless of its position in the stream, and only needs to change the block counter to get there.

In terms of getting the sender and receiver synchronized, with the Async SC you only need to know which block or bit you are on, and you are synchronized. The Sync SC requires the sender and receiver to both generate stream bits until they get to the same point, then they must make sure they do not get out of sync. Depending on the protocol and type of data, they may need to start at the beginning.  If using a Sync SC in a real time communications protocol, that can be a showstopper.

Some Async SCs may need some of the prior stream bits as input, which requires successful decryption of some of the prior data. An example of an Async SC that needs prior stream bits is a hash function that hashes the last output. This is not used in practice because it is not secure, but it is useful as an example.

Block ciphers also need some sort of synchronization, but that is mode dependent. Some modes turn the block cipher into a stream cipher, as referenced above in CTR mode. Some require only the prior block to sync, such as CBC mode. Any block cipher mode will need to keep the block alignment in sync.


Updating the seed key of a PRNG while maintaining initial entropy?

It's a matter of periods in the sequence of numbers generated by the PRNG. If the output of the PRNG has a single period that is of length $2^n$, then you can avoid repetition by appropriately recording the section that you have already used. Thus if you start from $0$ and get the first time to $g_1$, the next time you start from $g_1$ and get to $g_2$, etc. until you have used up the entire period (keep a count of the numbers generated in order to detect that). PRNGs that generate numbers in $[0, 2^{n-1}]$ may not necessarily have the maximal period length of $2^n$. One special kind of PRNGs that have the maximal period length are based on the so-called permutation polynomials mod $2^n$. I used it in one of my software (s13.zetaboards.com/Crypto/topic/7355166/1/), where a literature reference to permutation polynomials as well as a practical  implementation of PRNGs based on them are given.


Has anyone seen a stream cipher being used for FDE

The problem with full-disk encryption is that you don't want to "waste" space on authentication tags (because it would result in odd sector sizes or in a large latency / overhead on-disk).

So we can't have tags, but also don't want to completely give up on the nice features authentication offers, especially the fact that you can detect manipulation. With stream ciphers this is about impossible, because an attacker can change data at bit-level granularity and eg surgically implement a virus on the drive if he knows a file that gets automatically executed at system launch.

Now block-ciphers could make this much harder if you used modes which effectively turn whole disk sectors into blocks which where one bit-flip would destroy (i.e. randomize) the entire plaintext. Unfortunately these modes have computational overhead and thus aren't used.

What we actually do is encrypt each block individually with a specific "tweak"-value for this block which gains us these three properties that we wouldn't have with stream ciphers:

If you change a bit in the ciphertext, 128 bits of plaintext get changed
No matter how much you know about the underlying plaintext, changing bits in the ciphertext will result in different, unpredictable gibberish plaintext each time
You don't have to worry about IV/Nonce management which would be a major headache, because you'd have to change the IV for each sector update and storing the IV has the same problems as with tags, generating it from the sector index has the problem of IV re-use which usually leaks a lot of plaintext-information and incorporating a usage counter has the overhead of having to try different values or storing a counter which is back at the first problem


secret and unique random number generator within a range

A first cursory reading suggests that a format-preserving cipher like NIST SP 800-38G FF1, which makes an easy way to pick permutations of odd-sized blocks with short keys, might help.  But you asked that nobody learn anything about the final number generated by the user.  Here's a simple-minded protocol with approximately five minutes of effort put into it.  Maybe if you put more effort into it you could find a secure multiparty computation that doesn't require a trusted third party.

Pick an authenticated cipher $E_k$ like crypto_secretbox_xsalsa20poly1305.  Pick a DH function $(a, P) \mapsto [a]P$ with standard base point $B$, like X25519.  Enlist the help of a dealer Dale and an independent trusted third party Trent.

Each user generates secret scalar $p_i$ and publishes $P_i = [p_i]B$.
Dale picks a permutation $\pi$ of $\{1,2,\dots,n\}$ uniformly at random.  (You could use FF1 for this, but you might as well just do a Knuth shuffle unless $n$ is so gigantic this protocol isn't feasible anyway.)
Trent picks a permutation $\tau$ of $\{1,2,\dots,n\}$ uniformly at random.
For each $i$, Dale picks a blinding factor $b_i$ uniformly at random and sends $P'_i = [b_i] P_i$ and $\pi(i)$ to Trent.  Dale should make sure to send these messages to Trent in the order given by $\pi$.
On receipt of $P'_i$ and $\pi(i)$, Trent computes $u_i = \tau(\pi(i))$, picks $q_i$ uniformly at random, computes $k_i = H([q_i]P'_i) = H([p_i q_i b_i]B)$, computes $c_i = E_{k_i}(u_i)$, and returns $Q_i = [q_i]B$ and $c_i$ to Dale.
Dale sends $Q_i$, $b_i$, and $c_i$ to the corresponding user, encrypted with their respective public key the usual way if need be.
Each user computes $k_i = H([p_i b_i]Q_i) = H([p_i q_i b_i]B)$ and opens $c_i$ with $k_i$ revealing their unique number $u_i$.

In this protocol:

Each user learns only their own number $u_i = \tau(\pi(i))$: without knowledge of $\tau$ or $\pi$, which are independent uniform random permutations, they can't invert $\tau$ or $\pi$; and without the other users' secret keys or blinding factors $b_i$ they can't decrypt any traffic over the channels between Dale, Trent, and the other users even if eavesdropped.
Dale, knowing only $\pi$, $P_i$, $b_i$,  $Q_i$, and $c_i$, can't compute any $u_i$ without knowledge of $p_i$, $q_i$, $\tau$, or $k_i$: the number is chosen by a uniform random permutation $\tau$ known only to Trent, and encrypted with the user's public key $P_i$ using an ephemeral key pair $(q_i, Q_i)$ known only to Trent and a secret session key $k_i$ shared only by Trent and the user.
Trent, knowing only $\tau$, $P'_i$, and $\pi(i)$, can't compute $i$ or which $P_i$ the blinded key $P'_i$ corresponds to without knowledge of $\pi$ or $b_i$, and so can't tell which user $i$ gets $u_i$: the number $\pi(i)$ is chosen by a uniform random permutation $\pi$ known only to Dale, and the public key $P'_i$ is blinded with the uniform random secret $b_i$ known only to Dale.

CAVEAT CRYPTATOR: I'm a pseudonymous bird on the internet and scratched this out without review or careful thought about it.


Building such a table would be very difficult, because certificate-sizes depend on a lot of (variable-sized) things, including but not limited to:

usage constraints
signatures
public keys
URLs to CRLs and OCSP-servers
Name, location and other identifiers of the key-holder
Name, location and other identifiers of the issuing CA

However, you can estimate the difference between a pure ECC certificate and a pure RSA certificate yourself using simple math.

The relevant properties here are the public keys, the signatures and the signature algorithms. Let's assume that the signature algorithm identifiers are equally large in both cases (e.g. it's a simple OID or an integer).

Now we need to figure out the public key sizes. But this is easy as a public RSA key usually consists of the pair $(n,e)$ of which the lengths are known. Usually $e$ is 2-3 bytes long and $n$ is roughly 2048/8=256 bytes long. Now add these sizes together and ignore the structural ASN.1 encoding overhead and we get roughly 260 bytes of public key of the key-holder for RSA. RSA signatures are as long as the modulus so that's another 256 bytes coming from the CA. So in sum we're at about 520 bytes for RSA.

For ECC, the public key consists of one point, of which we only need the x-coordinate and an additional byte and an identifier identifying the used (standardized) curve. The curve point usually is as large as the curve modulus, e.g. 256/8=32 byte with one extra byte to encode the compression type. The OID is about 9 bytes long. An ECDSA signature by itself consists of two points, so that's another 66 bytes. Summing up you end up at about 110 bytes with ECDSA.

Similar calculations can be done for the security parameters of your choice.


Encoding scalar values to points on Ed25519

The problem may that ed25519-donna uses a decompression that inverts points. That's fixable, but from the description of the problem I think you might be mangling the point encoding somehow, and it isn't quite clear how.


Hash functions to the power of two and three notation

Yes, these notations always seem to mean that H^n(x) (or $H^n(x)$ in mathematical notation) means that $x$ is the first input, and that the next outputs are a hash of the previous output:

H^0(x) = x           // just defined as x below
H^1(x) = H(x)
H^2(x) = H(H^1(x)) = H(H(x))
H^3(x) = H(H^2(x)) = ... = H(H(H(x)))
H^4(x) = ............... = H(H(H(H(x))))
...

so another way to define it is $H^n(x)=H(H^{n-1}(x))$ where $H^0(x)=x$. I've used uppercase H as that seems to be more common.

The construct seems to comply with the exponentiation property within abstract algebra as only the less strong power associativity is required for the function composition of the (hash) functions (beware - the answer on the math site requires some mathematical background).

Usually this kind of construction is used for key stretching; a method of calculating a key from a password (or other low entropy secret) that includes a work factor. In other words, both the user and an attacker are required to perform a number of operations, which makes attacking the password harder.


Which of the following protocols is susceptible to replay attack?

Insecure, you just replay $\text{username}$ and $\text{password}$. Password is also sent in clear text.
Secure, if the hash function $H$ used is strong enough to resist bruteforcing of the password. However you'll also need to send the timestamp so that the server can check the auth, so this scheme is better portrayed as $\text{username, timestamp, }H(\text{timestamp}||\text{password})$.
Insecure, you replay $\text{username}$, $\text{timestamp_now}\ $ and $\text{password}$. Password is also sent in clear text.
Insecure, you replay $\text{username}$, $H(\text{timestamp_now})\ $ and $\text{H(password)}$. Password is also sent in clear text.

Make sure to use a secure PBKDF for password hashing, like $scrypt$.


Encrypt a big file in blocks with AES-GCM: how many nonce do we need?

AES-GCM can encrypt up to $2^{39}-256$ bits with a single key+nonce pair. That's just under 64GiB. A 10GiB file is fine.
If you'd go beyond 64GiB you'll lose security. In that case, either use XChaCha20-Poly1305 (max of 256GiB plaintext per message) or divide the file into chunks < 64GiB.
16MB is far smaller than needed, and will hurt performance.
Most implementations of AES-GCM (Or XChaCha20-Poly1305) will provide some sort of streaming interface, with init, update, and finalize functions, where init starts the computation, update takes in some data and can be called repeatedly, and finalize finishes it. Libsodium's crypto_secretstream_* (documentation here) is a good example, but any library offering a streaming implementation should have something similar.


Post-quantum authenticated key exchange with forward secrecy

Key exchange and authentication are typically done by separate algorithms. However, there are post-quantum key exchange algorithms that also provide forward secrecy. For example:

SIDH - Supersingular Isogeny Diffie-Hellman is very similar to regular DH. The main difference is that the security is related to the problem of finding the isogeny mapping between two supersingular elliptic curves with the same number of points.1
NewHope - This algorithm is based off of ring-learning-with-errors (R-LWE). The security relies on the approximate shortest vector problem (α-SVP). This is the idea that finding a vector shorter than α times the shortest vector is difficult, even for quantum computers.

Both of these algorithms can be combined with traditional key exchange to form a hybrid that is secure against both quantum computers and cryptanalysis of the relatively newer post-quantum algorithms. Google for example has experimented with their CECPQ1 key exchange algorithm, which combines NewHope and x25519. The Tor Project is also working on a hybrid algorithm using the same primitives, though implemented differently (using NTor rather than TLS).

Neither of these schemes provide post-quantum cryptographic signatures. The reason for this is simply that a signature does not need to provide security for nearly as long as key exchange. Key exchange must be secure against an adversary who can store the handshake and encrypted message and decrypt it at a later time when technology is sufficiently advanced. Signatures on the other hand only require that they cannot be broken right now. If your adversary is an attacker who is storing encrypted connections to break in the future, there is no need to switch to PQ signature schemes. It's only if your adversary is an active attacker with a quantum computer at this very moment that you need to worry about more secure authentication.


Would it be better to split a file and then encrypt, or vice versa?

Either could be implemented securely, but if you encrypt first and split afterwards, you can use standard tools and get everything right more easily. If you used the opposite order, you would have several pitfalls to deal with:

With password-based encryption you would either have to derive the key many times (spending resources that would be better used on additional hashing) or have a separate key derivation step and then use the key on all the parts.
If you had a single key used multiple times, you would have to make sure IVs are unique, when with a single-use key you can forgo it completely.
To fully authenticate the encrypted file you would need to add some metadata or a whole-file MAC, instead of simply using authenticated encryption on each part. Otherwise an attacker could be able to drop or reorder the parts.
As a practical issue, if you are splitting to a certain target size, you would have to take into account the expansion caused by encryption IVs and authentication tags.


How can 3DES encryption use decryption in the middle step?

I do not understand how can we decrypt a cypher which was encrypted with $K_1$, with $K_2$.

Triple DES essentially involves three encryptions on the plain text. First is using $K_1$, second using $K_2$, and third using $K_3$. Now one may argue that $K_2$ is not being used for encryption but decryption. Well, technically speaking, encryption and decryption are just the same, and are only the reverse of each other in all ciphers using the feistel cipher structure. So actually decryption with $K_2$ does nothing but jumble-up the message further more. We are not decrypting the cipher in the real sense. We are adding another layer of obscurity with a second key.


Lamport signature: How many signatures are needed to forge a signature?

If the message is random each additional signature halves the security level. If the message is chosen by the attacker, two signatures (of messages where each bit differs) are enough for a complete break.

A security level of about 64 bits can be broken by a determined attacker, and a level of 32 bits can be trivially broken on a single home computer.

So if you use 256 pairs, which is a reasonable level, since it offers 256 bit security against second-preimage attacks, and 128 bits against collisions, practical attacks are possible once you use the same key three times, and it's trivial to find messages-signature pairs once you use it four times.

Note that at this point the attacker can't fully determine the message he wants to sign, he needs to try $2^{64}$ (after three sigs) or $2^{32}$ (after four sigs) different messages to find one that he can sign. This usually isn't a problem for the attacker, since many things he might want to sign have parts the attacker can choose freely.

Why does it halve after every signature?

When you observe a single signature, you know one hash from each pair. So to create a signature you need to have a message hash that matches every single bit of the signature.

When you observe two signatures, you know both hashes from half of the pairs, and only one hash from the other half. So the message hash only needs to match the half where you only know one.

When you observe three signatures, you know both hashes from 3/4 of the pairs, and only one hash from the remaining 1/4. Now you only need to match 1/4th of the original bits.

etc.


Should AES-CMAC key cryptoperiod be affected by MAC truncation to avoid birthday-attacks?

Yes, truncated MACs influence the cryptoperiod.

First of all, I cannot really think of any case where it makes sense to assume that the attacker only sees a truncation of the MAC if that isn't what is actually used in the system!
And if you actually truncate your MACs to 30 bits you will probably have collisions after $2^{15}$ message blocks. So you definitely need to reduce the cryptoperiod.

On the other hand you're saying an attacker can only see 30 bits of the MAC because you are truncating it. Let us assume that you are still using the full MAC and that this makes sense in your scenario for some reason.

This in itself doesn't change the attackers position significantly:

Exhaustively searching for the correct key becomes more complicated because now the given 30 bits of the MAC might match but it might still be the wrong key. However there are $2^{128}$ possible keys and by the birthday paradox a MAC collision will probably occur after about $2^{64}$ message block. So this is the more plausible target anyway.
When a collision occurs the attacker can now not readily detect it anymore because only parts of the MAC are visible to him. On the other hand it will potentially be easy to submit fake queries to validate potential collisions and the probability for a collision doesn't change when the attackers view is truncated.

So in this case it would be fine to keep the values but I would love to hear how this makes sense.


I'll only talk about things on a very high level here, probably much higher than what you already know and will use Matthew Green's blog post as the primary reference. Nevertheless the idea should come across.

So in that post, WOTS is described as a smart way to have more than two (0 and 1) lists of of secret key values to publish as the signature. Now what you do is that for each symbol (eg byte), you publish one entry from these lists (in a smart way). But if you do this twice for different message which differ in at least 2 bytes, you can take one byte from the one and one byte from the other signature to forge a new signature! Also note that (as far as I can tell), it's usually not assumed for this kind of signature scheme to mandate hashing the input and only passing the hash to the signature primitive.


Secure function evaluation for Boolean formulae

For log-depth circuits, it is possible to use an information-theoretic version of Yao's garbled circuits. Note that in a garbled gate, each key is used to encrypt twice. Thus, if the keys on the input wires are double the length of the keys on the output wires, then one-time pad encryption can be used and the result is information theoretically secure.

See the paper Gate Evaluation Secret Sharing and Secure One-Round Two-Party Computation by Vlad Kolesnikov, and references within.


Limit AES-256 to Alphanumeric characters

The standard way to do this is known as "ASCII armoring".

The idea is that, on encryption, you have the crypto (AES in your case) generate the ciphertext in binary, and then you convert that binary into the character set that is appropriate to you; you can convert it into hexadecimal, you can encode it into Base64, or you can use a more aggressive encoding with a larger character set.

Then, on decryption, you would take the ciphertext you receive, and convert it back into binary, and then hand that back to your decrypt for the rest of the decryption.

This procedure does make the ciphertext longer; doubling the size of you use hexadecimal; 33% longer if you use Base64; somewhat less if you use a more aggressive encoding.  However, it can be shown that this cannot weaken the cryptography.


Use exported certificate with private key to logon using Kerberos

Note: The below holds assuming Microsoft did things properly and following. But Microsoft being Microsoft they didn't. Smart-Card (certificate-based) logon is only supported when using Kerberos thanks to the custom Microsoft extension to Kerberos.

  So my question is, how can I feed my exported certificate into Kerberos?

Short Answer: You can't.
Long Answer: Technically, you can.

To understand this, we need to take two detours: Namely the answer to your first question and to Kerberos. Let's do Kerberos first.

So, Kerberos is a (complex) protocol that allows a client to authenticate with a (sequence of) central server(s) such that at the end the client's actual intended communication partner can be sure of the client's identity and has a shared key with them. All of this while only the client has to establish connections with the central server(s) and while the only pre-shared keys are between each party and the central server(s). Now, Kerberos relies entirely on symmetric cryptography, so from a protocol point of view authentication via asymmetric cryptography isn't (directly) an option. I'm rather confident that Windows also doesn't support this natively (short answer).

However, the answer to your question

  Is it possible to use custom credential provider in windows to log on, that accepts certificate, which I export from certificate store with private key.

is yes. There is software that allows you to log-in to local Windows installations using a smart card and it's a built-in ability if the authentication is handled by a domain controller. Note though that using an encrypted exported private key isn't a sensible authentication method on its own, as you would be back to username (identifiying the relevant keyfile) and password (decrypting it) and would have gained nothing.

If you have a smart card and use this smart card to decrypt a windows password, then you can use this decrypted password for Kerberos authentication. Doing the first part is possible, as demonstrated by the software which feeds the password to the standard Windows login facilities after decryption for local logon. Doing the latter shouldn't be too hard. Please note that implementing this is likely a lot of effort and only potentially worth it in an environment where you cannot possibly switch away from using Kerberos to use "normal" domain-controller-based public-key authentication. This is why the longer answer is "you can".


What is the difference between a bijective random oracle and a random permutation?

At some level, there is no essential difference.  Certainly, there is no difference in the distribution on the random variable $O$ vs $f$.

However, there is a potential difference in how the terms are typically used.

If we say that $O$ is a random (bijective) oracle, then we are usually implicitly hinting that it is available to everyone: the legitimate parties, the attacker, everyone -- anyone can supply an $x$ and get back $O(x)$.
In contrast, if we say that $f$ is a random permutation, we have not yet made any commitment about whether it is made available as an oracle to everyone, or whether it is closely held.

Hopefully the set of parties who have access to $O$/$f$ should be made clear elsewhere (e.g., in the formalization of security), so there is no real danger of serious confusion, but this might serve as a hint to let readers know what to expect.


ECDSA vs RSA: Performance on Android platform and surprising results

BouncyCastle has a really bad ECC implementation. It uses affine coordinates which incur a huge performance hit (factor 20 or so) since it computes a field inversion after every single step. Good implementations use Jacobi coordinates (or a similar approach) where denominators are kept and there is only one field inversion at the end.

It's also potentially vulnerable to side channel attacks since it branches on secret data (only relevant to signing, not verification).

As another ECC benchmark you could look at the the ref10 branch of str4d/ed25519-java. This uses a different elliptic curve, Ed25519, but the main difference is that the implementation has been optimized more than the one you tested. But this is still new and experimental code, so be careful.


What is the recommended replacement for MD5?

That depends on what you want to use the hash function for.

For signing documents, sha2 (e. g. sha512) is considered secure.

For storing passwords, you should use one of the algorithms dedicated for this purpose: e. g. bcrypt, sha512crypt or scrypt. In order to slow down an attacker, these algorithms apply the hash functions many times with an input that is based on the number of the current round.

Scrypt takes this concept one step further and uses a huge amount of memory. Typical hardware for password cracking has access to about a couple of KB of memory, the default configuration of scrypt requires 16 MB.


Making ECDSA public keys one bit shorter

I think your question can be reduced to the question whether there is a significant subset of weak public/private key pairs in any of the EC groups you mention. I am not aware of any such weakness, but if it exists, it would put a large dent in the security of Elliptic Curve Cryptography as a whole.

If there is no significant risk you will get a key pair with less than the expected security, if you generate it uniformly at random in accordance with the relevant standard, but without discarding key pairs that have a public key with unwanted properties, the risk will still be insignificant even if you discard on average every other randomly selected key pair based solely on properties of the public key. It is important to reiterate that this argument only holds if you do not modify the private key generation in any way, but only discard key pairs based solely on properties of the public key.

This argument is based on pure logic. If you get the expected security from each of 1000 uniformly generated key pairs, and the adversary sees the public key of each one of them, you get the expected security from each ~500 of those that have a public key with the property you want. If the latter had been false, clearly the former couldn't be true either. Reduction ad absurdum.


Is encrypt-and-MAC secure for AES-CTR + UMAC?

Encrypt-and-MAC does not preserve confidentiality because two encryptions of the same message will have the same mac tag, revealing the fact that the messages are equal.

Ssh includes a counter in the data the mac tag is computed over, so it never computes the mac tag for the same message twice (even if identical data is transmitted twice), so this particular weakness is not an issue.

This is not an endorsement of encrypt-and-MAC, however. Do not use it.

(If you have a strange MAC, encrypt-and-MAC can leak even more than equality, but few reasonable MACs are strange.)


How are new coins minted in Proof of Stake systems

In a purely Proof-Of-Stake cryptocurrency the number of coins is fixed
And so are most government back currencies.  Interest in Proof-Of-Stake seems to be driven by the rise of 51% attacks, Ethereum Classic has been attacked multiple times, which significantly drove down value.
Unless you're BitCoin, the network of miners is simply not big enough to protect your blockchain once your coins start getting valuable.  Each Ethereum coin is worth about $1,500, which is enticing for attackers.  You can hoard coins, spend thousands on a 51% attack and still come out ahead.
Because of repeated 51% attacks, Ethereum released Ethereum 2.0, which swapped from a Proof-Of-Work, like BitCoin, to Proof-Of-Stake.  There were already plenty of coins and a healthy user base, so not adding new coins wasn't that big a deal.
By switching to Proof-Of-Stake Ethereum 2.0 forces any attacker to put up coins they won't get back quickly.  51% attacks work by overwhelming the network for a short time and cashing out.  Now any attacker would have to control 51% of the network for a long time in order to cheat and get the Stake back.
But where do the Proof-of-Stake coins come from
Ethereum started as a Proof-of-Work cryptocurrency and swapped over to Proof-of-Stake to stop attacks.  Most of the Proof-Of-Stake cryptocurrencies started out as Proof-Of-Work then switched over to Proof-Of-Stake after they had plenty of coins to go around and a good eco-system of users.
Proof-Of-Stake is a way for smaller cryptocurrencies to protect their blockchains.  BitCoin doesn't have to worry as much about a 51% attack since it is the largest cryptocurrency by far.  For reference each BitCoin is worth 48,850 USD while each Ethereum coin is worth 1,500 USD.
How I figured this out
Reading and re-reading the Ethereum 2.0 website
This reddit thread ask a similar question, which lead me to this article.


If I am about to generate one-time pad, where should I generate my pads from?

/dev/urandom is only computationally secure, so you won't get information-theoretical security for your OTP if you draw it from /dev/urandom. If you're happy with computational security, you might as well use a stream cipher instead of a OTP. Stream ciphers are much easier to use securely than OTPs.

On Linux /dev/random aims for information-theoretical security, but in exchange you typically get pretty bad performance. How well it achieves that goal is practice is unclear, since it relies on entropy estimators for its entropy sources, and that's error prone. (I think on BSD /dev/random is equivalent to /dev/urandom because they don't care about information-theoretical security)


Is there a PRNG algorithm that allows to switch between states directly, not calling next()?

Probably the easiest one with regards to the protocol is a XOF, an eXtendable Output Function. Two have been defined as part of SHA-3, called SHAKE-128 and SHAKE-256. These have a single input of any length, and can output as many bytes as required.

Of course SHA-3 is relatively new, so not all runtimes / API's may support the SHAKE variants out of the box.

In your case you would feed it the 128 bit seed concatenated with the 64 bit state. There should be no need for two separate variables.


How to encode and decode message into polynomial form on NTRU

NTRU operates on the ring $R = \mathbb Z[x]/(X^N -1)$. Therefore all parameters must be lie in this polynomial ring.

1.Does the message length have to be smaller than or equal to the parameter N? Can I do encryption on a message larger than parameter N or do I have to break them up?

That really depends on the encoding. The linked example suggested using binary encoding. In this case, if ASCII is used then you can encode it with degree 7 polynomials. Therefore, if your $N =7$ then you cannot encrypt more than one ASCII character. You have to divide your message character by character to encrypt, assuming that you are using ASCII characters for your messages.
Other encodings are possible like ternary $\{-1,0,1\}$, however, for simplicity keep the binary at the beginning.

However, in this case, how do I decrypt the message given that the decrypted message would be the addition of all the polynomials? Or do I have to encrypt and decrypt each letter separately?

You have to encrypt each of them separately. Note that the example is not ternary encoding it is the binary encoding. Check them like this;
$$ \texttt{h 01101000} = \color{red}{1}\cdot X^6 + \color{red}{1}\cdot X^5 + \color{blue}{0}\cdot x^4  + \color{red}{1}\cdot X^3 + \color{blue}{0}\cdot x^2 + \color{blue}{0}\cdot x^1 + \color{blue}{0}\cdot x^0$$
In ternary, actually, one expects to see some $-1x^i$ at least in some of the encodings if one doesn't select all of them deliberately not including the $-1$.

The below is a sample SageMath code for encoding a character into a polynomial. The full code running with the NTRU encrypt/decrypt is at GitHub.
Zx.<x> = ZZ[]

def encodeASCIIToPolynomial(c):

    C = ord(c)
    M = 0
    i = 0
    while(C > 0):
        M = M + x^i*(C %2)
        C = C//2
        i += 1
    return M

def decodePolynomialToASCII(D):

    x =0
    for t in D:
        x = x + t
        x = x *2
    return x

message = 'Z'
print("Message to Encrypt            ", message)
m = encodeASCIIToPolynomial(message)
print("Message encoded to Polynomial ", m)
print("Decoding back to character     ",chr(decodePolynomialToASCII(m)))


RSA: Recover e given factorization of N and plaintext/ciphertext pair

If $e$ is a random number, then knowledge of the factorization allows us to reduce the recovery operation to:

$$(c \bmod p) = (m \bmod p)^{e \bmod p-1} \pmod p$$
$$(c \bmod q) = (m \bmod q)^{e \bmod q-1} \pmod q$$

Solving both these discrete log problems will give us enough information on $e$ to efficiently recover it.

Now, while solving these two subproblems is easier than factoring $N$, or recovering $e$ without knowing the factorization, it is still nontrivial.  If we assume that the RSA modulus was a 2048-bit key, then each of these subproblems is a 1024 bit discrete log problem; that's larger than any published result.

On the other hand, if we are allowed to assume that $e$ is small (but perhaps a bit larger than we can brute-force), there are more efficient methods than simply trying each possible $e$ value.  For example, using the Baby Step Giant Step algorithm, you can efficiently check all possible values $e < 2^{61}$ with $2^{31}$ modular multiplications, and a few tens of Gigabytes of disk space.  You don't even need to know the factorization of $n$ (however, it would make it a bit more efficient, as that would allow you to compute everything modulo $p$)


Can a monoalphabetic substitution cipher attain perfect secrecy?

Since this is homework, let me just give you a hint: consider the two-character messages $m_1 = \text{"aa"}$ and $m_2 = \text{"ab"}$.

Given a ciphertext $c$ encrypted with a monoalphabetic substitution cipher, can you tell which of $m_1$ or $m_2$ it corresponds to, even without knowing the key?  Why (not)?  What does this imply about perfect secrecy?

Ps. The hint I gave above assumes that the cipher is not homophonic, i.e. that the encryption of each character is deterministic and independent of its position or the presence of other characters in the message.  For a (possibly) homophonic monoalphabetic cipher, it may be simpler to start the argument from the other end: if you intercept the ciphertext $c = \text{"xx"}$, what can you say about the plaintext?


Ciphers that use S-boxes are typically in the form of a Feistel network. This has the property that inverting the cipher does not involve inverting the round function, but simply applying the rounds in the opposite order. Therefore one doesn't need to invert the S-box to decrypt.


Is ”generating transcripts that are indistinguishable from actual messages in a signature scheme” not universal forgery?

Here and in many other signature schemes, $f$ is modeled as a "random oracle."  This means that on each distinct input, $f$ outputs a uniformly random value in $\mathbb{Z}_q$ that is independent of all other outputs.  (When queried on the same input multiple times, it always returns the same answer.)

The trick here is that the simulator has the power to "program" the output $f(m,r)$ to be the value of $e$ that the simulator chose.  In the "real" world, an attacker cannot control the outputs of $f$ like the simulator can.

Many more details can be found in the classic Bellare and Rogaway paper "Random oracles are practical."


Can anyone explain why CBC-MAC is not secure for variable length message?

For the previous question I'll quote Matthew Green's post from 2013:

  A quick reminder. CBC-MAC is very similar to the classic CBC mode for
  encryption, with a few major differences. First, the Initialization
  Vector (IV) is a fixed value, usually zero. Second, CBC-MAC only
  outputs the last block of the ciphertext -- this single value forms
  the MAC.

  Many dumb implementations stop here. And that leads to big problems.

  Most notably, if your system allows for variable-length messages -- as
  it should -- there is a simple attack that allows you to forge new
  messages. First, get a MAC T on a message M1. Now XOR the tag T into
  the first block of some arbitrary second message M2, and get a MAC on
  the modified version of M2.

  The resulting tag $T'$ turns out to be a valid MAC for the combined
  message $(M1 || M2)$. This is a valid forgery, and in some cases can
  actually be useful.

  The standard fix to prepend the message length to the first block of
  the message before MACing it. But a surprisingly large number of
  (dumb) implementations skip this extra step. And many CBC-MAC
  implementations are dumb implementations.

(more info here)

  First question, why need to set $T′′=C0$?

Actually it is not set. $T''$ is computed as written in the slide and the result is $C_0$.

  Second question which is biggest question I don't understand, why $T′′′=T′′$. How to prove this relationship?
  Third question, why is $\text{new message}=P_0,P_1,(P_0⊕T′)$?

Let's compute the tag for $P'''$:
after processing second bloc ($P_1$) one have $T'$, so when processing next bloc ($P_0 \oplus T'$) one computes the encryption of $T' \oplus P_0 \oplus T' = P_O$ that is, by definition, the tag of the second message: $T''$ ($P_0$ is the second message $P''$).

Roughly the idea is to add a bloc that cancel all previous computations and restart the CBC-MAC computation for a message which MAC is already know by the attacker. "Canceling" is done by xoring to the first added bloc the tag of the previous chain to the first bloc of an other message which MAC is known.


How to decrypt a '.enc' file that has been encrypted with RSA using a public key?

openssl rsa -pubin -inform PEM -text -noout < public_key.pem
Public-Key: (64 bit)
Modulus: 16513720463601767803 (0xe52c8544a915157b)
Exponent: 65537 (0x10001)

The modulus is small enough that you can easily factor it

After finding the prime factors, you can calculate the private exponent

After you have the private exponent, you raise each 64-bit block of ciphertext to the private exponent mod the modulus.


Key and signature sizes of NTRU and NTRU Prime?

The inconsistency of Ntru public key size is due to the fact that those are from two different parameter sets (targeting different security levels). The latest version of recommended parameter sets can be found from
https://eprint.iacr.org/2015/708.pdf

Ntru prime does not have a signature scheme as far as I know.

NtruSign signature scheme is broken and is not recommended for use. The same group of people come up with a new scheme named pqNTRUsign which is secure against the transcript attack that breaks ntrusign.
https://eprint.iacr.org/2014/457.pdf

The reference implementation of both Ntru and pqntrusign can be found from
https://github.com/NTRUOpenSourceProject/ntru-crypto


How come Shamir Secret Sharing uses Lagrange interpolation?

The purpose of the reconstruction of the polynomial $P(x)$, is just to calculate the value of $P(0)$, which equals the shared secret value.

If Lagrange polynomials are used, a trivial optimization which cuts the number of multiplication nearly in half is
$$P(0) = (\prod_{i=0}^{n-1}{-x_i})\sum_{i=0}^{n-1}{{\frac{y_i}{-x_i (\prod_{j=0,j\neq i}^{n-1}{(x_i-x_j)})}}}.$$

If Newton polynomials are used, there is no trivial optimization because you only want to calculate $P(0)$, simply because the formula is already optimized to half of $n^2$. This means that the overhead of the recursion might outweigh the general benefits compare to the Lagrange formula.

If you had had to represent the polynomial $P(x)$ in order to calculate other values than just $P(0)$, Newton polynomials would in general have been more efficient.


anything obviously wrong with my custom password hash scheme?

I am hesitant to say that this is "okay" because it probably is from a strictly cryptographic point of view, because if I do you will stop reading and go with your solution. Some thoughts:

In the word "password" there's the word "word". Passwords are meant to be typed in by humans, therefore they must at least be printable, therefore ASCII control characters are to be avoided.

If you need automatic accounts to log in (legitimate "bots") then they should not have passwords, instead you should provide an authentication API with an access token and a secret key, that the bot can use to make API calls to do whatever it needs to do on your application. This is the industry standard and you would do well to follow it instead of creating ad-hoc binary password schemes.

Generally it is good practice to separate human users and automated scripts/bots, even if just for auditing purposes.

So, in short:

don't give automatic accounts passwords, give them API keys that can easily be tracked and revoked; bots are not humans, they do not behave like humans, and they cannot be treated as humans; treating them the same in your authentication logic is a severe category error;
do validate passwords entered by the user, and accept general UTF-8 characters, but reject obviously invalid characters (control characters), for anything else let users sort themselves out with the "forgot password" feature if they mess up;
in the future, don't work around ridiculous implementation bugs (such as your bcrypt function not accepting null bytes) by modifying your fundamental design and core application assumptions; fix your implementation instead!!


Would SHA-1 be safe for certificates with short validity?

The short answer is that no, the length of validity would not help in a major way.

First you have to consider how the attack on the collision resistance of SHA-1 applies to certificates. The idea, and how it actually worked in the case of MD5, is basically:

Attacker finds a collision in the hash function that generates two certificates with the same hash.
They give1 the innocent one to a CA for signing.
Now they also have a signature for the malicious one, that e.g. allows them to claim to be Google.

A validity period of months would still allow them to make use of it for months. That may be less of a return for the attacker's resources than using it for years, but you would expect such an attack to eventually be exposed anyway. And if, like poncho mentions in the comment, the attacker can generate a malicious certificate with a different period of validity, then even that is not an issue.

Now, if you think that in the next year or so no-one will be able to generate a collision due to the expense or time it takes, then you can argue that certificates should be allowed for an extra year. However, the validity period itself does not really matter in this case.

1 Actually, the CA typically generates the certificate and the attacker must predict how and choose the information they give.


Why does OAEP have 2 rounds with 2 random oracles?

This variant of OAEP would be malleable if the underlying trapdoor permutation is malleable, and hence would not be chosen-ciphertext secure.  This is a major theoretical weakness, as I explain below, and one that may lead to attacks in practice.

In more detail, suppose $G$ is the (lone) hash function and $f$ is trapdoor permutation used, so the formula for the encryption algorithm of this variant of OAEP is
$$f(m\oplus G(r)\|r).$$
Suppose you have are given the output of the encryption algorithm (call it $y$) for some unknown message $m$.  If $f$ is malleable, it may be feasible to come up with $y'$ that is an encryption of $m$ with a bit flipped, meaning $$y' = f(m'\oplus G(r)\|r)$$ for $m'$ equal to $m$ with a bit flipped.  If one obtains a decryption of $y'$ (as is allowed in a chosen-ciphertext attack) then one learns $m'$ and hence $m$.

The extra round of OAEP is to ensure that such ciphertexts decrypt to unrelated messages that do not help an attacker.  You may want to look at SAEP and SAEP+ [1] for some more results on one-round variants of OAEP that are secure.

[1] D. Boneh.  Simplified OAEP for the RSA and Rabin functions. In proceedings of Crypto '2001, Lecture Notes in Computer Science, Vol. 2139, Springer-Verlag, pp. 275-291, 2001


Constructing secure key exchange protocol

Well, the obvious way to do this is:

Before the protocol occurs, Alice runs the $Gen$ procedure to create a public and a private key
For her round, Alice sends her public key to Bob
For his round, Bob selects a random symmetric key $\in \{0,1\}^n$, encrypts it with Alice's public key, and sends that encryption to Alice.
Alice decrypts the message that Bob sent her with her private key.

Now, Alice and Bob share a random symmetric key (Bob knows it because he created it, Alice knows it because she decrypted it).  In addition, Eve has no information on the key; the only thing that could possibly give her information about it is the encrypted version in round 2; and because we assume $\Pi$ is semantically secure, that gives her no information.


Is it possible to make time-locked encrytion algorithm?

Cryptographic algorithms are not time-aware, so you require a time-aware third-party to accomplish this. The third-party also needs access to a secure time source (like an on-site atomic clock or a secure connection to an offshore one)

The precise implementation and protocol depends on your usecase, but as an example you could have a server that does two things:

accepts inputs that include a message to timelock and a "release date"
allows requests to obtain the message only once the message's release date is passed

For the first case, the server would generate a random symmetric key of sufficient length, encrypt the message with it, hash the encrypted message and add the key + the hash + the release date in some database. The server then returns the hash that serves as an identifier for the message that was just timelocked. It can also return the encrypted message, if needed (presumably, the entity submitting the message destroys his plaintext copy after as he is the one wishing to timelock it).

Then, in the second case, the client sends the identifier to the server. The server looks it up, and checks the release date. If it isn't passed yet, the server denies and bails, however if it is, the server simply returns the correct encryption key (and the plaintext message if desired).

That's just one example of a very basic timelock service (you can elaborate by using public-key crypto to enhance various aspects of the service, for instance).

Your question is quite broad, perhaps you should add more detail.


DES — Can I recover the key when I have both ciphertext and the plaintext?

Efficiently - no. However, the best attack on DES - linear cryptanalysis - works with known plaintexts, and theoretically may work slightly faster than the brute force even for small amounts of data.

Computing linear relations between plaintext $P$ and ciphertext $C$, an attacker is able to enumerate all keys according to their likelihood. The PhD thesis by Junod provides a comprehensive description of the attack for various parameters in Sections 3.1, 3.2. There is a formula of the probability that the correct key is found among the $r$ candidates with the highest score after analysis of $\nu$ (plaintext,ciphertext) pairs. Given only few ciphertexts, all the keys will have almost the same likelihood, and $r$ must be very close to $2^{56}$ to provide the success rate close to 1. Still, the resulting attack must be faster than the brute force, even though only marginally.


Binary format of encrypted PGP private key?

PGP key formats are defined in RFC 4880. Specifically, section 5.5.

The private key format includes the public key and quite a bit of other information in unencrypted form. It might be easier to add another layer of encryption on top of that before you use steganography.


There are a bunch of issues involved with this question; the bottom line is that it while it wouldn't be a bad approach from a cryptographical standpoint, it appears to be more costly than the standard approach.

Let us first examine the number theory issues: the first question to ask is "does $g$ generate a large prime subgroup of $Z/p$?". That is, does $g^x \bmod p$ take on a prime number of distinct values (depending on $x$), and that prime number is fairly large?  If that's not true, you need to change your values of $p$ and $g$ so that it is true.  If you need a suggestion about what group to use, I always point people here; this gives a number of precomputed groups that are well designed.

Now the good news: as long as you're working in a prime subgroup, it doesn't matter which generator you're using; all elements of the subgroup (other than 1) generate the entire subgroup and (here's the best part) none are weaker as far as Diffie-Hellman is concerned.  To be more precise; if someone can solve the computational Diffie-Hellman problem with a generator $h$ (that is, given $h^a$ and $h^b$, compute $h^{ab}$), then he can solve the Diffie-Hellman problem with generator $g$; hence if $h$ is weak, then $g$ turns out to be weak as well.

Now, let us examine another issue: why are you rekeying in the first place?  What security properties do you hope hold for the new keys?  Do you hope to get Perfect Forward Secrecy (PFS, that is, if someone happens to get hold of the entire cryptographical state on one of the two sides at some point, they are still unable to obtain the new keys)?

If you are changing keys simply because that's good cryptographical practice (and don't care about PFS), there are a number of ways to do this securely.  We generally don't bother recomputing a public key operation (which is expensive); instead, what we generally do is use a Key Derivation Function to convert the DH shared secret (and some public nonces exchanged by the two parties) into the actual keying material we use; when we want to change keys, we just rerun the Key Derivation function with different nonces (possibly exchanged that that time); and we have new keys which are cryptographically unrelated to the previous keys.

On the other hand, if we want to get PFS, the recomputing the Key Derivation Function doesn't work (because an attacker with the previous state can do that as well); to do that, we generally do another DH exchange; that gives us PFS because we select new secret exponents at the time of the exchange; someone learning the state previous to that doesn't learn the secret exponents, and hence cannot learn the new keys).

We might consider doing a virtual DH exchange with another generator; the issue is "where does $h$ come from, and do we know the value $x$ such that $h = g^x$?  Note that they may appear to be a Discrete Log problem, however we may know the value $x$ by selecting that first, and then computing $h = g^x$.

If we know such the value $x$, then both sides can compute ${(g^{ab})}^x = h^{ab}$.  However, if both sides can compute it, so can the attacker (who learns the previous cryptographical state), and so you don't achieve PFS.  If you don't need PFS, this works, however rerunning a Key Derivation Function is rather cheaper than doing another modular exponentiation.

If we don't know such a value $x$, then both sides would need to compute $h^a$, $h^b$ and exchange them; effectively doing another Diffie-Hellman operation.  However, in contrast to an independent Diffie-Hellman operation, both sides must retain their $a$, $b$ values; and so an attacker learning the cryptographical state would learn one of those values, and so you don't achieve PFS.  Now, you could have the two sides discard their $a$, $b$ values, and select new ones; at this point, you're doing the traditional Diffie-Hellman, except you're changing generators; that isn't harmful, but doesn't appear to gain you any benefits either.

So, the bottom line is that if you need Perfect Forward Secrecy, your proposal doesn't do it; if you don't need Perfect Forward Secrecy, there are cheaper ways to do it.


Two diferents inputs can have the same output in $Shake256$ for every output size (for example, $Shake256(input_1, \ell) = Shake256(input_2,\ell)$ for every $\ell$)?

Yes, it is possible.  In fact, it is inevitable that some such pair $input_1, input_2$ exists.
Shake256 maps the input into a 1600 bit state, and then converts this state into an arbitrarily long sequence.  If two different inputs map to the same state, then they're produce the same sequence (independent of how much output you ask for).
In particular, if we consider all 1601 bit inputs, there must be (by the pigeon hole principle) two different inputs that map to the same state; that observation gives us an upper bound on the required size of $input_1, input_2$.  Almost certainly much smaller pairs exist.
Now, finding such a pair, well, that's a different (and far more difficult) problem...


implementing long term archive encryption

The AES solution will fail if either:

the secret key is leaked, or
AES-256 is broken.

The RSA+AES solution will fail if either of the above happens, or if:

RSA-4096 is broken.

Thus, even without considering the relative likelihoods of these events occurring within the next 30 years, it is clear that the AES-only solution cannot be any less secure than the RSA+AES one.

Of course, the RSA+AES solution has the practical advantage that the system performing the bulk of the work (AES encryption of data) need not know your secret RSA key (although they will, of course, still need access to the AES key used to actually encrypt the data, not to mention the data itself).  You will need to decide for yourself whether this extra feature outweighs the risk of complicating your system by introducing an extra point of potential failure.


"Security" of SHA functions (Wikipedia), what does it mean?

Security in the table refers to collision resistance. By the birthday problem, there's a generic attack that finds collisions in any compressing function by choosing $\sqrt{2^m}$ random inputs ($m/2$ security bits), where $m$ is the output length.

Depending on the application, weaker requirements might be sufficient, such as second pre-image resistance or even one-wayness. A generic attack against the two weaker notions requires about $2^m$ work ($m$ security bits).


Security of Paillier against chosen ciphertext attack

Is it yet proofed that Paillier is secure against chosen-ciphertext attack. The original Paillier paper mentions that it is not.

It is indeed not - CCA security is incompatible with the property of partially homomorphic encryption.
If we have a ciphertext $C$ and an Oracle that will decrypt any ciphertext (other than $C$), what an attacker can do to decrypt $C$ is generate the encryption of $0$ (which is presumably not the ciphertext value $1$), and homomorphically add that to $C$, generating the ciphertext $C'$, and hand $C'$ to the decryption oracle.  As long as the encryption of $0$ is not $1$, then $C \ne C'$, and so the decryption oracle will have us the plaintext corresponding to $C'$, which will be exactly the same value as the plaintext of $C$ - the attacker wins.


Could a C25519/ED25519 cryptographic module be FIPS certified?

Likely yes in the near future—although ‘near’ is measured relative to the pace of a US federal government bureaucracy.

On 2019-10-31, NIST submitted a request for comments to the Federal Register on drafts for FIPS 186-5 and NIST SP 800-186 that include the Montgomery and Edwards curve shapes; the particular curves Curve25519, Curve448, edwards25519, and edwards448; and the EdDSA signature scheme instantiated with them, as defined in RFC 7748 and RFC 8032.  Comments are due by 2020-01-20.

(The updates do not cover the X25519/X448 DH functions, but NIST's late 2017 announcement of the upcoming changes also mentioned future updates to NIST SP 800-56A, which covers key agreement.)


Are SSL modes with forward secrecy vulnerable to the BEAST attack?

BEAST is not affected at all if the keys are derived with Perfect Forward Secrecy.  If you were to derive fresh keys quite frequently (that is, issue a Change Cipher Suite every couple of TCP segments), that would frustrate BEAST, however it wouldn't matter if the new ciphersuite used PFS or not.  In addition, there are cheaper ways to foil BEAST.

What PFS means for SSL is that, after we are done with the session keys, no one can rederive what they were, even if they have access to all the long term keys (e.g. the RSA private key, if that were involved).  The normal SSL ciphersuites do not provide this, as someone who has the recorded the negotiation and has the RSA private key can decrypt the premaster secret, and from there rederive all the keys.

However, with PFS, once we've derived the session keys, they are handled just like session keys from nonPFS ciphersuites; the keys are used to encrypt/decrypt traffic, and they aren't changed between TLS records (unless, of course, another Change Cipher Suite record is issued).

Hence, while this "no one can recover the session keys" property may be useful, it has nothing to do with BEAST.  BEAST does not attempt to rederive keys at all.  Instead, it tries to use the CBC-mode encryption as an Oracle (and then by injecting plaintexts that the attacker picks, confirms guesses on what earlier plaintext might have been).  It does care that the keys used to encrypt this latter data was the same as the keys used to encrypt the earlier plaintext; however it doesn't care how the joint keys were created.


Why doesn't this replay attack work on ECDSA?

You got tripped up by the fact that there are two different group operations in play here, and they don't play nice with each other.  This is implicit in the notation, and it's easy to get tripped up, because the notation expresses both operations in the same way -- but they are not the same.  This is arguably a pitfall in the notation: the assumption is that the reader will be careful to keep track of which operation is which and not get tripped up, but as you have seen, it is easy to lose track and be led astray.

When we write $kG$, we are referring to a group operation in the elliptic curve.  $kG$ is short-hand for $G+G+G+\dots +G$, where here $+$ represents the elliptic curve point-addition operation (it takes two points on the curve and "adds" them, returning another point on the curve).

When we write $rx$, we are referring to a group addition for the integers modulo $n$.  It is short-hand for multiplying the two integers $r$ and $x$ and reducing the result modulo $n$.  Note that this operation acts, not on two elliptic curve points, but rather on two integers modulo $n$.  It is a totally different operation.

With that understanding, here's where you went wrong.  You wanted to write something like $k^{-1} r = k^{-1} (kG) = (k^{-1} k)G=G$.  However, that derivation is simply wrong, because it mixes up the two different kind of operations.  $kG$ is an elliptic curve operation, so the result is a point.  Actually, $r$ is not $kG$; it is an integer given by the x-coordinate of $kG$.  This is essential, because when we write $k^{-1} r$ (or $k^{-1} (kG)_x$), we are multiplying two integers using the group operation for integers -- not the elliptic curve group operation.

Even if you adjusted the derivation to $k^{-1} r = k^{-1} (kG)_x = (k^{-1} k)G=G$, it would still be wrong, because of the difference between the elliptic curve point $H$ and its x-coordinate $H_x$; the former is a point on the curve, while the latter is an integer.  Different addition/multiplication operations apply to these two different kind of mathematical objects, and they don't cancel each other out.

In fact, in some sense the security of ECDSA relies upon the fact that these two different kinds of operations don't cancel each other and don't play nice with each other.  So buried in your question is an insight about elliptic curve cryptography that is pretty fundamental to the whole concept.


Indeed, this is a threshold issue, but the real threshold is $2^{32}$, not $2^{36}$ as documented. You can verify this with the following test:
SetVerbose("FFLog", 2);
repeat p := 2 * (2^32-5) * RandomPrime(10) + 1; until IsPrime(p);
Log(PrimitiveElement(GF(p)), PrimitiveElement(GF(p))^Random(p));
repeat p := 2 * (2^32+15) * RandomPrime(10) + 1; until IsPrime(p);
Log(PrimitiveElement(GF(p)), PrimitiveElement(GF(p))^Random(p));

Unfortunately there does not appear to be a way to call Pohlig-Hellman directly, or at least disable index calculus.


Security properties and Cryptography objectives applied in algorithms

AES or DES/TripleDES are just primitives. These primitives aide in building the properties of the system you were describing. The 5 properties are that of the system but not a single algorithm. We need a combination of crypto algorithms sometimes to achieve these properties in certain setup.

Few examples,

Confidentiality of data-in-transit in a "communication system" is achieved by SSL protocol using combination of symmetric (AES) and asymmetric (RSA etc.) crypto algorithms.
Integrity of data-at-rest in a "storage system" is achieved by Hash algorithms
Availability of data could be ensured by having good key management systems, to avoid loss/compromise keys which could make data un-available. Ofcourse there are variety of other high available and fault tolerant designs too with crypto primitives.
Authorization & Authentication protocols like Kerberos are built using symmetric algos again. More modern access controls could be built using Attribute based encryption etc.
Provenance in a cloud storage system is through, "Proofs-of-Storage". Provenance in a cloud compute system is through, "Proofs-of-work". Non-Repudiation in communication protocols are built using digital signatures which in turn could use AES/3-DES internally.

These primitives like AES/DES etc. aide in building much complex security systems. The security properties described are that of the systems but not necessarily the primitives.


How to break a columnar transposition cipher?

(Although your question is for a long time ago) Transposition ciphers don't change the frequency of letters in their ciphertexts. So, you can implement a frequency attack. For decryption by this you only need the table of frequency of English letters and your ciphertext.
(Your encryption scheme here is a Columnar transposition with a key that all its letters are in order except 2 of them.)


Why does WOTS+ need a checksum during signing operation?

To understand why we need a "checksum", we can take a look all the way back to 1979 paper "A Certified Digital Signature" by Raphle Merkle.

From page 14 on the treatment of the Lamport-Diffie OTS:

  The method as described thus far suffers from the defect that B can alter m by changing bits that are 1's into 0's. ... However, 0's cannot be changed to 1's.

This is because, if one changes 1 to 0, she/he can simply calculate the image of the hash for that bit and get another valid signature.

The countermeasure as proposed was, quote:

  by signing a new message m', which is exactly twice as long as m and is computed by concatenating m with the bitwise complement of m.

The similar method was used in WOTS, except instead of concatenating m with its bitwise complement, it's concatenated with the "additive" complement of the sum of its indicies.

So this is more like a padding scheme (similar in purpose to that used in RSA), but since it's a number, we'll just call it a checksum.

As to the update in OP, the checksum also plays an important role in the provable security reduction of WOTS.


How to prevent accidental nonce reuse with AEAD cipher

If you are having a sequential conversation, like TLS where each record is sent in order before sending the next record, you should use message sequence numbers for the nonce.  These will never overflow in ChaCha even if you managed to send one message per nanosecond for four centuries.  As a bonus, you can reject replays and force the attacker to keep up with your conversation, and you can immediately detect incorrect implementations that use nonces insecurely, e.g. because they randomized it or rolled it back.
If, for some reason, you are using a single key for (say) thousands of conversations in parallel, you can carve up the nonce into smaller pieces and assign to each conversation a unique (say) 16-bit number and then use 48-bit message sequence numbers for the rest, which is still a lot of messages, or 32-bit/32-bit, etc.
But if you're not restricted to using the same key—and it seems unlikely that you are, since you get to dictate how the key is used—then you can derive subkeys from a master key with a key derivation function, KDF, such as HKDF-SHA256, in what is sometimes called a cascade.  In fact, this is exactly how XSalsa20 and XChaCha work, using Salsa20/ChaCha itself as a KDF!  (Note: KDF does not just mean password hash; KDFs can be extremely cheap to compute—no costlier than generating a single block of output with ChaCha, for instance!)

For example, if you have a master key $k$ for your application, and many uniquely labelled instances of it, you can use $k_i := \operatorname{HKDF-Expand}_k(L_i)$, where $L_i$ is a unique label called the ‘info’ for the $i^{\mathit{th}}$ instance or purpose.  If you don't have HKDF logic handy, but you do have HMAC, it's easy to implement HKDF in terms of HMAC.

In a pinch, if you need a randomized system, you could just choose a sufficiently long info label at random, say 256 bits, and there will be no danger of collision (unless there's a VM rollback, etc.).  You could also include a time stamp, counter, favorite color, process id, phase of the moon, or anything else you want in the HKDF info string, as long as you can reason yourself into confidence that it will be unique.

Caveats:  In some cryptosystems like AES, there's a high cost to changing keys, and for 128-bit keys, subkey derivation is safe only for a modest number of keys, which is part of why I advise against AES and particularly against AES-128.  But there is zero key setup cost in Salsa20 and ChaCha, and the danger of collision in 256-bit keys is negligible no matter how many subkeys you derive within humanity's capacity for computation.
You may also have the option of generating and storing additional keys, possibly encrypted with a master key, or with a master key pair to separate concerns, or using a deterministic authenticated cipher.  But this is getting a bit far afield of the original already broad question.

(Technical details ahead, not necessary for the principal conclusion above.)

A note on XSalsa20 and XChaCha: If you have a library that computes Salsa20 or ChaCha for arbitrary nonce and block counter, you can easily compute XSalsa20 or XChaCha!

XSalsa20 and XChaCha are defined as follows: for 128-bit $n$ and 64-bit $n'$, the stream $\operatorname{XSalsa20}_k(n \mathbin\| n')$ with 192-bit nonce $n \mathbin\| n'$ is the stream $\operatorname{Salsa20}_{k'}(n')$ where $k' = \operatorname{HSalsa20}_k(n)$, and $\operatorname{HSalsa20}_k(n)$ is defined as a function of the Salsa20 core which is also used to generate the Salsa20 stream.

Specifically, the Salsa20 core $\operatorname{Salsa20}(k, i, \sigma)$ combines a 256-bit/8-word key $k = (k_0, k_1, \dots, k_7)$, a 128-bit/4-word input $i = (i_0, i_1, i_2, i_3)$ (which, for the stream cipher, is composed of a nonce and a block counter), and a 128-bit/4-word constant $\sigma = (\sigma_0, \sigma_1, \sigma_2, \sigma_3)$ into a matrix $$x = \begin{pmatrix} \sigma_0 & k_0 & k_1 & k_2 \\ k_3 & \sigma_1 & i_0 & i_1 \\ i_2 & i_3 & \sigma_2 & k_4 \\ k_5 & k_6 & k_7 & \sigma_3 \end{pmatrix},$$ and returns the 512-bit/16-word string $$\operatorname{Salsa20}(k, i, \sigma) = \pi(x) + x$$ where $\pi$ is a permutation.  HSalsa20, in contrast, computes $$x' = \pi(x) + x - \begin{pmatrix} \sigma_0 & 0 & 0 & 0 \\ 0 & \sigma_1 & i_0 & i_1 \\ i_2 & i_3 & \sigma_2 & 0 \\ 0 & 0 & 0 & \sigma_3 \end{pmatrix},$$ and returns only the 256-bit/8-word string $(x'_{00}, x'_{11}, x'_{12}, x'_{13}, x'_{20}, x'_{21}, x'_{22}, x'_{33})$.  (The indexing is a little different for ChaCha, as is the permutation $\pi$, but that's all.)  Effectively, this is simply returning half the words of just the permutation $\pi(x)$, skipping the additions that Salsa20 does at the end, but the difference between those words of HSalsa20 and those words of Salsa20 depends only on the public nonce $n$ and the public constant $\sigma$ so that breaking HSalsa20 can't be easier than breaking Salsa20.

What this means is if you have a way to generate a single block of output with the Salsa20 or ChaCha stream cipher using a prescribed nonce and block counter, then you can compute HSalsa20 or HChaCha by just subtracting off the nonce/counter and constants to derive an XSalsa20/XChaCha subkey, and from there use your Salsa20/ChaCha code to compute the rest of XSalsa20/XChaCha.


Would that scheme be sound to implement ? Are there any flaws that would make it foolish ?

I believe it's sound.

Note that SRP is a proven authentication protocol that has similar security characteristics. It has more round-trips, though.

  I guess the most important thing to consider here is whether the salt generation is "random enough" to accommodate even the worst case (everyone has the same password)

A 256-bit random number is a good salt. It will never collide with another 256-bit random number anywhere, unless your RNG is broken. But a random salt is not enough.

If an attacker ever sees a signed challenge or gets the public key from the database, they can brute force the password that generates a matching key-pair. Therefore, the KDF should be a strong password based KDF, e.g. PBKDF2 with a high iteration count, or perhaps scrypt.

I used something similar in a (non-public) project. There the salt was generated by the server (because I wasn't sure clients had entropy), so it could even check that it didn't collide with any current salts. I used Ed25519 as the public key system; key generation from a seed is trivial for it.


What is difference between Yao's "Garbled Circuit" and ther "Garbling Scheme" given by Bellare et al?

Yao's garbled circuits is a generic protocol for two-party computation, which uses garbled Boolean gates along with oblivious transfer in a specific two-round protocol with a generator and an evaluator. Bellare, Hoang, and Rogaway's paper proposes a security model for garbling schemes themselves (i.e. the operation performed on individual gates in Yao's protocol) along with some constructions of garbling schemes.

Yao's protocol can be generalized to multiple parties, but those settings are usually better served by a protocol that generically supports many parties, such as GMW.


The question's code works for AES-128 and AES-256, but indeed does not for AES-192, for the reason pointed in the question.

Yes changing if ( !( i % 36 ) ) into if((!(i%36)) && (key_words == 4)) as suggested in comment by the OP is enough to make it (and the rest of the code) pass the example of appendix A.2 and C.2 of FIPS 197 (as well as A.1, A.3, C.1, C.3).

Reminds me of the book Security for Computer Networks by D.W. Davies (not the same Davies) and W.L. Price (May 1987 edition), which has a typo in the last constant for S4 of DES, causing failures for some test vectors. That drove me nuts for a while in the late 1980s. From that point on I implemented crypto on the basis of the standards.


With public-key crytography, is private-key crytography still useful?

Can anybody let me know when private-key crytography is useful in practice?

Symmetric techniques tend to be significantly faster than asymmetric techniques. Encrypting data with AES and an appropriate mode of operation can yield throughput that is magnitudes of order greater than what the fastest implementations of RSA could possibly deliver. This difference is so great that encrypting any sizable amount of information with only RSA would take a prohibitive amount of time and be unusable in practice.

So symmetric cryptography techniques are useful pretty much everywhere in practice, from encryption of bulk data at rest (e.g. full-disk encryption) to encryption of data in transit (e.g. TLS)

  If so, can it be replaced with public-key cryptography?

You could simply use asymmetric cryptography for everything. But there are much more intelligent ways to do things.

You can, for example, generate a regular symmetric encryption key and use that to encrypt your data quickly, and then use public-key encryption to secure the key. This nets the following advantages:

You can use a new secret key per encrypted message
But you only have to manage long-term control of a single private key, instead of $N$ secret keys for $N$ messages.

This highlights what Public-key cryptography is really good at: Key management.

Using public-key encryption to directly encrypt bulk data won't work out well in practice, because that's arguably not what the tool is supposed to be used for.


RSA by hand - did I do something wrong? (c = m on encryption)

In fact, your calculating is right. The problem is:

At first, $e=13=5\pmod 8$.

Next, $d=5=e$ since $d\cdot e=1\pmod 8$. This means that the decryption key is identical to the encryption key. You should avoid this of course.

Third, $7^{13}=7^5=(7^2)\cdot(7^2)\cdot 7\pmod{15}=(4\cdot 4)\cdot 7\pmod{15}=7\pmod{15}$. This is why your decryption outputs the same as the input. If you try another message, you may find that the cihertext is different to the plaintext.


How is Shamir's Secret Sharing better than this simple 2-password technique?

You've described an $n$-of-$n$ threshold encryption scheme by nesting: there are $n$ shares of a secret key, and it takes all $n$ of them (in the right order, so I hope you labeled them) to recover the plaintext.  Similarly, there's a simple $1$-of-$n$ threshold encryption scheme by concatenation, which is what, e.g., OpenPGP uses for multiple-recipient messages.

What neither of these handles is $k$-of-$n$ for $1 < k < n$; e.g., $2$-of-$3$, where you want to ensure that either

you and your solicitor, or
you and your mistress, or
your mistress and your solicitor,

can collaborate to recover the secret, but none of them individually can (and definitely not your husband).

Obviously, it is possible to compose nesting and concatenation to have the same effect—do $1$-of-$3$ where each share is a $2$-of-$2$ threshold system itself, for instance, like the list above—but there is a bit of a combinatorial explosion of overhead this way especially when $k \approx n/2$ so that the overhead grows as the central binomial coefficients.

In contrast, Shamir's secret-sharing scheme costs only $\log_2 n + b$ bits per share of a $b$-bit secret no matter what the threshold $k$ is, for a total of $n \log_2 n + n b$ bits of overhead, or $k \log_2 n + k b$ bits of storage to recover the secret.

Note that secret-sharing schemes are almost never what you want in practice (except, perhaps, for revealing deathbed secrets).

For example, if you jointly control a bank account, and you want to ensure any transfers out of the bank account are authorized by two of three signatories, it is a bad system to use a single signing key split up with a secret-sharing scheme—if you do that, then every time you sign a check, you necessarily reconstitute the single signing key, and whoever owns the computer on which you reconstituted it now has unilateral power to sign checks.

It is generally better to use threshold signatures, the simplest system of which is just the concatenation of signatures by distinct authorized parties.


Some Questions about the Veracrypt hash functions

These hash functions are also used for the key derivation function. Both are roughly equally secure for a KDF in the sense of collision resistance etc., but SHA512 offers a bit more security as countermeasure for custom hardware attacks, since the memory requirements are a higher than for SHA256 and custom hardware to crack the passwords like FPGAs is more expensive. So there is a small advantage using SHA512, even if the output is truncated at the end.
Although I can’t explain VeraCrypt’s selection of hash algorithms, it is not a bad idea to offer a variety of functions as a countermeasure to custom hardware attacks with ASICs, as these chips must be produced for each algorithm. This could also be a reason for using different SHA variants.
I agree with you, that Argon2, scrypt, bcrypt would be better than PBKDF2, which remains vulnerable to custom hardware attacks even at high iterations.
But VeraCrypt took the poor design of TrueCrypt, where all possible combinations of key derivation are tested in a trial and error process (see chapter 3 of VeraCrypt encryption scheme). This limits the amount of time for all key derivation functions (see Bill Cox's Responses). So if it would test PBKDF2, Argon2 and scrypt in sequence, the latency would increase drastically.
I don’t know if or why VeraCrypt is GPU resistant. hashcat supports GPUs to crack VeraCrypt volumes, but I don’t know anything about the performance.


Is there a cryptographic primitive that allows "signature chaining"?

Assuming that the number $i$ of signature operations that an attacker can perform is bounded to $i<\sqrt(n)$ (i.e. the birthday bound), is there a way to construct any signature scheme $S'$ that makes an existential forgery harder than $O(n)$ for an attacker, given the constraints on the atomic input into the asymmetric signature function?

It would appear that we can do better than that, assuming a bound on the number of valid signatures that can be generated.

Here's is one possible approach; we apply a randomized hash that converts the message into 5 different 64 bit values (perhaps the signer selects a random value and then hashes that value along with the message using SHAKE-256, squeezing out $5\cdot 64$ bits); then, you sign each 64 bit value using the asymmetric function.  Then, for the signature, you publish the random value and the 5 signatures.

To generate a forgery (assuming that the attacker cannot attack the 64 bit signature operation directly), the attacker would need to find a different randomizer/message pair that hashed to values that has already been signed (and so he can put together the signature using values he has already seen).

If we assume that the valid signer will sign no more than $2^{32}$ messages, that means that the attacker has (at most) $5 \cdot 2^{32} < 2^{35}$ 64-bits values for which he has the signature.  Then, for any randomizer/message pair he selects, he hashes it; if we treat the hash as a random Oracle, then that produces 5 random 64 bit values, without the attacker having any control of those values before he hashes them.  Each value has, at most, a probability of $<2^{35-64} = 2^{-29}$ of being a value he has a signature for.  To create a valid forgery, all 5 values need to be values he has signatures for, and so the total probability of success (for each trial) is no more that $2^{-145}$.  Hence, the expected number of trials the attacker needs to do before he is successful is $2^{145}$, which is considerably better than what you asked.


How to prove truncated MD (or chop MD) hash function is collision resistant?

How to prove a chop(H) is collision resistant with n-bit?

Is this statement true?  Is it true that all collision resistant hash functions remain collision resistant after chopping?

As a hint, you might want to consider this question.


Are quantum preimage attacks on hash-based random oracles serious for lattice signatures?

Yes, it is important.  In a lattice-based Fiat-Shamir signature scheme, the signature is (z,c) where z is a low-norm vector and c is a low-norm challenge.

The verification equation then satisfies c=H(Az-tc,m) where A and t are the public key (A is a matrix and t is a vector) and m is the message.  If the Adversary is able to find an m' such that c=H(Az-tc,m'), then (z,c) is also a signature for m'.  Thus having 128-bit classical pre-image resistance is not enough.


Generating secure hash using iPhone Secure Enclave

You can simply create a database / enclave specific (symmetric) key and encrypt that using Enclave key pair. You can retrieve that wrapped key back by decrypting.

The password-derived key can simply be calculated like you do now.

So all that is left is to combine the keys back to one single key that depends on both. You could simply XOR the keys together for that. Or you could concatenate them and then use a KBKDF (which, in the simplest form, could just be a hash algorithm) to derive a new data key.

You could also concatenate the salt and the unwrapped key together and use that as salt input. Such a combination is called salt-and-pepper, where pepper is the secret part of the input. That way the derived key depends both on the secret and the password.

The derived data key can then be used to protect the database.

Don't forget to add authentication if you don't want the database to get corrupted by an attacker.


How can I store a combination of multiple pass phrases?

If you are asking "how can the server verify that the password (or passwords in your case) that the user enters are valid", the standard answer to that is not to have the server encrypt the passwords at all.  Instead, what we have the server do is store one hash of the two passwords.  That way, if someone manages to break into the server and get the hashes, that doesn't tell him anything about what the passwords are.

One simple implementation would to be to take a standard hash function (SHA256, for example), and when registering the user, compute the hash of the user-selected password concatenated with the one generated from the real password; the server would store this hash in the database (or forget the actual passwords).  Then, when authenticating a user, the user would supply the passwords, the server would concatinate them, hash them, and compare that hash to what's in the database (and, of course, allow the user only if the hashes are exactly the same).

One advantage of this over encrypting the passwords is that hashing is a one-way operation; no one can reverse the hash (this is actually one of the security properties of a cryptographical hash, that give a hash, no one can find that hashes to that value).  In addition, if the user enters the wrong data, it well detect that as well (as that's another of the security properties, that no one can find two values that hash to the same).

Now, if your second password is as good as you expect, that it is "almost impossible to guess", well, that's actually good enough.  Even if someone broke into the server and recovered the hash, well, all they could do is make guesses for both passwords, hash them, and seeing if both guesses were correct; if one of the passwords is unguessable, well, they can't do that.

However, I rather suspect that the password might be a bit more guessable than that (after all, if it were truly unguessable, why bother with the user-chosen password at all?).  If that is likely to be the case, it might be wiser to do the same approach, but with a password derivation function (such as PBKDF2); it's pretty much like a hash, but it does these nice things:

It makes provision for a "salt" (which is an additional value that is hashed in); it won't make a brute force attack on a single hashed password any harder, but it does mean that the attacker cannot attack several hashed passwords at once (because each of them will have a different salt).  The server would choose a random salt when registering the user, and include it along side the hash.
It's slower to evaluate than SHA256 (and in this context, that's not a bad thing; it means that an attacker will take longer to go through his dictionary).
It also provides a "key" that's needed to do the hash evaluation; if the server stores the key separately, well, the hash doesn't do the attacker any good unless he gets the key as well.

Oh, and one thing; about your specific question about how to combine the two passwords; well, hash functions and password derivation functions don't really care; they'll work with just about anything.  The only thing you need to be careful is to make sure that you combine them in a way that doesn't lose information.  For example, you wouldn't want to exclusive-or them together, otherwise (as a trivial example, the two passwords "A" and "1" would hash the same as the two passwords "B" and "2").  One easy and safe way to combine them is simply concatenate the two (of if the two passwords are "Alpha" and "Omega", you'd actually hash "AlphaOmega".  (Note: if both passwords are variable length, you make also want to concatinate the length of one of them if you want to be pedantic; otherwise the two passwords "AB" and "C" would hash the same as the two passwords "A" and "BC").


What is the best current way to cryptographically secure databases?

Reading your message, we (in ZeroDB) realize that we need to add some things to our documentation.

  Provides authenticity and secrecy (most important)

That one we do have now

  provides integrity over the whole database (no silent dropping of data)

We pretty much have it at the level ZODB we base on has (ACID-compliant)

  leaks as less information to the server as possible, doesn't have to hide access patterns

We don't leak properties of encrypted data like CryptDB, but we do slowly leak access patterns. Seems suitable for you

  allows for complex (cryptographically enforced) access rules

In the version currently on github, access rules are pretty simple (users own their sub-databases, but there are also "admin" users). We have a version with proxy re-encryption and possibility to grant/revoke access in end-to-end encrypted manner, in a granular way (column and row-based).

  It can be assumed that the clients do use / own public / private key pairs and / or passwords and everyone without valid keys is considered an adversary to the data he doesn't have access to, i.e. attackers may not undetected modify, add or drop data or being able to read the data if they have compromised everything except the client.

In current implementation, clients by default have their private keys derived from passphrases (trivial to add a possibility to use certificates though). Attackers may not modify or add data, though we need to add some extra protection against dropping data (detecting that an attacker removed piece of your data is possible but currently would take a while).

  The server should hold the only copy of the database and should not have to give it out (due to size) if possible.

This is how it works in ZeroDB

  As for the API, more standard APIs (SQL?) are preferred but custom ones are also acceptable as long as they support the usual queries (like ZeroDB and CryptDB do).

Seems like you're quite familiar with our query language :-) In future, we're going to add SQL compatibility since many people ask for that. May I ask: what types of queries do you need?

And yeah.. Merry Christmas :-)


Can $d$ and $e$ be the same number in RSA?

1) To choose $e$, this value have to be between $1$ and $\phi=(p-1)(q-1)$, with $\gcd(\phi, e) = 1$, right?

No; $e$ can be any value that's relatively prime to both $p-1$ and $q-1$ (or equivalently, relatively prime to $\operatorname{lcm}(p-1, q-1)$).  There may be little point in choosing an $e$ larger than $n$; however there's no specific reason it wouldn't work.

  2) [Paraphrased] What if I pick an $e$ with $e^2 = 1 \bmod (p-1)(q-1)$; and set $d = e$.  Would it work?

Well, yes, it would work, in the sense that the protocol will encrypt and decrypt messages just fine.  It wouldn't work in the sense that it wouldn't be secure (even if you used more realistic sizes of $p$ and $q$).


Deterministically generate a RSA public/private key pair from a passphrase (with sufficient entropy)?

Yes, it is possible to deterministically generate public/private RSA key pairs from passphrases. For even passable security, the passphrase must be processed by a key-stretching function, such as Scrypt (or the better known but less recommendable PBKDF2), and salt (at least, user id) must enter the key-stretching function; the output can then be used as the seed material for the RSA key generation. This works for any public-key cryptosystem.

Security is equivalent to what you have in e.g. PGP/GPG when assuming an adversary has access to the private key file protected by the (unknown, key-stretched) passphrase. However, there are drawbacks:

one is giving away the considerable degree of security obtained, in normal practice, by not making the  private key file public; that first line of defense is lost, only the (stretched) passphrase remains;
it is impossible to change the passphrase while keeping the same key and the advantage that only the passphrase is needed;
the key pair generation method should remain static; any change will end up with a different key pair; that precludes periodically increasing the passphrase-stretching parameters to take into account hardware progress (while keeping the same key and the advantage that only the passphrase is needed);
as a consequence, there's a very difficult compromise between security for many years with the same public key, and acceptable usage speed now;
as a minor aside, due to variability of RSA key generation time (at least by standard techniques), some passphrases/keys will require more time than others when deciphering or signing.

No, it is not currently possible that a public key of a traditional public-key cryptosystem (not based on communication with some server) can be (re-)generated from something that a typical human is willing to memorize (perhaps, 80 bit worth of entropy, about 24 digits, or 3 phone numbers), much less from a passphrase a typical human can choose and no other information.

In RSA with $n$-bit modulus, we can reduce the public key to about $n/2$ bits with a good argument that it does not reduce security, or to $n/3$ bits with no argument that it reduces security (see this question), but apparently not much further. Other public-key cryptosystem (like ECDSA) have a more compact public key for equivalent security, but it is still several times above that 80-bit limits, thus impractical to memorize, and even painful to key-in from paper. I have strong doubts that we can ever have a reasonably secure public-key cryptosystem with a public key less than 160 bits.


According to PBC manual, Pairing functions, map $\hat e(,)$ (without t-power) could be calculated as follows:

pairing_pp_t pp;
pairing_pp_init(pp, g1, pairing);
pairing_pp_apply(r1, gn, pp); // r1 = e(g1, gn)
pairing_pp_clear(pp);

Before calculating the map, pairing parameters must be initialized.


Are mouse movement coordinates useful as a seed for a RNG?

I suppose as far as entropy sources go, you could have chosen much, much worse. In fact a user properly moving his mouse while you collect a bunch of samples and hash them all together to obtain a seed is a pretty good random bit generator. Be conservative in your entropy estimates, for instance I would estimate no more than two bits of entropy per sample if you collect them intelligently (e.g. avoid continuous duplicates and keep a reasonably large sampling rate).

However obviously, a single mouse position is a terrible seed to use, since it doesn't even cover the whole 64-bit space. Your monitor is probably at best 1920x1080, which corresponds to about 2 million possible positions. WEAK.

But while this may be useful to keep in mind, it's probably best if you use an existing CSPRNG for your randomness needs, that way you don't bother the user, and you delegate security to someone else (which may be a good or a bad thing). You should always use the CSPRNG provided by your operating system as it is best placed to collect entropy, whether you like it or not. Under Windows, you can use CryptGenRandom() to access it.

It might seem counterproductive to use another RNG to seed your own, but entropy collection isn't exactly a trivial little thing that you just plug into a program. It has to be carefully and constantly monitored and tracked to keep a good estimate of the available entropy and ensure you don't lose any of it. Sure, making your own ultrafast PRNG using AES in counter mode for your specific needs might be worth it, but you need to consider the limits of your own random generator.


Understanding how Oscar can decrypt a message in RSA

Let's assume textbook RSA, which is not apparent from the question. In that case $b$ is the public exponent (usually this is $e$). So yes, encryption is then the first-to-last formula if $x$ is the index in the alphabet of the character. However, the $\bmod 26$ in the last formula doesn't need to be used; I think that the text is just used to indicate that $x$ is within the range $[0, 26)$. The word residue is out of place here; no division is performed on the alphabet, so there is no residue. The modulus for RSA encryption is just $n$.

There are many ways how this crypto system is vulnerable:

textbook RSA is deterministic, so you can do frequency analysis of the ciphertext if the characters are encrypted separately;
indices 0 and 1 (A and B) produce the values 0 and 1 after encryption;

but the main reason that this is insecure is that an attacker could just take the public exponent and then encrypt each character of the alphabet, creating a table from a specific ciphertext to a letter. After that you can iterate over find each ciphertext and replace it with the letter.

These attacks are not feasible if a good padding scheme such as RSA / OAEP is used.