Is this a secure method of encrypting with authentication?

The system you described—essentially, sign-then-encrypt with ECDSA and ECIES—is vulnerable to the following attack:

Alice sends Bob the signed-encrypted message ‘The deal is off.’
Bob removes the encryption layer, getting a signed message from Alice saying ‘The deal is off.’
Bob re-encrypts the message to Charlie.
Charlie verifies the message and thinks Alice has canceled the deal.

The problem here is that the message that Alice signed didn't specify a recipient.  The same attack applies to practical systems like OpenPGP and S/MIME, as noted by Don Davis in 2001.

The mere use of signature is also vulnerable to the following attack:

Alice types ‘what a basket of deplorables the voters are’ into her phone, but accidentally sends it to a journalist Jamal instead of her running mate.
Jamal now has a signed message from the political candidate calling her constituents deplorables which he can show to anyone.
Bob wins the election.

The problem here is that anyone can verify Alice's message, because signatures by design provide third-party verifiability.  (The respect Alice has for the voters may be another problem, and the respect Bob has for democracy, rule of law, and journalists, yet another problem, but let's not make this situation too real lest someone get diced up with a bone saw.)

There's a much simpler system, which is actually what Diffie and Hellman suggested in their seminal 1976 paper.  Assume Alice has published her public key $A = [a]P$ in the telephone book, and Bob has published his, $B = [b]P$.

To send a message $m$, Alice looks up Bob's public key $B$ in the telephone book and computes $k = H([a]B)$ to use with an authenticated cipher $E$ to send the ciphertext $E_k(m)$ to Bob.
On receipt of a ciphertext $c$, Bob looks up Alice's public key $A$ in the telephone book and computes $k' = H([b]A)$ to open the message $m = {E_k}^{-1}(c)$, or drop it on the floor if verification fails.

If the telephone book hasn't been tampered with, $k = k'$ so Alice and Bob can communicate.

If Alice wants to save time for many messages to Bob, she can cache the shared secret $k$ and reuse it many times; likewise Bob.  The only overhead is the authentication in the authenticated cipher $E$.

Bob can't forge a message from Alice to Charlie because Charlie has a different shared secret with Alice.  Jamal can't cryptographically prove to anyone else Alice sent an incriminating message, because any ciphertext that Alice could have made, Jamal could have made too using the same shared secret.

This very simple protocol—and the protocol you proposed—has another issue: if Alice's long-term key $a$ ever gets exposed, anyone who learns it can decrypt any past messages Alice has ever exchanged with anyone.  Modern protocols also do key agreements for each conversation like TLS, or each message like Signal, so that they can quickly erase the keys that would allow a network eavesdropper to decrypt past messages.  If you want a bespoke protocol in an application for which existing systems like TLS are unfit for some reason, you might look into the Noise protocol framework and the Noise Explorer, a tool to automatically verify security properties of custom instances of Noise.


Is jacobian to projective conversion unique?

You'll get back the same point; however it may be a different representation of the same point.

Remember, an elliptic curve point is a solution to a cubic equation in two variables (or the point at infinity); one commonly used equation is $y^2 = x^3 + ax + b$ modulo a large prime $p$.

What projective coordinates do is encode the $x$ and $y$ coordinates of the solution; the projective coordinates $(A,B,C)$ are considered equivalent to the solution with $x = AC^{-1}$ and $y = BC^{-1}$.

Notice what we have here; if we take an arbitrary nonzero value $t$, and replace $(A,B,C)$ with $(tA,tB,tC)$, it turns out that it is equivalent to the exact same solution $(x,y)$, and so it is the exact same point; it is just a different representation of that same point.

If you go through what happens when you use the algorithm to map from projective coordianates to Jacobian, and then back again, it turns out the process multiplies $A$, $B$ and $C$ by the value $C^2$; $C^2 \neq 0$, and so after this process, the new projective coordinates refer to the same elliptic curve point.


Per Mark's suggestion, I looked into the "hidden" tests in lwe-estimator and read a few papers. I summarized my findings as an answer here:

Arora-Ge attack, and the improved version using Grobner bases, work better when $q$ is small, but it starts to be impractical once the number of samples $n$ and $q$ is very large, e.g., $q=2^{64}$. This seems to be due to the time needed for linearization.

Another hidden test, MITM (Section 5.1 in https://eprint.iacr.org/2015/046.pdf), can be useful here---MITM considers $\alpha q$, and it is important that $\alpha$ cannot be way too small. Reflected in lwe-estimator, this would disallow one to use $\sigma\approx0.001$.

Still, more discussion is welcome. For my own use case, it seems that $\sigma=1$ or $\sigma\approx0.8$ may be generally okay since my $q$ is large.


Bitcoin mining: how is a block header of 80 bytes processed in SHA-256? Isn't it too big?

The SHA-256 compression function takes a 256-bit chaining value $h$ and a 512-bit message block $m$ and returns a 256-bit chaining value $f(h, m)$.

The SHA-256 hash function takes a padded message $m$ broken into an integral number of 512-bit message blocks $m = m_1 \mathbin\| m_2 \mathbin\| \cdots \mathbin\| m_\ell$, up to $\ell \leq 2^{55} + 1$ blocks long (the unpadded message length in bits, encoded into the last block, is 64 bits, allowing up to $\lceil(2^{64} - 1)/512\rceil = 2^{55}$ message blocks plus one more for the padded length), and iterates the compression function using a standard initialization vector $\mathit{iv}$ as the initial chaining value: $$H(m) = f(\cdots f(f(\mathit{iv}, m_1), m_2)\cdots, m_\ell).$$

If you are considering messages of the form $m_1 \mathbin\| m_2^i$ where you vary $m_2^i$ for the $i^{\mathit{th}}$ iteration, then of course you can precompute $h_1 = f(\mathit{iv}, m_1)$ and then use only a single evaluation of the SHA-256 compression function to compute $H(m_1 \mathbin\| m_2^i)$ by $f(h_1, m_2^i)$.


Is it cryptographically insecure to use fixed-length AES-GCM messages?

An adversary who obtains AES-GCM ciphertexts but does not know the key cannot obtain any information about the plaintexts except their lengths. This is (in a highly simplified form) the definition of the claim that AES-GCM is secure. This is true for any secure authenticated cipher.
If your plaintexts are intrinsically all the same size, this is an ideal situation, because the ciphertexts leak no information at all about the content of the plaintext.
If your plaintexts can have different sizes and the size of the plaintext leaks some information that you want to keep secret, then padding plaintexts so that they all have the same length is a possible solution. Beware that the generation of the message, the padding process, the unpadding process and the processing of the unpadded messages are likely to take time that depends on the length of the plaintext, so it may still leak through timing. Appending padding to the message may not be the best solution: depending on how the message is structured, it may be easier to construct a secure system if you arrange each part of the message to have a fixed size, and concatenate those fixed-size parts. That way the assembly and parsing of messages is less likely to reveal confidential information through side channels.
Adding a random amount of padding is unlikely to help security. In particular, if the same message is likely to be transmitted many times, an adversary can average out the lengths, which will negate the uncertainty of the random padding. However, it can help in some scenarios where you want to hide which message was transmitted for privacy (for example, to make it harder to figure out which file a user download on a server). Still, the only fully reliable way is to have fixed-size messages (in the download privacy example, this would mean padding all files to the length of the largest one).


But this increases the keys, you need to store these permutations. Is it a good idea?

I wouldn't think so; not so much from a subkey storage perspective, but from a performance perspective.

Storage could be do-able; $\log_2 128! \approx 716.16$; $20$ of these could be stored in $1791$ bytes, although it is likely that you wouldn't store them in a storage-minimal way, but instead in a format that makes it more efficient to perform the 20 permutations.

On the other hand, performance would look to be hideous.  There isn't an obvious way for software to permute 128 bits in a random fashion efficiently; picking each bit up, and depositing it in target position is unthinkably slow.  About the best I can think of would be to emulate a Batcher sort of the 128 bits (with appropriate masks to control when you swap and when you don't) - that's still likely to be slow (especially when you consider you need to do it 20 times).

As for hardware, well, by throwing a large number of gates at the problem, you could make it run reasonably fast - however, there are a lot of better ways to speed up other ciphers if you have a lot of gates at your disposal.

Why do I say performance is important?  Well, if you don't care about performance, it's easy to design things that are quite secure (e.g. 8-AES-256, using 8 independent keys); unless your design has some advantage over that, your cipher would appear to be pointless.


P = NP and current cryptographic systems

A proof of P = NP would prove that one-way functions do not exist. That in turn would imply, that almost no secure cryptographic primitives can exist according to the accepted definitions of security. (No symmetric encryption, no MACs, no pseudorandom generators, no signature schemes, ...)

However, it would just mean that no scheme can be provably secure. It does not mean that all schemes would be broken in practice. It might even be possible to adapt our definitions of security in a meaningful way.

In particular, it is very much conceivable that a proof of P=NP would be non-constructive. Such a proof would not help in any way. It would just mean that there exists an algorithm to efficiently break RSA (for a theoretical definition of efficiency, i.e. in polynomial time) but that does not mean that we know said algorithm. And even if the algorithm is known, it might not be efficient in practice.  An algorithm running in  $\mathcal{O}(n^{2^{100}})$ is technically a polynomial time algorithm, but it isn't very helpful.

So in conclusion, the question whether some keysize would still remain "secure" or how we could regain some measure of security cannot be answered in general, as it depends on the exact nature of the proof.


Lucifer had different versions, keylengths could be 48, 64 or 128 bits. The blocklength could be 48, 32 or 128 bits.

The Feistel structure was used there for the first time. Horst Feistel was the main designer.

Alan G. Konheim has a nice description in chapter 9 of his book Computer Security and Cryptography, including diagrams, given the many examples available for DES, you should be able to follow what happens in Lucifer. Google books has the beginning of that chapter.

One of the open expositions is in a paper by Smith, later on described by Sorkin.

It looks like DES with simpler round key bit choices and mostly shifts instead of permutations, thus weaker.

You should be good to go on from here.

References:

Horst Feistel, (1973). Cryptography and Computer Privacy". Scientific American, 228(5), May 1973, pp 15–23.
Konheim, Alan G. (2007), Computer Security and Cryptography, John Wiley & Sons, p. 283, ISBN 9780470083970.
A. Sorkin, (1984). LUCIFER: a cryptographic algorithm. Cryptologia, 8(1), 22–35, 1984.


why to use a safe-prime in Diffie-Hellman key exchange?

In order for Diffie-Hellman to be extra secure we must use a safe prime which is (p – 1) / 2 will also be a prime.

We don't have to; there are other options which achieve the same effect.  However, it works.

so my question is what extra benefit of using such a prime, what's new does it bring to the table.

Well, a lot of the security of DH depends on the subgroup structure of $\mathbb{Z}_p^*$, and that depends on the factorization of $p-1$.
For any generator $g$ we use, the order of the subgroup $q$ (the smallest positivie value $q$ such that $g^q = 1 \bmod p$) satisfies $p-1 = h \cdot q$, for some integer $h$.
In addition, we generally prefer working with a prime subgroup, that is, where $q$ is a prime value.  That's because if $q$ is composite, that is, $q = r \cdot s$, then given $g^x \bmod n$, we can recover the value $x \bmod r$ in $O( \sqrt{r} )$ time; if $r$ is not large, this leaks more information that we'd care for.
Thirdly, there is a invalid key share attack possible if you reuse DH public keys (which sometimes we do).  That is, if $h$ has a moderate factor $t$, then by issuing an invalid key share, the attacker can rederive $x \bmod t$ (where $x$ is your private value).  This attack can be detected, but the detection is expensive, and so it is often not done (even when you do reuse key shares).
So, with all that:

and does using a regular prime make the problem much easier to solve(make an attack practical).

What do you mean by a "regular prime"?  Do you mean just picking a random prime $p$ and random generator $g$?  Well, while the order of $g$ is probably large, it is likely to be composite, and will often have moderate factors; these factors (if present) would allow someone listening in to recover some information about your private value (and if you use one that's not full length, it may be enough to recover the entire value).  However, possibly this is not the case; however you're taking a gamble here.
In contrast, if we have a safe prime, well, we're safe.  We generally use a prime that's in the "quadratic residue" subgroup, that is, the one where every member (other than 1) has order $(p-1)/2$, which is prime.  And, if we happen to pick another generator (other than 1 or $p-1$), the only other subgroup is the one of size $p-1$, which means that the attacker can find $x \bmod 2$, but nothing else about $x$.
In addition, the invalid key share attack can only recover $x \bmod 2$ (because $h=2$), and so even if we reuse key shares, that's not a concern.
Now, there are other ways to make sure that we work within a prime-sized subgroup.  On the other hand, safe primes have the property that we can have $g=2$; these other methods generally require larger $g$ values (which makes part of the computation more expensive).


What could "look for the constants that you might find in RC6" mean?

The Key schedule appendix of the RC6 paper (Rivest et al.) defines two arbitrary constants in hexadecimal notation. They also appear in RC5.

$P_{32} = \tt{B7E15163}$
$Q_{32} = \tt{9E3779B9}$

Be aware that the binary coding of these constants will vary based on the endian-ness of the computer architecture.

There seems to be nothing 'special' about these constants in relation to the construction of the RC6 algorithm. They can be replaced with any random value, producing an incompatible variant of RC6 with presumably identical security properties, and the authors make note of this. (The 'official' constants were chosen based on open criteria, described in the paper, in order to dispel any notion that they induce a back door.) Thus a serious search for RC6 would include RC6-alikes and look for algorithm structure rather than constants.

There are no other arbitrary numeric constants defined in RC6, unless you would go so far as to consider the number of rounds etc. as such.

By the way, Appelbaum's talk wasn't "well documented" enough to provide any justification for this RC6 hunt. Typically of Appelbaum, he takes the position, "Trust me, I've seen the secret documents." Sounds like some senators I know.


I've decided to allow the user to choose between a pin code and a password.

/*
 * Various authentication types are possible within SneakerPass.
 *
 * For now, I've only implemented PIN (pin codes) and PWD (passwords). Here's how they work:
 *
 * PIN:
 *    For a pin code, the user will enter a pin that can include only what is on the keypad.
 *    THIS HAS LOW SECURITY! On a 4x4 keypad with 0-9 and A-D, that's only 14 possible keys.
 *    You'd need a 20+ digit pin code to have the same security as a 9-character password.
 *    ONLY USE IF:
 *      1) You know the implications of using reduced-keyspaces pin codes
 *      2) You can quickly remove the SD card from the SneakerPass hardware (for destruction, ingestion, etc)
 *      3) You need the speed of a pin code and reduced security.
 *
 *    Instructions:
 *      When the device is powered on, you will be asked to enter the pin code. Each key
 *      press will yield exactly one key. If you make a mistake, use '*' to erase the
 *      previous value and re-enter it. When you're finished, press '#'. If it is correct,
 *      you will enter the SneakerPass menu.
 *
 *
 * PWD:
 *    This is the preferable solution. It definiely takes more time to enter a password
 *    like you're typing a text prior to the invenion of T9. However, the keyspace is greatly
 *    expanded to include uppercase/lowercase numbers, all 10 digits, and 14 symbols.
 *    Below describes what each character maps to. You must keep selecting the same key
 *    to iterate through the values. If you are idle for 1 second, or if you select a
 *    different key, that value will be submitted.
 *
 *    KEY     NORMAL      SHIFT
 *    1       abc1        ABC!
 *    2       def2        DEF@
 *    3       ghi3        GHI#
 *    4       jkl4        JKL$
 *    5       mno5        MNO%
 *    6       pqr6        PQR^
 *    7       stu7        STU&
 *    8       vwx8        VWX*
 *    9       yz9         YZ(
 *    0       0-=         )_+
 *
 *    WARNING: IF YOU ARE USING A 3x3 PIN PAD, YOUR KEYSPACE
 *    WILLE NOT CONTAIN THESE CHARACTERS!!!
 *    A       []\         {}|
 *    B       ;'          :"
 *    C       ,./         <>?
 *    D       `           ~
 *
 *    *       [ TOGGLE SHIFT ]
 *    #       [ SUBMIT/ENTER ]
 */


What is DLf3072s256mRijndael cipher suite?

Guessing:

DL -> Discrete Logarithm
f -> finite field (of prime order)
3072 -> size of finite field in bits
s -> (not sure) SHA?
256 -> size of hash digest or subgroup size (used in DSA the old Digital Signature Algorithm?)
m -> don't know honestly.
Rijndael -> AES.


Longer IV generation from a single block IV for ICBC

I'm reading the question's suggestion as using $\text{IV'}_0=\text{ENC}_k(\text{IV})$ as the Initialisation Vector for stripe $0$ and for $0<i<s$ using $\text{IV'}_i=\text{ENC}_k(\text{IV'}_{i-1})$ as the IV for stripe $i$.

That's not (CPA) secure, because it allows distinguishing that the plaintext starts with zero blocks: in that case, the second ciphertext block of stripe $0$ will be the same as the first ciphertext block of stripe $1$.

Addition: I do not immediately see an attack¹ if we build the IVs as $\text{IV'}_0=\text{IV}$, $\text{IV'}_i=\text{ENC}_k(\text{IV'}_{i-1})\oplus\text{IV}$. Or this slightly different option, using the question's notation:
$$\text{IV'} = \operatorname{CBC}_k(\text{IV},\text{IV}^s)$$

¹ which is not a conjecture of security.


Known-plaintext attack on 1-round Feistel networks

Regardless of the specific $f$ function, you already observe that you can obtain
$$
R_1\oplus L_0=f(R_0,k_1)
$$
where $k_1$ the first round subkey is your target.

But $R_0$ is also a part of the known plaintext. So you have a system of equations for the bits of $k_1$ which you can systematically attempt to solve. For a normal Feistel function $f$ (which is one to one or the cipher wouldn't be invertible) this is straightforward.

Exactly how $sha_2(R_0,k_1)$ is defined plays a part here:

Possibilities include $sha_2(R_0||k_1),$  or $sha_2(R_0 \oplus k_1)$ (possibly with padding or repeating of $k_1$ to make it the same length as $R_0.$).

In any case you can try to use the $sha_2$ equations, noting that the effective input length is essentially at most the length of $R_0$ plus the length of $k_1$ and hence a strong hash function is most likely one to one for such inputs. Using the random oracle model, a randomly chosen function from an input of length, say, 128 bits, to the full digest size for sha_2 of 512 bits is one to one with overwhelming probability (see birthday paradox, addressed in many answers to questions on crypto stackexchange).


How many bits of an exponent are leaked when doing a powmod?

The answer depends on the factorization of $p-1$; for any factor $q$ of $p-1$, the attacker can derive $x \bmod q$ in $\sqrt{q}$ steps (by first computing $(g^x)^q = g^{xq}$, and then searching for the value $y$ with $(g^{xq})^y = 1$ using, say, Pollard Rho.

Hence, if the attacker has a computation budget of $n$, and $p-1 = q \cdot r$, where $q$ is $n^2$ smooth, and $r$ has no prime factors $< n^2$, then the attacker can derive $x \bmod q$, which can be analogized to $\log_2 q$ bits.  However, if you're interested in the precise bits (and not just bit equivalents), then (unless $p-1$ is $n^2$ smooth, in which case you can derive the entire value of $x$), you're stuck with $m$ bits, where $2^m$ is the largest power of 2 which is a factor for $p-1$.

(Note: I'm ignoring the factor that if $p-1$ might have multiple prime factors near $n^2$, we might take more than $n$ work; not ignoring that makes the analysis more complex, without changing the result substantially)

By this logic, your observation that we can always derive the lower bit of $x$, that is $x \bmod 2$, is equivalent to the observation that $p-1$ is always even.


What cryptanalysis is possible against two independent keystreams XORed against plaintext?

Asmuth and Blakley provided a proof that, assuming the keys for each cryptosystem are chosen independently, breaking their composite cryptosystem is at least as hard as breaking the hardest part of either. [1]  Building on their work, cascade ciphers have been shown to in fact be harder to break than the hardest part of either.

Admittedly, what you're talking about sits in an awkward place between cryptographic exponentials and cascade ciphers.  A cryptographic exponential (of two ciphers) is defined as:  $$M\oplus R\oplus R'\>\|\>E(R)\>\|\>E'(R')$$ where R and R' are truly random bitstrings.

I can't give much of anything concrete other than that.  Hope this answers your question.

C. Asmuth, G. Blakley.  "An efficient algorithm for constructing a cryptosystem which is harder to break than two other cryptosystems"


When would one prefer a proof of knowledge instead of a zero-knowledge proof?

Formally, this is all very complicated, but informally:

An interactive proof is a conversation between a prover and a verifier that ends with the verifier either accepting or rejecting.

The interactive proof can be zero knowledge, in which case a cheating verifier does not learn anything new by talking to the honest prover.

The interactive proof can be a proof of knowledge, where a cheating prover cannot convince an honest verifier to accept unless he (essentially) knows some secret.

The interactive proof can of course be both zero knowledge and a proof of knowledge.


random number generator 10-side dice alternative

One problem is that keyboard keys may or may not be uniform. Look at the F and J keys - they may have a little dot of plastic to identify them with your fingertips. That little dot may make them heavier or lighter than other keys, affecting how they shake up in a hat. Some keyboards, like Das Keyboard, were built with different spring actions for different keys, which might or might not affect the weight or shape of each key. And some keyboards have larger curvatures for various key tops, and those keys definitely have different mass.

The problem is that creating perfectly symmetric keys is not a design goal for keyboard designers, so without studying and measuring each keyboard, you won't have assurance that any particular keyboard is suitably random for your purpose.

They may also be just fine if you are not looking to generate thousands of passwords. If you're concerned, though, consider repurposing a device designed to generate random values. A bingo cage could be refilled with 26 hand lettered balls. Playing cards could have handwritten letters and shuffled extensively. A 100-sided dice could be repainted to match your character set, and extra values blacked out to indicate "roll again".

See also "diceware" for a way to turn 6 sided dice into passwords.


Why is "key-rotation" called key-rotation?

Purely speculation, but given most cipher usage historically was military, diplomatic and espionage, I wonder if it might be related to the longtime common practice of the military (certainly US, and I believe many others), and to an extent the diplomatic corps at least US, of changing the assignments of individuals to jobs, posts, or duties, and for the military of whole units to missions, on a regular schedule automatically (i.e. not requested by the people involved). This practice is usually called rotation, and a particular (limited-time) assignment is metonymically called a rotation -- e.g. a soldier might speak of 'doing a 3-month rotation in \$job1 and then being moved to \$job2'. Random example To a military comms specialist -- and their commanding officer -- the periodic, scheduled replacement of one key by another would certainly seem similar.


What is the harm if I publish an encrypted RSA private key publicly?

Systems like ssh, for example, often encrypt a user's private key using a password, so that is not new. The fact that they are published on a web server that technically anyone could access is a little different. But, if the password is strong, brute force and dictionary attacks would be impossible. So the system seems secure.

That if, though, is a big if. As CodesInChaos points out, users are bad at picking good passwords. So, lets assume they are still bad at picking passwords. Eventually the URLs will become known, so we can't rely on that for security. An attacker can then download the encrypted private keys and decrypt them since a bad password was chosen.

How does this differ from traditional passwords? Well, in traditional passwords, at least the database and server can be hardened to keep people from getting material that can be used in an offline dictionary attack. Under this system, the URL scheme would be the only thing preventing an offline dictionary attack.


Universal forgery based on mathematical problem

Elliptic Curve Digital Signature Algorithm admits universal forgery if the Attacker can solve the equation
$$z=\frac{\psi_{k-1}(x,y)\psi_{k+1}(x,y)}{\psi_{k}(x,y)^2},$$ where $k$ is unknown, $\psi_{k}(x,y)$ are Division polynomials  and $(x,y)$ are the coordinates of a point $P$ on the elliptic curve $ E:y^{2}=x^{3}+Ax+B$. This UF is based on the formula for the coordinates of the nth multiple of $ P(x,y)$:
$$kP=\left(x-\frac{\psi_{k-1}(x,y)\psi_{k+1}(x,y)}{\psi_{k}(x,y)^2},\ldots\right).$$

The question Elliptic curve sequences needed for universal forgery about hardness of this UF was asked at MathOverflow separately.


Need a test suite for my RSA implementation


If you can recover the private key from a message and a signature (and the public key), then that signature method is broken, and broken quite bad.

We believe that RSA, with a decent signature padding method, is secure, and hence the specific failure mode you mentioned cannot happen.

There are two obvious ways to try to recover the private key for RSA; we believe that both are infeasible.

In the first one, we have the padded value of M (note: RSASSA-PKCS1_V1_5 has deterministic padding, so we always know that Pad(M) looks like, and we have the signature S; we could try to find the value $d$ where $Pad(M)^d = S \pmod{N}$, d would be the private key.  However, this is a discrete log problem; we believe that is difficult

In the second one, we could try to factor the public modulus $N$; if we could, then we could compute $d = e^{-1} \pmod{lcm(p-1,q-1)}$, and that would be the private key.  However, we believe that factoring a number the size of N is difficult.

One thing that might be an issue is a man-in-the-middle; if there is something between the client and the server; the server sends M to the man-in-the-middle, who forwards it to the client; the client returns the signature to the man-in-the-middle, who forwards it to the server.  The server thinks it has authenticated the client, but if the man-in-the-middle can then send its own requests to server, it hasn't really.

It might be that the larger protocol has protections against this sort of thing; however that's what I would be worried about.


How does pairing letters increase the security of a substitution cipher?

In a simple substitution cipher you have a mapping of 26 letters like following:

A -> M
B -> Z
C -> V

The statistics for English texts shows that letter E has frequency 11.162%, T - 9.356%, A - 8.497%, etc. An attacker computes frequency for each letter in the encrypted text. If the text is long enough, then a symbol with frequency about 12% is very probably E, a symbol with frequency  about 8% is very probably A, etc. In the example above suppose the text is long, and the frequency of M is 8.2%. Then the attacker will fist suppose that M in the encrypted text corresponds to A in the original text. The same for other letters. In the reality the frequency will deviate from this, and the attacker will test some other variants. Despite this the number of combinations that he will test will be relatively small, compared to a straightforward brute-forcing of 26! (1x2x3x4x5...x24x35x26).

You text about 26 x 26 means that they suggest not to replace a letter by letter, but a pair of letters to another pair of letters, like following:

AA -> GH
AB -> DT
AC -> LQ
...
BA -> BM
BB -> KA
BC -> OJ
...
ZY -> ZG
ZZ -> WM

There are 26 x 26 = 676 pairs mapped to other pairs.

For pairs the frequencies are also known and in case of long message or if attacker has many short messages, they still can be relatively easy decrypted. But for short texts it it can be hard.

Suppose the message has length 2600 symbols. In case of simple mapping it means that each letter on average is used 100 times. The correlation of frequencies with known values can be very high and decryption can be very quick.

But suppose this message was encrypted with polygraphic substitution of 676 pairs. Each pair will be used on average less than 4 times. That's why deviations of frequency of each pair from the known average values will be high. The attacker will have to test much more candidates for each pair. The amount of computations can be much higher than in case of simple substitution. Thus if the attacker has not sufficient resources (not enough computation power, not enough time), this can help to keep the message encrypted.

In serious cases, when encrypted message is valuable, more resources can be involved and also such cipher can be more or less quickly brute-forced. And an attacker will use of course not only frequency, but all possible information. E.g. the frequency of combinations of 3-4 letters, the frequency of some words in the language.


LLL - Lattice Reduced Basis Algorithm question?

LLL algorithm has two main parts:

the reduction step: which recomputes the basis vectors aiming to reduce the values of the Gram-Schmidt coefficients to some value smaller than one half. This condition is usually written as $|\mu_{i, j}| < \frac{1}{2}$.
the swap step: which swaps basis vectors aiming to achieve the Lovász condition, that is $ \delta \Vert \mathbf{b}^*_{i}\Vert^2  \leq \Vert \mathbf{b}^*_{i+1}\Vert^2+ \mu_{i+1,i}^2\Vert
 \mathbf{b}^*_{i}\Vert^2$.

Notice that the swap step just changes the order of the vectors, so, if somehow the reduction step is not executed, the output is just a reordering of the input basis...

Now, what is the Gram-Schmidt orthogonalization of a basis that is already orthogonal? Answering this will give you a trivial relation between $\mathbf{b}_i$ and the corresponding GS vector $\mathbf{b}_i^*$. And what are the values of $\mu_{i, j}$ given that $\mathbf{b}_i$ and $\mathbf{b}_j$ are orthogonal?

With these information, you can see that, for an orthogonal basis, the reduction step is ignored and the LLL algorithm just reorder the basis vectors according to whether $ \delta \Vert \mathbf{b}_{i}\Vert^2  \leq \Vert \mathbf{b}_{i+1}\Vert^2$ or not.

And to answer your second question, you just have to run this "simplified LLL" that you will have found in the first question and get the correct reordering.


Naor Pinkas OT - senders security; reduction to DDH

Hint

Due to DDH we have that $(g^a, g^b, g^{a\cdot b}, g^c)$ and $(g^a, g^b, g^{c'}, g^c)$ are indistinguishable (where $c'$ is uniformly random and independent of $c$).
By the same reason, $(g^a, g^b, g^c, g^{a\cdot b})$ and $(g^a, g^b, g^{c}, g^{c'})$ are indistinguishable.

Can you see how to put things together?


Why Smart's attack doesn't work on this ECDLP?

The reason the attack does not work is because you are hitting a special case—the canonical lift. This is the case where the lifted curve over $\mathbb{Q}_p$ is isomorphic to the curve over $\mathbb{F}_p$, in which case no additional information can be extracted from it. The journal version of Smart's paper mentions this case.

The solution is simple: if we are hitting a special lift, randomize the lift! We can do this by lifting to the $\mathbb{Q}_p$ curve $y^2 = x^3 + (p\cdot a')x + (8856682 + p\cdot b')$, for some arbitrary $a'$ and $b'$, which reduces all the same modulo $p$, but will be unlikely to hit the same issue. So we can easily rewrite the attack as

def SmartAttack(P,Q,p):
    E = P.curve()
    Eqp = EllipticCurve(Qp(p, 2), [ ZZ(t) + randint(0,p)*p for t in E.a_invariants() ])

    P_Qps = Eqp.lift_x(ZZ(P.xy()[0]), all=True)
    for P_Qp in P_Qps:
        if GF(p)(P_Qp.xy()[1]) == P.xy()[1]:
            break

    Q_Qps = Eqp.lift_x(ZZ(Q.xy()[0]), all=True)
    for Q_Qp in Q_Qps:
        if GF(p)(Q_Qp.xy()[1]) == Q.xy()[1]:
            break

    p_times_P = p*P_Qp
    p_times_Q = p*Q_Qp

    x_P,y_P = p_times_P.xy()
    x_Q,y_Q = p_times_Q.xy()

    phi_P = -(x_P/y_P)
    phi_Q = -(x_Q/y_Q)
    k = phi_Q/phi_P
    return ZZ(k)

which now succeeds:

sage: p=235322474717419
sage: a=0
sage: b=8856682
sage: E = EllipticCurve(GF(p), [a, b])
sage: P = E(200673830421813, 57025307876612)
sage: Q = E(40345734829479, 211738132651297)
sage: assert(P.order() == p)
sage: n = SmartAttack(P, Q, p)
sage: assert(n*P == Q)
sage: n
152675955744921


Memory-expensive hash from an array of hashes?

The premise that people cannot make a memory intensive password hashing function is incorrect. scrypt does approximately what is described in the question. Of course you still want to limit the amount of memory, especially if many of these hashes are to be calculated in parallel.

Furthermore, you could have a look at the password hashing competition where m_cost is specifically mentioned as a possible parameter to the hash function. You'll have to look at the candidates to see if that parameter is present and how it is used though.

Note that the main idea of using larger amounts of memory is to protect against brute force attempts that make use of hardware acceleration. Just scaling up the amount of memory to rely on the speed of memory access does not make sense; an attacker may have a system that does faster memory access than your system. It's less likely that an attacker has both hardware acceleration and a hugely fast & large memory system.


When a DER format RSA private key is extracted from an encrypted PEM file, is it still encrypted?

No, it will output the PKCS#1 compatible encoding of the private key, try this:

openssl asn1parse -inform DER -in sample.prv.der

it will output an ASN.1 sequence of:

a version number (00);
the modulus;
the public exponent;
the private exponent;
the CRT parameters.

It did ask you for the password, right?


suggestions for cryptography projects for an ece 3rd year student

Cryptography is a broad field and most of it falls naturally under computer science and math. However there are certain areas that are very much within ECE's domain. For an undergraduate project, you typically do not need to find new results, just do a good literature review and perhaps implement/duplicate some of the results.

Here are a few ideas for an ECE student:

Side-channel cryptanalysis. When a cryptographic function is implemented, the implementation itself can leak information that is useful to an attacker. On the hardware side, it could be power consumer or radiation. With an FPGA, you may purposely zap certain gates to introduce faults that may leak useful information. (Wikipedia)
Reverse-engineering chips. Sometimes vendors will implement a cryptographic function without disclosing the details of the function. There have been a number of papers on reverse-engineering RFID chips by inspecting the VLSI layout. There are tools to automatically recognize certain gates or components from images of the circuit. (Example paper)
PUFs. Physically unclonable functions use the natural variance in physical structures to implement cryptographic functions. A number of candidates for PUFs are electronic components. (Wikipedia)
Implementation and Optimization. There is usually always room for implementing a function as optimally as possible in your favourite medium. For ECE: VLSI or FPGA for example. The major functions (AES, SHA, etc) have had attention in this regard but more obscure primitives/protocols may have less attention.
Circuit-based Evaluation. One goal in cryptography is to do computation on encrypted data in a way that does not reveal the data itself. There are generally three classes: two-party computation, multi-party computation, and homomorphic computation. In two-party in particular, an approach is to represent the function being evaluated as a boolean circuit and then use a technique called "garbled circuits" to evaluate. Most researchers look at general techniques for doing this efficiently and with high security; less look at how to best represent a boolean circuit that implements are particular useful function (beyond certain toy examples like Yao's millionaire problem). (Example Paper)

This is a good blog on research that is generally more from the engineering perspective.


Using the same private key to generate Schnorr and BLS signatures

There is a classic solution, applicable to any two public-key cryptosystems: deriving both private keys from a master key, which plays the role of a new common private key.

Start from a master key. Derive from it and two public constants the seeds of the CSPRNGs used for the key generators of the two public-key cryptosystems (use some Key Derivation Function like HKDF). Perform the two key generations (limited to public key if that help), to obtain the public keys. And, at each use of the master private key for one cryptosystem, perform the appropriate one of these two derivations, then the appropriate key generation (limited to private key if that helps), thus obtaining the private key for the cryptosystems, and use it as normal.

The main drawback is more complex/costly use of the private key, and that's an issue with RSA. But for Discrete Logarithm based cryptography, including Elliptic Curve Cryptography, the overhead tends to be minimal (relative to private key use), because the KDF has comparatively low cost, and reducing its output to a private key is usually essentially modular reduction (ECDSA) or bit extraction (Ed25519).

Note per comment: the requirement that "the verifier should be able to tell that the signatures were generated with the same private key" is met only as far as the verifier is certain that the two public keys used to verify the two signed messages have been generated from the same master key. The person preparing the public keys must thus be trusted. To avoid errors, it is possible to add a unique common identifier to the public keys. That can be obtained from the master key by derivation with another constant.


In an A5/1 stream cipher, why do the registers have a stepping probability of 3/4

In A5/1, there are three shift registers (about 20 bits each), each with a certain bit (about in the middle) controlling clocking. At each cycle, a register is shifted when its clock bit agrees with one or both of the other two clock bits.

Under the fair approximation that the clock bits are random, independent, and evenly distributed, a given register is thus shifted with odds $3\over4$ (derivation: as the odds of a coin toss matching either of two other coin tosses).


Proof that a hash matches an encrypted file

If you use a one-time pad as your encryption function then this simplifies to a proof that Alice knows some $F$ that hashes to $H$. $K$ can be trivially derived from $F$ and $E(K, F)$ by xor-ing.

An interactive zero-knowledge proof of this simpler problem - Alice proving she knows a pre-image of $H(F)$ - would go something like this:

You need to use a partially homomorphic hash such that $H(A+B) = H(A) \oplus H(B)$ for some composition operation on each domain. An example might be to add/xor the pre-images and use scalar multiplication of an elliptic curve base point as your hashing function - though note for an arbitrary length message this is going to be magnitudes slower than a traditional cryptographic hash function.

In a single trial in the proof Alice generates a one-time pad - $P$ - and commits to $H(P)$. Bob calculates $H(F+P) = H(F) \oplus H(P)$. He can challenge Alice to reveal either $P$ or $F+P$. Each trial halves the probability that Alice is cheating.

You can turn this into a non-interactive proof by Fiat-Shamir. It's not very succinct however, the proof ends up being many times longer than $F$.

I guess with a homomorphic DRBG you could extend the proof to show that Alice knows a stream cipher key $K$ that defines the tranformation $F \rightarrow E(K, F)$. This would improve the succinctness of the proof as well as being a closer match for what you asked for.


Aren't $IV_1$ and $IV_2$ public in TLS 1.2 as well?

$IV_1$ certainly is (as that's just the ciphertext block in front of the block we're attacking); however the IV that the TLS 1.2 sender will use for the next message ($IV_2$) is not.  In fact, the sender might not know it yet, as it might not have not picked it yet.

  But doesn't this mean that BEAST will only verify you guessed a message correctly with quite low probability?

Actually, if you guess all 128 bits of the block correctly, it will tell you.  If you say "what's the probability that we can guess all 128 bits?", well, we can make it significantly better than $2^{-128}$.  Another thing that BEAST does is it maneuvers the cookie under attack so that the plaintext block that we're trying to guess consists of:

KNOWNCOOKIENAM=?

where it knows the first 15 bytes of the plaintext; all it needs to guess is the last byte of the plaintext (which is the first byte of the cookie under attack).  Then, we need to check at worse 256 possibilities for that unknown byte (actually, less, because not all byte values are possible).  Yes, each attack requires a new message; however messages are pretty cheap.

Then, if it finds out that the first byte is X, then it remaneuvers the cookie, and then it attacks a block that consists of:

NOWNCOOKIENAM=X?

where ? is the second byte of the cookie.

That's the insight of BEAST; not only does TLS 1.0 allow us to verify guessed plaintext blocks with a CPA attack, but also by playing games with cookies, we can make plaintext blocks guessable.


How often do I need to rotate AES 256 keys

Is it necessary to factor time into this equation for devices that communicate infrequently with the same key?

No. Time would only matter for attacks that require a lot of processing by the attacker. Basically, key recovery attacks, through either brute force (impossible with AES key size) or maybe weaknesses in the cipher (even known related key attacks aren't feasible either).

In comparison, the attack here only needs to store all the used ciphertext in a data structure so that duplicates are detected. If you use a hash table, that's $O(1)$ time per block.

  How does one determine an acceptable risk factor?

You have to understand the risk first.

The attack here is related to the block size of AES, i.e. 128 bits (even with your 256-bit keys the block size is 128). The risk factor essentially indicates the probability that a duplicate would be observed with a PRF after that many blocks. The advantage gained by the adversary is some information about the plaintext of some encrypted blocks. It does not allow key recovery.

What it means depends on the cipher mode used. For example:

If you are using CBC, like in the linked question, the risk is that two blocks of ciphertext are equal, leaking the xor of the corresponding plaintext blocks.
With CFB, if two ciphertext blocks are equal, it leaks the xor of the blocks following them.
With CTR, if counters remain unique, the risk is that two ciphertext blocks are equal. Here it only leaks the fact that the two plaintext blocks are different.
With OFB, a collision results in the rest of the key stream being equal, leaking the xor of the rest of the messages.

You have to decide how important it is that the attacker not learn that information.


Can I encrypt user input in a way I can't decrypt it for a certain period of time?

This is an interesting discussion of the problem, as well as this crypto.SE question (they seem to be called "time-lock puzzles").

The most reliable scheme is to use a trusted third party which provides a public key and only releases the private key some time later.

The only scheme that doesn't require a trusted third party is to iteratively hash a random value for the time period you want, use the result to encrypt the information, and then discard the result and store the initial random value. To decrypt the data the iterative hashing needs to be performed again in order to recover the result which was used to encrypt the data, which should take the same amount of time it did before (although hashing can be sped up with GPUs or ASICs).


The authors of the paper might be able to tell you; I suspect no one else will.

You are having problems understanding the paper; a large part of the reason is that the paper isn't very well written; it introduces terminology (such as "ph") without ever defining it, and includes things that don't make any sense, such as the first line of their "Encryption Process": "If M=3, such that M$<$n ").

This might be an indication that they are not used to writing papers (along with their lack of fluency in English), or it might be an indication that they really don't know what they're talking about.

My best guess about their proposal (from making "corrections" in what they wrote, and in a way that's looks to be secure) would be:

Select primes $p$ and $q$ and a small value $r$
Compute $e = r^{-1} \bmod pq$ and $d = e^{-1} \bmod (p-1)(q-1)$ (there's no indication what to do if $e$ is not relatively prime to $(p-1)(q-1)$; perhaps pick a different $r$?)
To encrypt a message $M$, compute $C = eM^e \bmod pq$
To decrypt a message $C$, compute $M = (rC)^d \bmod pq$

This would work and also be secure (as it can be easily reduced to RSA); however it also begs the question "what advantages does it have over standard RSA?".  After all, they use a large public exponent $e$ (remember, it's $r$ that is small); and so it would appear they're making the public operation more expensive; what benefit are they gaining for that expense (perhaps some tolerance to side channel attacks?  If so, they would need to spell out the side-channel resistant implementation).


Certificate Authority RSA key expiration?

To understand why CAs need to rotate their RSA keys less often, let's first investigate why end-users have to rotate their keys / certificate every few years.

There are three main reasons why end-users have to renew their keys / why certificates have a limited life-span.

To keep CRLs somewhat small. Expired certificates don't need to be put onto CRLs because they're invalid anyways, this the CRLs can be "constant-sized". Obviously CAs aren't hit by this because you always have an explicit list of trusted CAs.
To enforce technology renewal. From time-to-time technology changes and becomes potentially unsafe. Certificate renewal usually forces you to upgrade to more secure technologies (like RSA-2048, SHA-2, ...). The CAs are hit by this, but not because of expiry dates but rather because of pressure from the browsers. However they usually tend to have a long grace period where they put their new certs (not neccessarily with new keys) into the trust stores and gradually remove the old certs.
To allow CAs to earn money. When your certificate expires, you have to buy a new one from the CAs which brings them money. So obviously they want to limit certificate validity. Obviously CAs aren't hit by this because renewing CA keys is a lot of work and procedures and thus will be avoided at (nearly) all costs.

So the main reasons why CAs renew their keys seems to be that they have to upgrade key-length and the the main reasons why they have to renew their certificates is outdated hash functions (but in this case they usually keep on using the keys).

Now there are two more reasons why CAs have to renew keys / certs (without being put out of business due to a breach):

Issues related to their root key storage. CA root keys are stored in super-secure HSMs inside of heavily guarded vaults. Depending on the HSM in use, it runs on batteries (while it's not being actively used) and they will run out of power sooner or later. At this point you have to renew keys as well. This happens after five years earliest and depending on their setup may require new keys to be put in the trust stores or just some effort to move the keys into a new HSM (which is possible).
They "screwed up" with the expiry date. Obviously you only want to renew keys / certificates if there's a need for it and sometimes the older CAs just set their expiry date of the root certificates to something like 20 years in the future assuming there would be other reasons meanwhile to renew the certificates. But that usually doesn't happen so they keep the key and just distribute a new cert (with a much longer expiry date this time).


What are the implications of allowing a zero-length GCM nonce?

As documented in NIST SP800-38D, GCM works as follows, upon input of block cipher $E$, key $K$, initialization vector $IV$, and plaintext $P$:

Compute the GHASH key $H=E_K(0^{128})$
Compute the initial counter-mode value $J_0$ using some rules which amount to $J_0=0^{128}$ for an (illegal) empty IV.
Encrypt the plaintext using CTR-mode and IV $\operatorname{inc_{32}}(J_0)$, i.e. $C=\operatorname{GCTR}_K(\operatorname{inc_{32}}(J_0),P)$
Compute the polynomial hash (GHASH) over the ciphertext $C\|0^u\|\operatorname{len}(A)\|\operatorname{len}(C)$ using the key $H$ and call the resulting block $S$.
Compute the tag as $T=\operatorname{GCTR}_K(J_0,S)$

Now the key thing to note here is that $\operatorname{GCTR}_K(J_0,S)$ actually amounts to computing $E_K(J_0)\oplus S=E_K(0^n)\oplus S=H\oplus S$. Now we only need to realize that e.g. for a single-block message we have $T=H\oplus S=H\oplus H^2\cdot C\oplus H\cdot L$ where $L=\operatorname{len}(A)\|\operatorname{len}(C)$. As you can probably see the last equation $T=H^2\cdot C\oplus H\cdot L\oplus H$ is actually a quadratic equation where we know every value except $H$.
As we're working over a finite field in the above computation, we can just solve the equation using standard algebra and compute $H$ using the appropriate operators for the field. As you have now recovered $H$, you can change the ciphertext however you want and re-authenticate it at-will and even do that to messages with a different nonce but the same key.
This issue is avoided in "legal" versions of GCM by hashing in the length of the IV for variable-length IVs and for fixed-length IVs by setting the last bit to 1. This then yields a $J_0\neq 0^{n}$ which gets translated to a (pseudo-)random independent-looking value by $E_K(J_0)$.


What are the computational benefits of primes close to the power of 2?

After a multiplication you have a number with $2 \cdot 255$ bits. Since $2^{255} = 19 \pmod q$, you can take the upper half, multiply it by 19 and add it to the lower half. This gives you an equivalent number smaller than $20 \cdot 2^{255}$. Repeat this to get a number that's smaller than $2 \cdot q$. Now check if the value is greater or equal to $q$ and subtract $q$.

Being close to a power-of-two matters in the first step. Since 19 is so small, the number after the first reduction step is only a few bits bigger than $q$.

If to the power-of-two the difference were bigger, the resulting number would be bigger and you'd need more steps to reduce it. If you have a random prime, the result is barely smaller than the input and you're better off with a different algorithm (such as montgomery reduction).


Are there reasonably secure online voting implementations e.g. for student council elections?

In short, my answer is no; keep paper ballot, they have essential virtues unmatched by electronic substitutes; in particular, giving voters confidence that the result of the vote is not grossly manipulated.
Full disclosure: I co-founded a (French) association towards citizen oversight of voting means, essentially opposing electronic voting for political elections. I take some pride in our contribution (however little) to an observed pause in the deployment of electronic voting machines in France since 2007.
Electronic voting has two different meanings:

voting in polling stations using dedicated electronic voting machines;
voting remotely by electronic means such as mobile phone, web browser.

The question seems to be about 2, and I'll focus on that. A major problem is that it does not propose any means to discourage vote selling or voting under duress. In most proposed systems, handing over one's credentials to vote (perhaps: during the closing of the polling time-frame) will do the trick.
Contrast with the traditional voting system used for political elections (in France, and many countries with a long history of voting, thus a long history of voting fraud, and fixes to the voting code to fight that). Voting takes places according to procedures carefully designed to discourage vote selling and threats to vote in some prescribed way, by making it hard (and prohibited) that anyone but the voter knows how the vote was cast (that goal is not reached for mail voting, instead this is purposely kept marginal by requiring formal prior declaration to police that normal voting can't be performed for some reason, like traveling). Towards that goal, complex measures have evolved over time:

generally, making it illegal and difficult to act in any way such as showing how one voted, or transferring one's right to vote to another person (voting requires an official ID with photo, in all but very small towns).
requiring the insertion of paper ballot materializing the vote in an opaque envelope in a voting booth ("isoloir" = isolating device) where no one but the voter is allowed;
making paper ballots with a distinctive sign invalid (and not counted); this is a countermeasure to the practice of marking the paper ballots handed for vote under duress/pay with a distinctive sign, so that the bribed/intimidated voter can fear that if s/he does not use that paper, it will get noticed at vote counting;
often, making the paper ballots available by multiple means (at the polling station, and by mail), so that voters can be seen not grabbing a ballot from the stack X at the polling station, but still actually vote for X by using a paper ballot for X that they brought secretly (ticking a choice with a pen would be superior to paper ballots in this regard, but may bring back the previous problem; also, separate availability of paper ballots at least helps the reading impaired).

Another issue with both forms of electronic voting is that it makes fraud by a very small group of persons conceivable, when the traditional voting system makes that impossible for large-scale voting with multiple independent polling stations (this argument thus does not apply to a small local student council with a single polling station):

Votes are cast in urns which remain observable from vote start till end of counting (French urns are transparent, in reaction to fraud).
Votes are counted locally at each polling stations; anyone is allowed to obverse counting and check what the tally at the polling station where s/he voted.
The tally at each polling station is made publicly available in print, so that any observer can check that the tally at the polling station where s/he voted was not modified, and check the addition of counts thus the election result (there is a hierarchy of two levels of publication, but the principle remains valid).

Most importantly, a rational person/voter can be convinced that the traditional system does not allow centralized fraud; but electronic voting systems which manage to keep what one voted secret do not meet (or even have) that goal, to my knowledge. At best, the organizers of an electronic election can be convinced that there was no fraud; that's not the correct objective (and it is not even really met by any practical system that I have seen).
Again restricting to voting remotely by electronic means, some usually poorly mitigated risks include:

Browsers (e.g. on university computers) modified to vote as asked by the voter as far as the screen is concerned, when the vote is really cast differently on the network side; that's far from rocket science.
A server pretending to be the real voting server(s) to the voter's browser, performing Man-in-the-Middle attack at some point on the network; if the cryptographic defense is https with TLS as in normal web browsers, that's defeated with a copy of the private key of the true server (certificates emitted by certification authorities in breach of CPS, which abound, would also trick most voters, albeit with a risk of being caught by an observer comparing the certificate shown by the browser with the real thing obtained out-of-band). The MitM machine can go undetected to a real voting server (and even inquisitive client) scrutinizing IP address and routing info, if the MitM machine is appropriately inserted in the network near either the real voting server or the targeted browser, and competently programmed; a university network is ideal grounds for such attack.
In many systems, plain subversion of the machine(s) counting the votes. Having several counting machines run by multiple parties helps, but what should be the rule when they do not agree?
Denial of service; it's easy to prevent voting by attacking the voting server or network infrastructure, and conceivable (especially if observers are allowed) to create some ESD/EMP that zaps the server.
Loss of secrecy of individual votes, threatened by:
penetration of the central computer(s) running the election; that's a problem the industry hardly knows how to tackle when the computer operators are trusted; and in this situation, we'd like not to trust them!
compromise of the voter's device (this is somewhat mitigated by the diversity of devices)
brittleness of web security practices; e.g. consider an https connection used for a "please confirm your vote" page visually showing the ballot selected: if there's a jpg image shown and no special precaution is taken, it is likely that mere analysis of the length of TCP/IP packets reveals the choice made.

Note: there's a simple countermeasure, mitigating 1, 2, 5.2 and 5.3, that I have seldom seen proposed: the voter would key-in a few digits, received secretly, different according to the vote cast. That would largely remove the browser and network from the attack surface. This is not without its own security problems, but the real reason why some proponents of electronic voting dislike it is that it is low tech, and acknowledges the need to distrust high tech in matters of voting.

Addition: any voting system, electronic of not, must balance between two antagonist goals:

Keeping individual votes secret, including to whoever runs the election; because otherwise, individual retaliation could ensue.
Making the outcome convincingly representative of the intention of voters, to as many reasonable persons as feasible; because the elected needs legitimacy.

We can reach either goal by a sacrifice of the other (if all individual votes are made public along the name of the voter as the election goes, the outcome is verifiable; if we choose the election's winner by stone/paper/scissor, voting in one's mind is enough).
Electronic voting complicates both goals considerably, particularly when you consider that whoever runs the election is an adversary (in the sense of that in crypto) trying to breach vote secrecy and accurate vote counting. Simply put, I do not see an even mildly-satisfactory solution.


How to correctly (good practice) generate gpg keys in batch mode (unattended) WITH a passphrase

I finally found the answer by reading the whole manual.
$ man gpg says around line 1944:
--passphrase-fd n
Read  the passphrase from file descriptor n.
and
--passphrase-file file
Read the passphrase from the file.


Doubt on elliptic curve over a finite field and binary representation

I couldn't figure out a field of order, say, 4, 8, 9 or 16. What are examples of such fields?

Let's do that with $8=2^3$.

Elements of that field $\mathbb F_{2^3}$ will be assimilated to $3$-bit quantities, that is the set $\{\mathtt0,\mathtt1\}^3$, or equivalently polynomials of degree less than $3$ with binary coefficients, where e.g. $\mathtt{110}$ is the polynomial $x^2+x$, and $\mathtt{101}$ is the polynomial $x^2+1$.
Our addition is bitwise exclusive-OR, or equivalently addition of polynomials, so that $\mathtt{110}\oplus\mathtt{101}=\mathtt{011}$, or equivalently $(x^2+x)+(x^2+1)=x+1$.
For our multiplication we choose an irreducible_polynomial $P(x)$ of degree $3$ with binary coefficients (among two such polynomials, see this list of irreducible polynomials over GF(2) up to degree 11), e.g. $P(x)=x^3+x+1$; and we define multiplication as polynomial multiplication followed by reduction modulo $P(x)$. This simply tells that when in the product we get a term of degree $d\ge3$, we can get rid of it by adding the polynomial $x^{d-3}\,P(x)\ =\ x^d+x^{d-2}+x^{d-3}$. So for example
$$\begin{array}{lll}(x^2+x)\,(x^2+1)&=(x^2+x)\,x^2+(x^2+x)\\
&=x^4+x^3+x^2+x\\
&\equiv(x^4+x^3+x^2+x)+(x^4+x^2+x)&\pmod{x^3+x+1}\\
&\equiv x^3&\pmod{x^3+x+1}\\
&\equiv x^3+(x^3+x+1)&\pmod{x^3+x+1}\\
&\equiv x+1&\pmod{x^3+x+1}\\
\end{array}$$
thus $\mathtt{110}\otimes\mathtt{101}=\mathtt{011}$.

The full multiplication table goes
$$\begin{array}{c|cccccccc}
\otimes     &\mathtt{000}&\mathtt{001}&\mathtt{010}&\mathtt{011}&\mathtt{100}&\mathtt{101}&\mathtt{110}&\mathtt{111}\\
\hline
\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}&\mathtt{000}\\
\mathtt{001}&\mathtt{000}&\mathtt{001}&\mathtt{010}&\mathtt{011}&\mathtt{100}&\mathtt{101}&\mathtt{110}&\mathtt{111}\\
\mathtt{010}&\mathtt{000}&\mathtt{010}&\mathtt{100}&\mathtt{110}&\mathtt{011}&\mathtt{001}&\mathtt{111}&\mathtt{101}\\
\mathtt{011}&\mathtt{000}&\mathtt{011}&\mathtt{110}&\mathtt{101}&\mathtt{111}&\mathtt{100}&\mathtt{001}&\mathtt{010}\\
\mathtt{100}&\mathtt{000}&\mathtt{100}&\mathtt{011}&\mathtt{111}&\mathtt{110}&\mathtt{010}&\mathtt{101}&\mathtt{001}\\
\mathtt{101}&\mathtt{000}&\mathtt{101}&\mathtt{001}&\mathtt{100}&\mathtt{010}&\mathtt{111}&\mathtt{011}&\mathtt{110}\\
\mathtt{110}&\mathtt{000}&\mathtt{110}&\mathtt{111}&\mathtt{001}&\mathtt{101}&\mathtt{011}&\mathtt{010}&\mathtt{100}\\
\mathtt{111}&\mathtt{000}&\mathtt{111}&\mathtt{101}&\mathtt{010}&\mathtt{001}&\mathtt{110}&\mathtt{100}&\mathtt{011}\\
\end{array}$$
The neutral for $\otimes$ is $\mathtt{001}$ that is the polynomial $1$. The distributive property and other commutative field properties follow from that for polynomials.

The elements of the a binary field of order $q=2^m$ cannot be represented as integers modulo $2^m$.

Actually it's OK to represent them as integers, and even convenient in some computer languages (perhaps our $\oplus$ is just the bitwise-XOR operator ^). But when $m>1$, addition and multiplication modulo $q=2^m$ give the ring $\mathbb Z_q$, which is essentially useless to build the field $\mathbb F_q$, for $\mathbb Z_q$'s addition and multiplication bear no relation with $\mathbb F_q$'s $\oplus$ and $\otimes$.

A convenient way to represent elements of the a binary field of order $q=2^m$ is by means of binary polynomials of degree less than $m$.

Indeed. That's what we did above.

Following comment

If $m=1$ then coordinates over elliptic curve are just scalars, whereas if $m>1$ then a coordinate is in its turn a "set of coordinate".

Yes, that's a useful way of seeing it. An element of the field $\mathbb F_{p^k}$ is most naturally expressed as $k$ "coordinates" each in $\{0,1\ldots,p-1\}$ when devising a general computer implementation of arithmetic in $\mathbb F_{p^k}$. The usual mathematical statement of the same thing is that such element is a polynomial of degree less than $k$, with coefficients in $\mathbb F_p==\mathbb Z_p$.
In the first part of the answer I have specialized to $p=2$, since the question mentioned binary in the title, but we can do the same for any prime $p$, and that makes polynomial notation shine: it implies the definition of addition, and of multiplication with the help of an irreducible polynomial.


Black-Box Zero Knowledge vs Non-Black-Box Zero Knowledge

The difference is to do with the quantifiers on the simulator. Non black-box zero-knowledge says that for all verifiers, there exists a simulator that can simulate a proof of all statements (i.e. there can be one simulator per verifier). Black-box zero knowledge says that there exists a simulator that can simulate a proof of all statements over all verifiers (i.e. there is one simulator total). Therefore, black-box zero-knowledge is the stronger definition of security.

Reference: Lysyanskaya, 2002 (page 31) https://dspace.mit.edu/handle/1721.1/29271


Cracking a key using a combination of partial keys

If you know the probabilities $P(k_1), P(k_2), \dots, P(k_n)$ of candidate keys $k_1, k_2, \dots, k_n$, the fact that the probability mass function $P$ factors into a product for independent subkeys is irrelevant; if you sort the $k_i$ by descending $P(k_i)$ so that the most probable answer is $k_{\pi(1)}$ with probability $P(k_{\pi(1)})$, the second-most probable answer is $k_{\pi(2)}$ with probability $P(k_{\pi(2)}) \leq P(k_{\pi(1)})$, etc., then this minimizes the expected number of guesses because each successive guess covers the maximal fraction of probability mass left unguessed so far.

Specifically, the expected number of guesses is $$\sum_{i=1}^n i\cdot P(k_{\pi(i)}).$$  Any transposition of the weights that puts a higher weight $P(k_{\pi(i)})$ on a larger number $i$ will lead to a higher weighted sum.


This is at least feasible if you allow a one-time setup where related keys are distributed among the $n$ devices and the master device. There is a primitive known as aggregated encryption which has the following properties:

The $n$ devices $(D_0, \cdots, D_{n-1})$ each receive a secret key $(s_0, \cdots, s_{n-1})$.
The master device receives an "aggregated secret key"; concretely, this will in general be $s = \sum_i s_i$.
Each device $D_i$ can encrypt some message $m_i$ with the key $s_i$.
Given $n$ encrypted messages $(E_0,\cdots, E_{n-1}) = (E_{s_0}(m_0), \cdots, E_{s_{n-1}}(m_{n-1}))$ and the aggregated secret key $s$, the master device can decrypt $\sum_i s_i$, and cannot learn anything more.

This is relatively easy to build using cryptosystem with appropriate homomorphic properties. The article I link to builds it from the ElGamal cryptosystem, however there also exists constructions from the Paillier cryptosystem, which will be more suited to your problem.

Now, given such a primitive, there is a natural way to ensure that the master device can learn all messages, but without knowing from which device they come: in the one-time setup phase, also give to each device $D_i$ his secret index $j = \pi^{-1}(i)$ ($\pi$ is a uniformly random permutation of $\{0, \cdots, n-1\}$, $\pi^{-1}$ is the reverse permutation, $\pi^{-1}(i)$ will be the "pseudonymous index" of the device $D_i$). Let $\ell$ be a bound on the size (in bit) of each message $m_i$ (I assume $\ell$ to be publicly known) Then, to send $n$ message while concealing the identity of the device each message came from, each device $D_i$ with message $m_i$ computes and sends:

$E_i = E_{s_i}(2^{\ell\cdot\pi^{-1}(i)}\cdot m_i)$

Given $(E_0, \cdots, E_{n-1})$ and his aggregated key $s$, the master device can only recover

$M = \sum_{i=0}^{n-1} 2^{\ell\cdot\pi^{-1}(i)}\cdot m_i = \sum_{j=0}^{n-1} 2^{\ell \cdot j}\cdot m_{\pi(j)}$

Which is exactly the value $m_{\pi(0)} || m_{\pi(1)} || \cdots || m_{\pi(n-1)}$ (when padding each message $m_i$ with zeroes such that it is exactly $\ell$ bit long), id est, all the messages of the devices in some fixed secret permuted order.

Note that an ElGamal-based scheme would not work here since you need your aggregated scheme to support a very large message space, but the Joye-Libert scheme has no restriction on the message space, and should work fine here.


Why the need to hash before signing small data?

First of all I do not know your implementation, but it seems that you have some basic misunderstandings.

  Signature:  ECDSA(sha256(Data) )

ECDSA is typically implemented in a way that you do not explicitly hash the data prior to passing it to the signing algorithm (but as this might be your own implementation and signing may still work correctly).

  decrypt(Signature) == sha256(data)

In ECDSA signature verification you do not decrypt anything nor compare the hash value of the message with some signature value, but the hash value of the message is used implicitly in the verification relation. So I do not see any chance that your verification will work.

I think you actually read a bad source about RSA signatures which uses the wrong and misleading term "decrypt with public key". This is sometimes used because in RSA the  enryption and decryption function is commutative and thus RSA encryption and RSA signature schemes use the same operations in different order. So you sometimes read instead of signing the term "encrypt with private key" and instead of verifying "decrypt with public key", but you should not use this terminology, as this does not apply to other signature schemes such as ECDSA. Furthermore, due to this way of signing in RSA in the verification you compare the value obtained by performing the public key operation on the signature with the hash value, but also this does not hold for other signature schemes such as ECDSA.

To your next question:

  So if the data, hash function, and public key are known, why is there a need to hash?

If you do not hash the data before signing you cannot have one consistent signature algorithm, because you could only sign messages up to a certain size and if the size of the message gets too large you would need to hash. But that is not a good practice for signature schemes. More importantly, there are signature schemes which can easily be forged when the data is not hashed, such as RSA, see my answer here. In order to have security independent of the size of the signed message, we typically use this hash-then-sign paradigm, i.e., hash the plain message before performing signing operations on it, and thus the signature algorithm works for any size of the message and we do not really have to care about the message size.

So to your final question

  If the same Data with a different nonce is sent over and over, can someone figure out my private key?

If you use a secure digital signature scheme (for instance  ECDSA - which internally hashes the message) and a correct implementation thereof, then you are safe.

  Finally, your last question in context of ECDSA, i.e., would your private key be safe in ECDSA when not using a hash function?

All ELGamal type signatures (ECDSA is one of those) are existential forgable if no hash function is used. Although this does not reveal your private key, it allows everyone to compute valid signatures for messages which you have not signed. Although the adversary has no choice over the message for which the forged signature is computed, don't do that and use the standard ECDSA with hashing.


Why are LMS and XMSS not candidates in the Post-Quantum Cryptography Standardization process?

Can anyone explain why?

That is because NIST specifically stated that stateful schemes were not allowed in the NIST postquantum competition, because they could not be implemented using the API that NIST has defined (which does not allow any state).
That would appear to be reasonable, as stateful hash based signature methods do need extra care to implement safely; NIST 800-208 outlines what NIST believes are reasonable precautions - those precautions are not needed for other algorithms, and hence NIST kept those separate.


How to determine the shift key to decrypt a ciphertext which was encrypted using Caesar cipher?

There are only 26 possible shifts with the Caesar cipher, so you can check them all pretty quickly with a computer, or by hand for fun.

You could also get one step more sophisticated and do a frequency analysis: make histograms of ciphertext letters and compare those to the frequencies of English (e is the most common single letter; followed by t, a...just remember Etaoin Shrdlu and you'll be fine). Then you can do a $\chi$-squared test to compare your ciphertext frequencies to the expected ones from English.

Usual warning: because of how easy this is to break, make sure you only use it for fun: it offers no real security. Here's a longer discussion about cracking ciphers by hand.


Fundamental difference between the constant, key, nonce, and counter bits in Salsa20/ChaCha20 or AES-Encrypt?

Is there a reason specific input bits were chosen for specific purposes? For example, if the some of the counter bit positions and key bit positions were swapped, would this result in a weaker cipher?

No, there would be no real effect on security. The specific positions were chosen primarily to improve SIMD implementation performance. The Salsa20 and ChaCha core functions, ignoring the constant, can be thought of as a $f : \{0,1\}^{384} \rightarrow \{0,1\}^{512}$, so the exact locations for the various bits don't really matter as long as it is secure, which it is thought to be. In fact, the IETF variant of ChaCha uses a different nonce and counter size from the original version by Bernstein (96:32 vs 64:64, respectively).

Note that the positions do have some security implications. Section 3.2 of the ChaCha paper explains how the attacker-controlled words were more spread out in Salsa20 and gave an attacker extra flexibility, but made analysis of the cipher easier. ChaCha, on the other hand, keeps all attacker-controlled words (the nonce and counter, regardless of their size as long as they both sum to 128 bits) on the bottom row of the input matrix. However, the effect on security is extremely small for a standard number of rounds.

  What if we used the constant bits as additional key bits?

Now that would not be a good idea. The constant is important, although the specific value is somewhat arbitrary. Without the constant, an all null key, nonce, and counter would result in an all null keystream block. In theory, a completely random, uniformly-distributed key could be extended to use the counter bits and it would have a negligible chance of resulting in security issues, but that would violate the security properties of the cipher (after all, you'd have to create restrictions as to what a valid key is!).

  What about AES-Encrypt? If we view AES-128-Encrypt as a mapping from 256-bit values to 128-bit values, can we use whichever of the input bits we want for the key and IV without weakening it?

AES is completely different from Salsa20. It is a block cipher, so the IV (which, for most block modes, is nothing more to the cipher itself than an input message) and the key are fundamentally different.


There are two facets in the use of TLS-1.0 with TLS_RSA_WITH_RC4_128_MD5. From a cryptographic point of view:

TLS-1.0, as a protocol, is not broken. It does a number of things in a suboptimal way, forcing implementations to jump through intricate and topologically improbable hoops in order to avoid side-channel leakages. Recent implementations ought to be fine, but of course anything which is deployed is fast becoming non-recent unless it is promptly updated whenever a security fix is published by the vendor.
RC4 has a number of weaknesses, mostly biases which are serious enough to be exploited in practice, if the usage conditions are right (for the attacker). Worst bias is on the second byte of an RC4-generated stream: that byte will have value 0x00 with probability about 1/128 instead of the expected 1/256. Thus, if you send the same secret data at the start of the stream for a few thousands of distinct streams, then the attacker will be able to guess the second byte of that secret data.

If your TLS usage really is HTTPS, then the first few dozens or hundreds of bytes of the stream will be an HTTP header, most of which being non-secret, and the data you want to protect will be subject to less serious encryption biases -- the attacker will need to observe connections by the millions, not the thousands. From an academic point of view, this is still utterly broken; but in practice, this will still be quite hard to leverage for attackers.
MD5 is broken with regards to collisions. In TLS-1.0, MD5 is used as part of HMAC, and right now nobody knows how to attack HMAC/MD5.

From a security point of view, your use of TLS-1.0 with RC4+MD5 is thus probably not a real issue in itself. However, it is a symptom. If you still use such a protocol version and algorithms, then chances are very high that your implementation is an old library which has not been updated in the last decade, thus probably riddled with numerous known vulnerabilities that would allow attackers to simply buffer-overflow it to death. Real-world attackers don't resort to breaking cryptography upfront unless they have no other choice.

Therefore, while using TLS-1.0 with RC4+MD5 is not an immediate danger, it indicates that there are very serious structural issues in your software management procedures, namely that they don't exist. This is what you should strive to fix.

Also, if you handle PII, then chances are that you must comply to some regulations. If conformance auditors see you using TLS-1.0, RC4 or MD5, then they will skin you alive.


Testing the Fortuna random number generator?

Perhaps obvious, but couldn't you download other implementations, design a test set of your own, and run it through multiple implementations to verify the same results?

There are these implementations:

http://sourceforge.net/projects/fortunaprng/
https://github.com/dlitz/pycrypto/tree/master/lib/Crypto/Random/Fortuna

If system entropy is an issue, you might be able to tweak all implementations to fudge the updates to be equal.


Do ciphertexts leak information about their algorithmic creators?

A good block cipher should be indistinguishable from a random permutation (otherwise it is considered broken). A consequence of this is that two good block ciphers are indistinguishable from each other (with at most a doubling of the adversary's advantage).

In your scenario, it means that finding a way to succeed in learning which algorithm has been used implies finding a cryptanalytic attack on at least one of the algorithms you are considering.

[Note that this answer disregard any implementation flaw in your program that would leak the algorithm being used.]


Can we give access to controlled functionality in Fully homomorphic encryption schemes?

This concept is called targeted malleability:

http://crypto.stanford.edu/~dabo/pubs/abstracts/reshom.html

The abstract and introduction of that paper give a good overview of the ideas. In brief, the goal is to ensure that a homomorphic evaluator can only produce a ciphertext by evaluating a function from an "approved" class of functions. It is trivial to achieve this by attaching to the ciphertext a noninteractive proof/argument that it was computed correctly, but this yields a ciphertext whose length is at least linear in the length of the chain of homomorphic operations performed. (This may be acceptable if only a small number of such "hops" are needed.)

The solutions given in the paper instead use succinct noninteractive arguments of correct computation relative to the previous ciphertext in the chain.  This keeps the ciphertext length from growing much, because only one proof is attached to the ciphertext. However, the argument system needs a stronger property of "extractability" (of the previous statement in the chain to be proved) to make this work.


How can Shamir's method for secret sharing work in the GF(256)?

Shamir's secret sharing works in any finite field. A field is a mathematical structure that follows the usual laws of addition and multiplication. A finite field is a field with a finite number of elements, unlike for example the real numbers, which have an infinite number of elements.

Fields exist for all prime powers pk where p is a prime and k a positive integer.

Prime order fields (k=1) are nice because you can use standard modular arithmetic. You add/multiply as usual, and apply the modulo operation in the end.

For other fields operations are slightly harder to understand. If you use simple modular reduction they won't work (e.g. you can't just compute the operations mod 256). Mathematically you use a reduction polynomial. In practice an implementation will use lookup tables.

The most common choices are binary fields with p=2 (including 256 = 28) and prime fields with k=1.


Security relevance of random factor in Paillier

Easy solution is to use a large $r$. You are correct that if the $r$'s were small primes we would have a problem, ergo randomness is essential. However, if the $r$'s are generated randomly then their product doesn't help in guessing one. (Think about guessing $x,y$ random given $x+y$ in an abelian group).


Why does Shamir's Secret Sharing Scheme need a finite field?

The simplest answer is probably to give an example of information leaked when using Shamir's secret sharing over the integers. Assume that we construct a low degree example, defining $q$ to be a linear polynomial with $q(0)=D$ and $q(1)=a_1$. By interpolation you find that: $$q(x)=(a_1-D)x+D.$$

Assume that you are given the share corresponding to evaluation at $2$, i.e. $q(2)$. You can see that $q(2)=2a_1-D$. Since $a_1$ and $D$ are integers, given this single share, you learn the parity of $D$.


Without more context the answer isn't quite precise. In the following answer $\oplus$ always denotes bit-wise XOR.

First let's quickly revisit "plain" cascade encryption. You encrypt arbitrary messages using the keys $K_1,K_2,K_3$ and the encryption algorithm $E$ as follows: $C=E_{K_1}(D_{K_2}(E_{K_3}(P)))$

Now the first possible XOR-cascading construction (more common) is to use three stream-ciphers (or blockciphers in CTR-mode) as follows: $C=E_{K_1}(Ctr)\oplus E_{K_2}(Ctr)\oplus E_{K_3}(Ctr)\oplus P$. This was already recommended by B. Schneier in his Applied Cryptography.

The mode, I think is most likely the one you're looking for, is proven secure in this paper. First you need again the three previously mentioned keys. Secondly you need four more keys of the same length as the blocksize (128-bit for AES-256). Using these additional four keys $l_i$, you encrypt the plaintext $P$ as follows:
$C= E_{K_3}(E_{K_2}(E_{K_1}(P\oplus l_1)\oplus l_2)\oplus l_3)\oplus l_4$.


Small Quantum Signatures - Reality check needed

I see two problems with this idea.

The first problem is Shor's algorithm; that's a quantum algorithm that is able to find the cycle length of a group (and if you can solve that problem, it is easy to factor and compute discrete logs).  In this case, if we define the group of elements defined by the initial start state in the signature, where $H^n$ is the initial state stepped $n$ times (with the group operation defined as $H^a + H^b = H^{a+b}$), Shor's algorithm should be able to find the cycle length of the group, and as you point out, that allows the attacker to reverse the operation.  The only defense I can see it to deliberately select an operation where the above is a semigroup; that is, where the set of elements $H^n$ never come back to the initial state $H^0$, but instead hits a loop later on (and so the first collision $H^x = H^y$ occurs with $x, y > 2^{256}$).  I don't know how you would ensure that.

The second problem I foresee is the mathematical structure that you would need within your PRNG; to be able to compute $H^n$ in $o(n)$ time, you need quite a bit of mathematical structure within your PRNG; I would worry that such structure could be exploited by an attacker.  For example, in your case of multiplying by a noninvertable matrix, I believe that an attacker can just look at the subspace defined by the nonintertable matrix, and effectively step backwards (by looking only for solutions that are within that subspace).  There are methods that appear to be strong against classical computers (e.g. squaring modulo a hard to factor composite), but the ones I can think of run into issues against a Quantum Computer.

Bottom line: I don't believe the idea's quite dead; I do see a number of difficulties in the path.


Password hash that can be upgraded without plaintext password

This is called Client-Independent Update, according to the
Catena paper.

  It is desirable to be able to compute a new password hash (with some higher security parameter) from the old one (with the old and weaker security parameter), without having to involve user interaction, i.e.,
  without having to know the password. We call this feature a client-independent update of the password hash.

The Rig password hash adopted this term:

  Client-independent update: Our design supports client independent
  update, i.e., server can increase the security parameter without knowing the password.

This article even shorts it to CIU.

Battcrypt and Parallel have CIU or are easily modified to have it.
POMELO mentions that you could just run the algorithm twice to get CIU.
Yescrypt seems to have CIU.

An overview:


You want both confidentiality and authenticity. You use e.g. encryption for confidentiality and a MAC for authenticity.

There are a host of problem that you can get if you use the same key for both. (This is imho the canonical example.) So that unfortunately in general means you should use two keys or in other words a combined key of twice the size.

The sentence you quote advertises that given certain other assumptions this is unnecessary for CCM.

For reference:
RFC and
Security proof


Will using a 32 character key for Blowfish make it a 32 bit encryption?

Well, it's a kind of marketing speak.  If you look through the individual entries of this list of block ciphers, you'll see that they are categorised by two distinct parameters.

Block size. This is the number of bits that the cipher operates on at a single time. Blowfish has a 64 bit block.
Key size. Unsurprisingly, this is the length of the key.

These two parameters are somewhat independent, but key length >= block width. Blowfish's key can be up to 56 bytes, and all things being equal, the longer the key the higher the security level. Crypto guys tend to refer to bits though rather than bytes.

With reference to your question, I'd pick the longer number when telling someone about how secure my kit is. Otherwise you have to give out two numbers. You could say Blowfish128 if you want to say anything at all.

PS. Not sure if this matters to you, but the designer of Blowfish recommends using Twofish instead.

PPS. Further to some comments you've had, be aware that cryptographers would assume that your key consists of independently and uniformly distributed bytes, rather than text characters.  Please do not confuse key with password.  An error of understanding here can have very serious consequences for the security of your system.  Your example key is actually  $\operatorname{log_2}(16) \times 32 = 128 $ bits long. Modern crypto really warrants a minimum block width of 128 bits though to prevent various attacks, but that's a call only you can make.


Should I be using PKCS1 v1.5 or PSS for RSA signatures?

Which of these should I be using? PKCS1 v1.5 seems a bit simpler to implement.

Generally you should not be implementing this yourself, there are plenty of libraries that implement these schemes out of the box.
Both the PKCS#1 v1.5 padding for signature generation and PSS padding have pro's and con's which I list below. Which one you decide to use it up to you.

Are there security concerns with each schemes I should be aware of?

PKCS#1 v1.5 padding has the following drawbacks.

It is deterministic, which is not a requirement for signatures and this can actually be detrimental to security in some very specific situations.
It's missing a security proof; PSS has a security proof (for the padding mode, not for RSA itself of course). That said, PKCS#1 v1.5 padding for signature generation has not been broken (unlike PKCS#1 v1.5 padding for encryption, which does have vulnerabilities).

PSS has  drawbacks as well:

it is more complex to implement;
it is definitely not as prevalent as PKCS#1 v1.5 padding - probably because PKCS#1 v1.5 padding is older and hasn't been broken;
it requires configuration (both during signature generation and verification).

If I need to use PSS, what digest should I be using? Is SHA1 a concern if used?

SHA-1 is definitely an issue if you would use it for hashing the message as part of the signature generation (regardless of the padding mode), as it isn't collision resistant anymore. A collision resistant hash is a requirement for signature generation algorithm.

PSS uses another instance of a hash function for PSS padding for a function called the mask generation function (MGF) which performs the actual padding. MGF1 is the only MGF defined for PSS, and it in turn requires a hash to create the PSS padding: the data hash value is input for MGF1.  MGF1 can be compared to HMAC when it comes to security, and SHA-1 is still secure in HMAC.
So SHA-1 isn't a problem if you just use it for the underlying MGF1 used within PSS padding. Of course, for new protocols you'd still go for a more secure cryptographic hash function such as SHA-512.
The two hash functions algorithms can be different than the one used for the data hashing. Some implementations default to SHA-1 and some default to the data hash algorithms. For some reason SHA-256 is often preferred for MGF1 although SHA-512 would make a lot more sense for RSA because it would be more efficient because of its larger output size. As indicated, complexity is a drawback of PSS - even when it comes to configuring the algorithm.
Quite often the hash used in MGF1 it is set to the same hash as used for hashing the message, and that's probably best if you want to remain compatible with most applications & libraries.
If you decide to use PKCS#1 PSS padding, be sure you document the algorithm you use for both the data and the MGF1 function.


Secure way to compare two secret numbers without disclosing them?

Of course there are ways to do that.

See for example, Secure Integer Comparison with Applications in Economics which is implemented in VIFF.

Also, solutions to the millionaire's problem would probably do the trick too. There are lots of these. Just search around for solutions to that problem.


Why is it impossible to find the private key from the public key?

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

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

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

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


Which is the irreducible polynomial in GF(2^256) used in AES256-GCM?

The AES block cipher supports various key sizes of 128, 192, and 256 bits, and a single block size of 128 bits. The degree-8 polynomial $x^8+x^4+x^3+x+1$ is the one used in AES-{128,192,256} for MixColumn and SubBytes.

There is no $\operatorname{GF}(2^{256})$ in GCM because GCM only supports block size of 128 bits. The degree-128 polynomial $x^{128}+x^7+x^2+x+1$ is the one used in GCM.


Term for the ratio of ciphertext to plaintext size?

Ciphertext expansion, or expansion ratio are terms used to indicate this.


Impact of super-polynomial extractors on the security of a zero-knowledge proof

The philosophy behind the extractor and knowledge is that if the prover can generate the proof, then it could itself run the extractor. Therefore, if it can prove, then it knows the witness.
If the extractor runs in super polynomial time, then the prover itself cannot run the extractor. Note that if you took this to an extreme, then in exponential time it is always possible to just find the witness. So, any ZK proof can be said to be a proof of knowledge with an exponential-time extractor. But this is meaningless.
Technically, proofs of security of protocols that would use such a zero-knowledge proof of knowledge would break down.


Adding a Password Hash (key derivation) function to existing password storage solution

Since your HMAC key is held in the same database as the passwords you shouldn't count on it to do anything... If the attackers get the passwords, they get the HMAC key. So HMAC doesn't prevent brute forcing, and a password hashing function would provide both points 1 and 2 above.

Depending on your timeline you may want to consider using whatever function ends up being chosen as the winner of the Password Hashing Competition (https://password-hashing.net/). That's not expected to happen until Q2 this year though, so switching to or adding scrypt, bcrypt, or PBKDF2 in the mean time is probably a good idea.


If the buyer is selecting proxies to use as trusted third parties, presumably the buyer needs to trust that at least one of them is honest and not colluding with the other three.  Therefore, if you need to be sure that they're not colluding, the answer is that the buyer should choose the three proxies to ensure that they're not colluding.

Precisely how to do that depends upon the system and upon what knowledge the buyer has of the proxies.  One scheme is to choose randomly from a list of vetted proxies, and count on the fact that most parties on that list are honest so it's unlikely that you (by chance) happen to pick three that are evil and colluding.  Another is to choose three proxies who have a good reputation or who you have some other reason to trust.  But ultimately, this is not so much a cryptographic question as it is a systems design question for the particular system.

No, end-to-end encryption on its own is not enough to guarantee anonymity.  You need to also use some sort of system designed for anonymity, like Tor, and take other steps to protect your anonymity.


What does the TLS 1.2 client finished message contain?

rfc5246 7.4.9 defines
verify_data as

     PRF(master_secret, finished_label, Hash(handshake_messages))
        [0..verify_data_length-1];

Note the second line; this effectively truncates the PRF output to verify_data_length octets. It goes on to say that verify_data size

  depends on the cipher
        suite.  Any cipher suite which does not explicitly specify
        verify_data_length has a verify_data_length equal to 12.

ECDHE_RSA_AES_128_GCM_SHA256 is defined in rfc 5289 which does not explicitly specify, so this default applies.

Second, someone somewhere is wrong. GCM and CCM ciphersuites do not have a HMAC on the (plaintext) record, although stream and 'block' (CBC) suites do; instead an authentication tag is added to the encrypted record by the AEAD process. Compare 6.2.3.3 to 6.2.3.1 and 6.2.3.2.


Threshold Secret sharing - How to create a shared secret from pre existing secret parts?

I'd like to suggest a potentially interesting reformulation (or variant) of the problem as a form of secure multi-party computation:

  Given $k$, $n$ and $m$, is there a protocol by which $n$ participants $i \in \lbrace 1, \dotsc, n \rbrace$ may, without the help of a trusted external party, each compute a share $s_i$ such that

  there exists a secret $S \in \mathbb Z / m \mathbb Z$ that is uniquely determined by any subset of $k$ shares (and can be efficiently calculated from them), and
  during the course of the protocol, no group of $k-1$ colluding participants can learn sufficient information to allow them to guess $S$ with probability higher than $1/m$?

  Further, if such a protocol does exist, does it require assumptions about the computational capacity of the participants, or can it be made information-theoretically secure like conventional secret sharing schemes?

As Thomas Pornin's answer shows, such a protocol does exist when $k = n$: each participant simply selects $s_i$ independently and uniformly from $\mathbb Z / m \mathbb Z$, with $S \equiv s_1 + \dotsb + s_n \mod m$.  Thomas's answer also shows that, for $1 < k < n$, at least some communication between the participants must be necessary to establish the shares.

Addendum:

There's actually a very simple way to do this.
Each participant $i$ chooses a random element $x_i$ of a finite field $\mathbf F_m$, generates $n$ subshares $y_{i,1}$ to $y_{i,n}$ of it using Shamir's scheme of order $k$, and sends each subshare $y_{i,j}$ to participant $j$.  Each participant $j$ then adds the subshares they receive together to obtain their share $s_j = y_{1,j} + \dotsb + y_{n,j}$.  By the linearity of Shamir's secret sharing, interpolating any $k$ of the shares $s_j$ then yields the secret $S = x_1 + \dotsb + x_n$.

(Edited to incorporate PulpSpy's space-saving suggestion; see comments.)