I guess the answer is no, as long as you are using ECIES then this protocol does not work - you cannot trust the public key of Bob, which is required for ECIES.

You could however use ephemeral-static Diffie-Hellman, using ECDH as cryptographic algorithm. Alice would supply the static part as her public key is trusted, Bob may use any key pair. That means that Bob can trust Alice, but not the other way around. This may however be sufficient for some protocols (TLS normally does not perform client authentication either).

Of course, you may just as well use a static key pair for Alice instead of randomly generating it again and again, requiring to set up trust for each key pair creation.


Why can't the IV be predictable when its said it doesn't need to be a secret?

The requirements for an IV depend on which encryption algorithm you are using (AES is not an encryption algorithm by itself, since it can only act on 16-byte strings, but it can be used as a building block in a variety of different encryption schemes), specifically on the mode of operation.

Roughly speaking, the role of the IV is to insert some "new" randomness into the process each time a message is encrypted. That way, the same message encrypts to a different ciphertext each time, and similar messages to not result in similar ciphertexts. This is the reason why IVs often need to be random, but never need to be secret.

To answer your questions:

IVs do not need to be secret. In fact, they are often considered part of the ciphertext, and it is assumed that in adversary will see them.

Predictable IVs can sometimes be harmful. If you are using AES inside of Counter mode (CTR) encryption, predictable IVs are fine (the IV acts as a counter that gets incremented with each 16-byte block you encrypt; the important point here is that a counter value should never be repeated). On the other hand, if you are using Cipher Block Chaining mode (CBC), a predictable IV can allow some chosen-plaintext attacks. Preventing this is usually considered the ideal goal of an encryption scheme, since it implies the attacker can't do other, more harmful, things. Depending on the specific context, predictable CBC IVs can definitely cause problems.

Hashing doesn't necessarily make IVs more unpredictable. Hashing an otherwise predictable IV can make it look "more random", but where are you getting the salt and pepper? If these are also predictable, then hashing hasn't gained you anything. If they are random, then why not use this random number generator to make your IV directly?

You can play it safe by always generating random IVs. This can be "overkill" for algorithms such as CTR mode, but it will still be safe.

For more information:

Blockcipher modes of operation (Describes CBC, CTR, and some others)
Initialization vectors

Based on my understanding of what you're doing (I'm not to clear on the details), I'd recommend that whenever you update or create a row, generate a new, random IV for that row, and then use that IV for the encryption. The IV can be concatenated to the ciphertext, or stored in a separate location.

If storing IVs is impractical, a better alternative to hashing would be to use a second key $K$ to generate IVs; for example, the IV for row i could be $\textrm{AES}_K(i)$ or $\textrm{HMAC-SHA256}_K(i)$. The reason for this is that hash functions are not the same thing as pseudo-random functions from a cryptographic perspective, and so hashing something doesn't really give you a random IV. This approach is not secure if you need to update rows (or rather, if an adversary could potentially see two different ciphertexts for the same row), since repeating an IV is bad, bad, bad.


How to calculate RSA Key Size correctly starting from 384 bits to 15360 bits or beyond 15360 bits

Oh, that one is simple: any key size is possible. The key size for RSA is set to the size of the modulus. The modulus in turn is the multiplication of two (or more) large primes. Of course, multiplication means that all prime sizes are added together (give or take a bit).

However, not every implementation will allow any key size. Since computers are byte oriented, in general the key size needs to be a multiple of 8. That makes encoding the key values easier, for starters. Quite often the numbers are calculated using words, so a 32 bit of 64 bit increment is also not uncommon. Finally, if just to avoid over-extensive testing, an implementation may also decide to just allow some specific key sizes.

Generally there is also some lower limit, if just to avoid completely insecure choices like 128 or 256 bit RSA. Creating an upper limit also makes sense, because key pair generation of 16Kib RSA keys or higher is nothing to sneeze at (and, not counting quantum cryptography, that provides a 256 bit security margin anyway).

If I remember correctly Microsoft's native RSA implementation uses 32 bit increments for the key sizes, although there are of course multiple API's and implementations of these API's (managed and unmanaged). But in the end you have to look it up, and even then changes may happen (such as upping the minimum bound or allowing more key sizes).

For common key sizes, try 2048 (on the small side), 3072 (2048 + 1024) and 4096 bits. Almost all implementations will support those key sizes and there is really not much need to choose an intermediate value, except for niche purposes (smart cards). RSA with bit size 1024 is not recommended anymore and may well be prohibited by some implementations.


For example, if $M = M_1 || M_2 || \ldots || M_n$, compute
$\operatorname{CMAC}(\operatorname{CMAC}(M_1) || \operatorname{CMAC}(M_2) || \ldots || \operatorname{CMAC}(M_n))$

If we assume that the attacker cannot find two distinct messages $M_1, M_2$ with $\operatorname{CMAC}(M_1) =\operatorname{CMAC}(M_2)$ (which he is unlikely to if the number of messages being MAC'ed is considerably below $2^{64}$), then you're good.
That is, if the attacker is able to produce a message/MAC pair that validates with this construct, then either:

He is able to construct a message/MAC pair for CMAC which we hasn't previously observed; that is $CMAC( M' )$, where $M' = \operatorname{CMAC}(M_1) || \operatorname{CMAC}(M_2) || ... || \operatorname{CMAC}(M_n)$ which he has not previously observed, or

He finds a collision $\operatorname{CMAC}(M_i) = \operatorname{CMAC}(M'_i)$ (and reuses a top-level CMAC he has observed)

(Note that this initial analysis does not consider the possibility of an interaction between the bottom-level and top-level CMAC's, where the attack has actually observed the message $M'$ in one of the bottom level MACs; a full proof would need to address that)

Would it be better to use a XOR operation instead?
$\operatorname{CMAC}(\operatorname{CMAC}(M_1) \oplus \operatorname{CMAC}(M_2) \oplus \ldots \oplus \operatorname{CMAC}(M_n))$

That's far worse; consider the MAC of the message $M_2 || M_1 || M_3 || M_4 || ... || M_n$


Are "private keys" in the context of diffie-hellman refer to the private $a$ and $b$ that Alice and bob privately select respectively?

Yes, correct. Similarly, $A=g^a\bmod p$ and $B=g^b\bmod p$ are also called the "public keys".

What is considered an exchange? A session of information exchanging between to parties?

An exchange is an execution of the Diffie-Hellman protocol. This happens whenever either a party feels like it or a party has forgotten the resulting shared secret from the last execution. In the context of the internet this usually means that if you connect to, say, Stack Exchange today it will run a Diffie-Hellman exchange. Then when you shutdown your computer it will "forget" the resulting shared secret $K$ and tomorrow when you connect to Stack Exchange again, it will have to run another Diffie-Hellman exchange.

If so, does static DH refer to exchanges between the same two parties?

In a static exchange usually both parties always reuse their private keys, which implies that if they re-run the Diffie-Hellman exchange more than once with each other they always get the same shared secret $K$.
Indeed getting a shared secret the same shared secret between Alice and Bob and Alice and Charlie has a negligible probability if everyone involved picked their private keys properly and the protocol was followed.


That issue is not really relevant when one implements such schemes, because the plaintexts are typically used only in the encryption, where they are combined with big values that need to be encoded as big integers anyway.

All the homomorphic operations should not depend on the plaintext, so, the chosen encoding is irrelevant here.

And even if the decryption outputs a single bit, all the operations done in the decryption function are performed also over big integers.

As an example, the scheme implemented by Leo Ducas uses a regular C integer to encode input bits, as you can see in lines 29 and 30 of file LWE.h from his Github repository.


What could be the keylength of a DES encryption?

DES has a 56-bit key in 8-bytes. The length of the output depends on the length of the input, mode and padding, not the key.

Note: The LSb (least significant bit) of each key byte is reserved for parity, depending on the DES implementation parity may or not be checked.

See: Data Encryption Standard.


Summing up and fleshing out the comments: Generally, signing software updates is good practise and should definitely be done. However, you ask about the security of an unpadded RSA signature on an MD5 hash. There are at least two issues with this:

MD5 security

MD5 is no longer considered safe, and hasn't been for quite a while (we're already phasing out its successor, SHA-1, in favor of SHA-2 and eventually SHA-3). MD5 has been broken for a while, and in ways that make it unsuited for signatures. Edit: My old explanation was wrong. See the comments by @Gilles and the answer by @fgrieu for the details of why MD5 is bad. The conclusion of "don't use it" still stands.

Solution: Use SHA-256 or another up-to-date hash algorithm instead of MD5.

Unpadded RSA signatures

If you sign the hash with a primitive RSA signature without any padding, you can attack the scheme as described in this question and answer. This would, again, allow an attacker to forge a message with a valid signature. Even when using SHA-256 instead of MD5, the security margin is too low for comfort.

Solution: Use a proper padding like PKCS#1 v1.5 or, even better, PSS.

General remarks

Please consider using an established method and (ideally) implementation for this purpose. Take a look at how other systems do this. Even though the potential attacks mentioned here may seem like they would not apply to your use case, it is bad practise to use methods you know to be insecure, just because you think the insecurities may not apply to your specific system. Using good algorithms and padding has almost no additional cost, but gains you the peace of mind that your system is secure, instead of "probably secure because the attacks probably do not apply to it, I hope".

Finally, the standard caveats about "don't implement the crypto yourself, use an established library" apply, and this question has a large number of good answers concerning best practises for cryptography and can serve as a good starting point for further research.


Zero-knowledge authentication to commercial VPN

A modern approach might be to use blinded tokens like PrivacyPass based on a VOPRF.  There are two parts to the protocol: an OPRF to negotiate blinded tokens with a payment that can later be redeemed for service, and DLEQ proof to verify that the tokens are unlinkable.

VOPRF, verifiable oblivious pseudorandom function family.  This is a combination of a series of related concepts:

A PRF or pseudorandom function family is a family of functions $F_k$ that is hard to distinguish, if $k$ is chosen uniformly at random, from a uniform random function.  In other words, for distinct $x$, $F_k(x)$ appears to be independent uniform random to anyone who doesn't know $k$.

(PRFs are ubiquitous in cryptography.  Typical examples: ChaCha, AES, HMAC-SHA256.)
An OPRF or oblivious PRF is a protocol by which a client and a server jointly compute a PRF using a key known only to the server and an input known only to the client, so that the client learns $F_k(x)$ but not $k$, and the server learns nothing.

(OPRFs are used in protocols like the password-authenticated key agreement OPAQUE (paywall-free preprint).)
A VRF or verifiable PRF is a public-key cryptosystem for computing a PRF $F_k(x)$ giving a value $v$ together with a proof $\pi$ so that (a) without knowledge of the public key, $v$ is indistinguishable from uniform random (i.e., $F_k$ is a PRF to anyone who doesn't have the public key and $\pi$), but (b) with knowledge of the public key, a verifier can use $\pi$ to confirm that $v$ is the unique output of $F_k$ on $x$.

(More on VRFs, and an application in DNSSEC.)
Finally, a VOPRF or verifiable OPRF is a protocol by which a client and a server jointly compute $v = F_k(x)$ and give the client a proof $\pi$.  Then even the server—with knowledge of the public key, $k$, and $\pi$, but not $x$—can't distinguish $v$ from a uniform random string, but the client can verify with $\pi$ and the server's public key that $v$ is in fact the unique value of $F_k$ at $x$.

How does it work?  Here's the OPRF used by PrivacyPass—ignoring the ‘verifiable’ part for the first approximation.  Fix a group $G$ of prime order (written additively) with standard base point $X$, and fix hash functions $H_1\colon \{0,1\}^* \to G$ and $H_2\colon G \to \{0,1\}^n$.  A public key is a group element $Y \in G$ and a private key is the secret scalar $k$ such that $Y = [k]X$.  The PRF is $$t \mapsto H_2(t, [k]H_1(t)).$$  The client and server jointly compute it as follows:

  PrivacyPass OPRF.

  Client picks a secret bit string $t$.
  Client picks a secret blinding scalar $r$ uniformly at random, and sends $P := [r]H_1(t)$ to the server (along with, say, a payment for purchase).
  Server, given $P$, sends $Q := [k]P$ back to the client.
  Client, given $Q$, reverses the blinding scalar $r$ to compute the group element $$[r^{-1}]Q = [r^{-1} k]P = [r^{-1} k r]H_1(t) = [k]H_1(t).$$
  Client finally computes the bit string $z := H_2(t, [r^{-1}]Q) = H_2(t, [k]H_1(t))$.

(The client could alternatively do additive blinding: send $P := H_1(t) + [r]X$ to the server, and use $z := H_2(t, Q - [r]Y)$, like OPAQUE does.  The two provide essentially equivalent security.  Multiplicative blinding requires computing scalar inverses, which may be a little expensive.  Additive blinding requires, well, computing addition, so it can't be used with, e.g., $x$-restricted scalar multiplication only like X25519—although X25519 can't be used directly anyway because it's not a prime-order group, and we'll want addition later on for the DLEQ proof of anonymity.)

How do we use an OPRF in a purchase and redemption protocol?

  Purchase.  The user picks a secret $t$ and sends a blinded token request $P$ for it together with a payment in order to purchase service, and the server—on confirmation of payment—returns a blinded token $Q$, computed with its private key $k$.  The user then unblinds $Q$ and combines it with $t$ to obtain a token $(t, z)$.

  Redemption.  The user then redeems a token $(t, z)$ to authenticate a request for service $m$ by sending $(t, \operatorname{MAC}_z(m))$ as an authenticator for $m$.  The server recomputes $z = H_2(t, [k]H_1(t))$ using the private key $k$ to verify the authenticator, and keeps a database of spent tokens $t$ to prevent replays; the server can also periodically—say, weekly, or monthly—rotate the public key so that the spent token database doesn't accumulate indefinitely.  If the token is unspent and the authenticator matches, the server provides the service.

This protocol guarantees that the client is unable to forge tokens, no matter how many tokens they've already acquired from the server, and guarantees—if the server follows the protocol and uses a single key for every client—that the tokens submitted by each client are indistinguishable from one another to the server.

But wait!  How do we know that the server doesn't use a different key for every client, enabling the server to track clients from purchase to redemption?  We need a way for the server to prove to the client that the tokens are made with the same private key $k$ each time.  This is where the verifiable part of the VOPRF comes in, using a zero-knowledge proof of discrete log equality.

DLEQ proof, a receipt for a non-interactive zero-knowledge proof of discrete log equality.  A DLEQ proof is a proof that two group elements $Y, Q \in G$ have the same discrete log with respect to two bases $X, P \in G$: $\log_X Y = \log_P Q$.  In other words, that $Y = [k]X$ and $Q = [k]P$ for the same $k$.

We start with an interactive zero-knowledge proof by a $\Sigma$-protocol due to Chaum and Pedersen between a prover and a verifier who share $(X, Y, P, Q)$ a priori:

  Chaum–Pedersen interactive zero-knowledge proof of discrete log equality.

  Prover picks a uniform random per-session secret $u$, and commits to it by announcing $A := [u]X$ and $B := [u]P$.
  Verifier picks a uniform random scalar $c$ to challenge the prover.
  Prover answers the challenge by returning $s := (u - c k) \bmod \ell$, where $\ell$ is the order of the group $G$.

  Verifier accepts if $A \stackrel?= [s]X + [c]Y$ and $B \stackrel?= [s]P + [c]Q$.

Using a hash function $H_3$, with the Fiat–Shamir heuristic we can turn this into a non-interactive zero-knowledge proof system that gives a verifiable receipt, much like the Schnorr signature scheme is derived from the Schnorr identification protocol:

  Chaum–Pedersen non-interactive zero-knowledge proof of discrete log equality.

  Prover picks a uniform random $u$ and computes $A := [u]X$ and $B := [u]P$.
  Prover computes challenge $c := H_3(X, Y, P, Q, A, B).$
  Prover computes $s := (u - c k) \bmod \ell$ and returns $(c, s)$ as receipt.

  Verifier accepts if $c \stackrel?= H_3(X, Y, P, Q, A', B')$ where $A' := [s]X + [c]Y$ and $B' := [s]P + [c]Q)$.

We can even efficiently extend a short receipt $(c, s)$ to work on a batch of discrete log pairs $\{(P_i, Q_i)\}_i$ by hashing $(X, Y, \{(P_i, Q_i)\}_i)$ into a sequence of challenges $\{c_i\}_i$, deriving $P' := \sum_i [c_i]P_i$ and $Q' := \sum_i [c_i]Q_i$, and then doing the one-point DLEQ proof on $(X, Y, P', Q')$.

Batch DLEQ proofs are important if you want to allow a single payment to purchase many unlinkable instances of service at once—like exchanging one robot overlord training session for the high privilege of just reading the fucking newspaper without having to do another robot overlord training session for every newspaper you want to read, as is the dominant application of PrivacyPass with the global active adversary Cloudflare: to reduce $n$ captchas down to one captcha.

Armed with a DLEQ proof technique by which to turn an OPRF into a VOPRF, the server can now commit to a public key $Y$ relative to the standard base point $X$ in some very public verifiable space (e.g., a well-known URL like https://www.example.com/tokenkey that the user fetches through Tor), and prove to the user that the tokens are unlinkable with a minor variant of the purchase protocol:

  Purchase with proof of anonymity.  The user picks a secret $t$ and sends a blinded token request $P$ for it together with a payment in order to purchase service, and the server—on confirmation of payment—returns a blinded token $Q$, computed with its private key $k$, together with a DLEQ proof that $\log_X Y = \log_P = Q$.  The user then unblinds $Q$ and combines it with $t$ to obtain a token $(t, z)$.

  Before redeeming the token, the user verifies the DLEQ proof; if it fails, the user tells all their friends that the server is a lying sack of gastrointestinal distress and loudly demands to speak to the manager of the cryptocurrency scam by which they bought their tokens.

By the way, you could also just use Tor.


As in the linked question, what you are missing is that the simulated view for a given input pair must be indistinguishable from the simulated view for the same input pair.

So if $A$'s input $s$ is $0$, then the real view of $B$ will be $0$ with probability $1$. On the other hand, if your simulator just chooses a uniform bit, the simulated view of $B$ will be $0$ with probability $1/2$. That's distinguishable, so your simulator doesn't work. (Same if $s=1$ of course.)

A slightly more involved argument shows that any simulator will have the same issue, so there is no suitable simulator, and the protocol is not secure.


Should I use a self-designed Block Cipher Mode of Operation?

Similar concerns apply as to any self-designed cryptographic algorithms. Standard block cipher modes usually have security proofs. If yours does not then even if it seems correct you may be missing some weakness.

An example of where security proofs of cipher modes are clearly important is the CCM mode (pdf). The same cipher key is used both for CBC-MAC authentication and to produce the CTR blocks used for encryption. This key-reuse is generally a bad idea and in a home-baked mode could be a weakness, but is proved safe in the particular composition used.

Very simple modes may be easy to prove secure yourself. However, I doubt those have any real advantages over using a standard mode either.


Efficient Symmetric Mutual Entity Authentication Protocol

Please refer the well-known handbook of applied cryptography by Menezes et al.,you may find many symmetic key-based mutual authentication protocols (in Chapter 10), and more important, some pointers to the standards, e.g. ISO/IEC 9798 et al. Wish it helps.


Formal definition of "explicit" algorithm?

What Dan Boneh says is not a formal definition as you want it. Let me quote Rogaway on this:

  In cryptographic practice, a collision-resistant hash-function (also
  called a collision-free or collision-intractable hash-function) maps
  arbitrary-length strings to fixed-length ones; it’s an algorithm
  $H:\{0,1\}^*\rightarrow \{0,1\}^n$  for some fixed  $n$ (we
  momentarily assume a message space of $\{0,1\}^*$. But in
  cryptographic theory, a collision-resistant hash-function is always
  keyed; now $H:\,\mathcal{K}\times\{0,1\}^*\rightarrow \{0,1\}^n$,
  where each $K\in\mathcal{K}$ names a function $H_K = H(K,\cdot)$ (This
  formalization assumes a concrete-security framework.) In this case $H$
  can be thought of as a collection or family of hash functions
  $\mathcal{H} = \{H_K:\:K\in\mathcal{K}\}$, each key (or index)
  $K\in\mathcal{K}$ naming one. (Note that we call $K$ a key but it is
  not secret; it will be chosen from $\mathcal{K}$ and then made
  public.)

  Why should theoretical treatments be keyed when practical
  constructions are not? The traditional answer is that a rigorous
  treatment of collision resistance for unkeyed hash-functions just
  doesn’t work. At issue is the fact that for any function
  $H:\{0,1\}^*\rightarrow \{0,1\}^n$ there is always a simple and
  compact algorithm that outputs a collision: the algorithm that has one
  “hardwired in.” That is, by the pigeonhole principle there must be
  distinct strings $X$ and $X_0$ of length at most $n$ such that $H(X) = H(X_0)$, and so there’s a short and fast program that outputs such an
  $(X, X_0)$. The difficulty, of course, is that us human beings might
  not know any such pair $(X, X_0)$, so no one can actually write the
  program down.

  Because of the above, what is meant when someone says that a hash
  function $H:\{0,1\}^*\rightarrow \{0,1\}^n$ is collision resistant
  cannot be that there is no efficient adversary that outputs a
  collision in $H$. What is meant is that there is no efficient
  algorithm known to man that outputs a collision in $H$. But such a
  statement would seem to be unformalizable — outside the realm of
  mathematics. One cannot hope to construct a meaningful theory based on
  what humankind currently does or does not know. Regarding a hash
  function like SHA-1 as a random element from a family of hash
  functions has been the traditional way out of this quandary.

Rogaway then demonstrates that even though it is not possible to formally define the collision resistance, it is possible to formally define the requirement for a collision resistant hash function by a higher-level protocol or a construction. This is done by a reduction that shows that if someone can break the protocol in a certain way, then he is able to find a collision for the underlying hash function. This allows to consider the protocol secure as long as collisions have not been explicitly found.


How to prove secret value in Pedersen commitment is equal to secret value in Fujisaki commitment?

This may look like a homework, so I would not present any complete "Ctrl-C Ctrl-V" -style solution.

A proof for equality of logarithms was introduced at Chaum, Evertse and van de Graaf paper, "An Improved Protocol for Demonstrating Possession of Discrete Logarithms and Some Generalizations", Eurocrypt 1987. At the core, Prover shows that the same single response would open both commitments.

According to http://kodu.ut.ee/~lipmaa/crypto/link/commitment/,
Fujisaki-Okamoto commitment scheme (spelling warning) is somewhat similar to Pedersen.
Major difference is operating with a group of an order hidden from Prover, which makes it acceptable to commit to integers (not only elements of a field of residue classes modulo prime group order).
This difference does not prevent from using the same response, as was stated.

Having said this, I would encourage to do it yourself.


Is it practical to use a stream cipher in a block cipher mode?

The way you propose to use a stream cipher as a drop in replacement for a block cipher is flawed, as the other answer explains nicely.

There is a simple way to convert a stream cipher into a block cipher. In pact, it works for any PRF, regardless of if it is reversible or not.

This presentation perfectly covers how to use a PRG such as a stream cipher to construct a block cipher.

Basically, you use the stream cipher in the following manner:

Take your message m and break it down into an n-bit binary string.

Take your stream cipher $G(k)$ and use it to generate a a stream of length $2 · |k|$. So $G(K) \to K^2$ (output space = double that of keyspace).

Do $k \to G(k)[0]$ and $G(k)[1]$, pick $G(k)[x]$ depending on what the first bit of m is.

Then, compute $G( G(k)[x] )$. You have a message of length two blocks, pick the block corresponding to the second bit of m. Repeat n times.

This can be reversed (decrypted) in the same way Feistel networks are, via the Luby-Rackoff theorem.


This answer has been updated a lot, again, after being accepted. I now base my analysis on simple functional equivalent source code to the deterministic PRNG used.

The cryptosystem proposed works, in the sense that it allows decryption. The best cryptanalytic method there is to predict further output is enumerating the 64-bit key by brute force. That's in the realm of feasible for a governmental organization: testing a key guess merely requires computing the SHA-1 of the key; then the SHA-1 of that; and comparing to the first 20 octets of known pad. Modern suitable resources are GPUs, FPGAs, or ASICs. I'm told that some commercial GPUs do 2.6G SHA-1 per second. That allows testing like 1.3G keys per second per GPU. On a farm of 1000 such GPUs, an attack is expected to last less than 3 months. I expect that a competent standard-cells ASIC design allows to improve that by a factor like 100 at constant power and cost, disregarding NRE that can be amortized over multiple other projects with similar requirements, such as password search, an industry that siphons untold budgets and power.

On first reading of Java's specification for SecureRandom, I thought that the proposed scheme would not allow decryption by the legitimate key holder, because of the "SecureRandom must produce non-deterministic output" fragment of that specification. However it turns out this is not a promise to a user, but a constraint, implying that "any seed material passed to a SecureRandom object must be unpredictable". My guess is now that the design intend is that the generator is deterministically seedable for conformance testing, and is seeded with true random in normal use, including automatically when not explicitly seeded.

SecureRandom does not by itself define either an algorithm or implementation, it is designed to support various named algorithms and allow access to various crypto-providers (such as HSMs, Smart Cards, or native OS implementations), with a default software-only crypto-provider implemented by an unspecified combination of Java bytecode on top of a JVM and possibly native primitives. As documented, SecureRandom's constructor "traverses the list of registered security Providers, starting with the most preferred Provider. A new SecureRandom object encapsulating the SecureRandomSpi implementation from the first Provider that supports the specified algorithm is returned".

I have experimentally verified that on a default installation of jdk-7u51-windows-x64, new SecureRandom() and SecureRandom.getInstance("SHA1PRNG") are the same deterministic generator when deterministically seeded before having produced any output (and appear non-deterministic whenever they have been used unseeded). The pseudo-random pad used in the question (which first 100 octets are known in the context) are as produced by:

// Produce a pseudo-random pad from a key using "SHA1PRNG" of the default provider,
// (which also is the default SecureRandom algorithm)
private static void orgSHA1PRNG (byte key[], byte pad[]) throws GeneralSecurityException {
    SecureRandom rng = SecureRandom.getInstance("SHA1PRNG"); // or: = new SecureRandom();
    rng.setSeed(key);
    rng.nextBytes(pad);
    }

Based on the source code available here, I wrote a minimal piece of Java code that I verified produces the same output:

// On a default install of jdk-7u51-windows-x64, the following is equivalent to
// orgSHA1PRNG above, with reference only to SHA-1. Distilled from code found at
// http://www.docjar.com/html/api/sun/security/provider/SecureRandom.java.html
private static void eqvSHA1PRNG (byte key[], byte pad[]) throws GeneralSecurityException {
    // initial state is the SHA-1 hash of the key
    byte state[] = MessageDigest.getInstance("SHA").digest(key);
    // while there is output to produce..
    for(int j=0; j<pad.length+19; j += 20) {
        // compute new output as the SHA-1 hash of the current state
        byte hash[] = MessageDigest.getInstance("SHA").digest(state);
        // copy the hash (possibly truncated) to the pad
        for( int i = j+20<pad.length?20:pad.length-j; --i>=0;)
            pad[j+i] = hash[i];
        // The documented INTEND is to perform
        //    state = (state + output + 1) % 2^^160,
        // with an increment of the first octet of state if the whole state is unchanged.
        // This is performed considering variables as little-endian, and with a minor
        // mess in carry propagation, due to the signedness of the  byte  type in Java.
            int c = 1<<8;     // turns into the + 1 of the above formula
            boolean z = true; // true when state is unchanged
            for (int i = 0; i < 20; i++) {
                c = (c >> 8) + state[i] + hash[i];  // partial result; can be negative !
                byte t = (byte)c;                   // truncation to byte
                z &= state[i]==t;                   // z becomes false when state changes
                state[i] = t;
                }
            if (z)          // occurs with low odds
                ++state[0];
        }
    }

Simplified pseudo-code:

compute state = SHA-1(key)
while output is needed

compute hash = SHA-1(state)
use hash as up to 20 additional output octets
state = state $\boxplus$ hash
if the previous operation did not modify state, then

increment the first octet of state.

where $\boxplus$ is some internal law on the set of 20-octet strings, remotely similar to addition $\bmod 2^{160}$ (the neutral element is the all-0xFF octet string, and most importantly a = x $\boxplus$ b always has a unique solution; $\boxplus$ is commutative; I'm uncertain about if $\boxplus$ is associative, but that's of secondary importance). More precisely, $\boxplus$ is addition performed by scanning octets from first to last (that's the reverse of addition within 4-octet words in SHA-1), and with a carry that is initially 1 then either -1, 0, or 1 (because the octets are considered signed two's complement). This is odd, but unlikely to introduce a cryptanalytic weakness.

There are two obvious weaknesses (none of them really exploitable in the context of the question):

the generator enters a cycle with odds $p\approx(b/20)^2\cdot2^{-161}$ after $b\ll2^{84}$ octets;
there is an attack recovering the state (thus allowing prediction of future output) with odds $p$, from $b\ll2^{84}$ octets of output, with expected effort less than $p\cdot2^{161}\cdot20/b$ hashes, and less than $b$ octets of memory.

The attack sketch goes:

from the $b$ octets of output get $\lfloor b/20\rfloor$ values of hash and organize that for quick search
repeat

choose an arbitrary state (an incremental counter works)
if SHA-1(state) is among the hashes

if SHA-1(state $\boxplus$ SHA-1(state)) is among the hashes

stop and output the guess state, which is correct with overwhelming odds.

I'm critical on the rationality of testing that state did not change (except, perhaps, when considering the possibility of malicious reseeding, using means not shown here), for that test and associated action does not significantly decrease the odds of entering a cycle (it only makes it impossible to enter a cycle of length 20, 10, 5, 4, 2, or 1 octets).

Even accounting for the known weaknesses of SHA-1, brute force for keys significantly less than $16$ octets might remain the least inefficient purely cryptanalytic attack for decades, considering $b=100$ in the question's statement. I'm discounting attacks on implementation, like compromise of the software integrity, side channels, and induced faults.

A quick search on SHA1PRNG returned an analysis report of 2009 (in French) hosted by usually serious officials, studying Java SE 6, with mention of substandard cryptographic post-processing and unexplained statistical anomalies in SHA1PRNG of the default Sun provider, reportedly detected using a standard entropy test of 500 MB output; leading to a JAVASEC rule #36 intended to mean: the developer should not use SHA1PRNG of the Sun Provider. I second the substandard cryptographic post-processing, but conjecture that the unexplained statistical anomalies are an artifact of the test method (the other option is that a standard entropy test managed to distinguish SHA-1 from a random function, which is next to unbelievable).


How does the security of Elliptic curve compare to normal discrete logarithm?

As far as I know the best choice is a 'safe prime' with $P=2q+1$ with $q$ a prime as well.

This is the best choice for a given size of $P$, but not for a given size of $q$. See this.

This discrete logarithm can be solved in $\mathcal{O}(\sqrt{q})$ with q the biggest prime factor (with Pollard's (Rho) algorithm).

Essentially yes (minor caveat: $\mathcal{O}(\sqrt{q})$ is not effort, but the number of multiplications of integers of size $P$, with $P>q$, hence the effort grows faster by a factor at least $\ln P\,\ln\ln P$). That the DLP can be solved with such method and effort does not imply that such method or effort is needed. And if $P$ is a safe prime, there are methods (including the Number Field Sieve) requiring less effort. Again, see this.

Do (DLP in a subgroup of an appropriate Elliptic Curve on one hand, of $\mathbb Z_P^*$ on the other hand) have the same solving time of $\mathcal{O}(\sqrt{q})$ (group operations, where prime $q$ is the order of the subgroup)?

Yes, when using Pollard's Rho algorithm. That algorithm is believed optimum in the Elliptic Curve case, and for $P$ large enough in the $\mathbb Z_P^*$ case.
No, when $P$ is a safe prime (and large enough to make the DLP non-trivial), and using the Number Field Sieve to tackle the DLP in the subgroup of $\mathbb Z_P^*$.

Note: I don't know that the Number Field Sieve can be used to solve the DLP in an appropriate Elliptic Curve (sub)group; and it would come as a huge surprise if it was more efficient than Pollard's Rho algorithm.


How does linear vs. non-linear operations relate to cryptographic security and differential cryptanalysis?

If you have a linear function $F$ then the output difference corresponding to
the input difference $d$ is
$$
F(x\oplus d) \oplus F(x)=F(x)\oplus F(d) \oplus F(x)=F(d),
$$
for any value  of $x,$which is a devastating differential characteristic holding with probability one.

You can take $F$ to be an sbox, or a parallel set of sboxes which make up part of a round. Iterating, you can get a differential characteristic with probability one for the whole cipher since differential characteristics are independent of key addition. This completely breaks the cipher.

Now let $n$ be the input and output bitlength of $F$ and let $F$ be a nonlinear permutation  i.e., a proper sbox. The goal is to have many different output differentials, each holding with small probability, corresponding to each input differential.

The best possible case is that each output differential which holds occurs for exactly $2$ out of $2^n$ $x$ values. Note that in binary the output differential corresponding to some $d$ and a fixed $x$ also occurs for $x'=x\oplus d,$ i.e., they come in pairs.

Such a function is called almost perfect nonlinear (APN) but exists only for $n$ odd, thus is not much used since sboxes of byte or multiple byte or nibble length are popular. AES snoxes have maximal differential characteristic probability $2^{2-n}$ instead of the optimal $2^{1-n}$ which an APN sbox would give.


Encrypt-then-HMAC implementation - am I doing it right?

PBKDF2 alone would be bad for step 4, since the blocks of its output can

trivially be computed independently.  If the PBKDF you use can't directly

produce enough output, then you should compose with a fast key-based KDF.

Make sure that

the IV is part of step 9's ciphertext
and
step 5 of decryption is constant-time

.


Digital Signing algorithm for a fixed set of private and public keys in broadcasting like system?

There is a lot of confusion in the question:

message encryption is performed to achieve confidentiality, it is performed using the public key of the receiver's key pair (the public key needs to be trusted by the sender);
message signing is performed to achieve authentication and integrity of messages, it is performed with the private key of the sender's key pair (the public key needs to be trusted by the receiver);

Now you are missing the receiver's key pair in your question. This makes it impossible to encrypt messages for the receiver, as you cannot establish the identity of the entity that is trying to contact you. You could still use Diffie-Hellman key agreement to establish a secret key to prevent passive attacks, but the scheme would not be secure against active attacks.

Public keys are usually not protected against attack. For instance, an RSA public key exponent is usually set to 65537 so anybody that also processes the modulus can guess the public key using only a single guess. Public key operations are usually not protected against leaking the public key either. So any scheme that requires the public key to be secret is build on quicksand.

You need to provide the receiver with a shared secret key or a key pair with a trusted public key to create a secure scheme.

[UPDATE] After the update only message authentication and integrity seem to be requested. This can be performed using any secure digital signature format. RSA with a large key size and PKCS#1 v2.1 PSS padding would likely be the best choice.

Although key rotation is always preferable, a large enough key pair is likely to be secure enough unless quantum computers start to scale really well. Currently QC secure algorithms are not standardized all to well, so it's not like you have much of a choice in that regard. ECDSA could also be used.

It's probably best to use an existing container format for this. Usually CMS would be recommended as protocol.


Why do we use one transformation to hide the structure in UOV?

The public key in Oil-Vinegar was proposed as $F\circ L$, where $L:\Bbb F^n \to \Bbb F^n$ ($n = o + v$) is an invertible linear transformation and $F:\Bbb F^n \to \Bbb F^o$ is an Oil-Vinegar map.

I think you are suggesting that another transformation $T:\Bbb F^o \to \Bbb F^o$ is used at the end of the composition so that the public key becomes $P = T\circ F \circ L$. This is natural (and necessary!) in other similar schemes like Hidden Field Equations (HFE). However, this is not necessary in Oil-Vinegar since $F$ is uniformly random among all Oil-Vinegar maps and the composition of an Oil-Vinegar map with a linear transformation (on the left) yields another Oil-Vinegar map.

To be more precise, if you let your public key be $P = T\circ F \circ L$, then by definining $F' = T\circ F$ your scheme will have the shape $F'\circ L$ where $F'$ is an Oil-Vinegar map, so we can assume without loss of generality (or, without losing security strength) that the transformation $T$ does not exist.


Given a PRF $F$ , is $G(s) = F_s(1)\|F_s(2)\|\cdots \|F_s(n+1)$ a PRG?

Consider the following game:

I assume certain familiarity with the definitions of Katz and Lindell book (this is exercise 3.14 in the book). In particular, $O$ is denoting an oracle. It can be either a random function oracle (if $b = 0$) or the output of a random function $F_s$ (if $b = 1$). What you do essentially in your distinguisher is query this oracle $l(n)$ times. This is a generalization with respect to your setting. Instead of $n$ one can write an arbitrary polynomial $l(n)$ since the involved algorithms are PPT.

In any case, note that when you gather all the $b_i$ you get $y = G(s)$ or $y$ uniformly distributed in $n \cdot l(n)$. This is because the independent concatenation of uniformly distributed bits is uniformly distributed (?). So, indeed what you have in the last part is a distinguisher for the PRG game.

If you assume that $G$ is not a PRG then we can use an attack $A$ that has non-negligible probability $|P[WIN_{PRG}] - \frac 1 2|$. Then, we realize that one wins in the game PRF if and only if one wins in the PRG game (case distinction on $b$). Therefore, $|P[WIN_{PRF}] - \frac 1 2| = |P[WIN_{PRG}] - \frac 1 2|$ is non-negligible, but this contradicts the definition of PRF.


Find a LFSR given 2n (or more) non-consecutive keystream bits

We are given the sequence $b_i$ for $i$ multiple of $m>1$ with $0\le i<2n\,m$.

If all the given $b_i$ are identical, we can't compute any missing $b_i$ (beyond a wild guess they are all $b_0$), stop.
Build the sequence of $2n$ known bits $c_j=b_{(j\,m)}$ with $0\le j<2n$.
Use Berlekamp–Massey to find a LFSR (polynomial $P$ of degree $k$ and $k$-bit initial state) matching $c_j$.
Find some period $p$ of the $c_j$. For small degree $k$, we can simulate operation of the LFSR until the state repeats (OK to say $k\le40$ on a PC) or we can use baby-step/giant-step (OK to say $k\le75$ on a PC, see final section of this former revision). But more generally, if $P$ factors into a product of irreducible polynomials of degrees $k_r$ (thus with $k=\sum k_r$), then a period is $p=\prod(2^{k_r}-1)$.
Note: For large polynomial, we can still efficiently compute $c_j$ for large arbitrary $j$ (see this), once we have $P$ and starting state.
If $\gcd(m,p)=1$, then $b_i$ also has period $p$, thus $\forall j\in\Bbb N,\ c_j=b_{(j\,m\bmod p)}$ ; it follows that $\forall i\in\Bbb N, b_i=c_{(i\,m^{-1}\bmod p)}$
Note: $m^{-1}\bmod p$ needs to be computed only once, e.g. with the half extended Euclidean algorithm.
Note: with $p=\prod(2^{k_r}-1)$ and $m$ a power of two as in the question, $\gcd(m,p)=1$ always holds. If $\gcd(m,p)\ne1$, it might be possible to find a smaller period, by factoring $p$ and iteratively removing those factors that leave what remains a period, until finding the smallest period $p_\text{min}$ (which depends on the irreducible factors of $P$ being primitive or not, and on the starting point). $\gcd(m,p_\text{min})=1$ allows to conclude without guesswork.

Once $2k$ consecutive $b_j$ are found, an easy option to find the LFSR yielding them is to use Berlekamp–Massey again. The initial state of the LFSR for the $b_j$ (in Fibonacci form) is of course the first $k$ bits $b_i$.

Not covered (yet?): polynomial arithmetic would allow to directly derive the LFSR for the $b_j$ from the one for the $c_j$; and conclude when $\gcd(m,p_\text{min})\ne1$ and partial information on the $b_j$ is available.


There is no security difference; there are a handful of practical ones:

With xor, you can have the same code to do encryption and decryption
With xor, you don't have to pick a 'word size'; a larger CPU can handle 4 or 8 bytes at a time, while a microcontroller can handle 1 byte at a time, without changing the ciphertext
With xor, you don't have to worry about endianness (which you would if you, say, added words modulo $2^{32}$

While these are all minor differences, they all point towards xor being slightly better from a practical standpoint


How is Homomorphic Encryption secure (over integers)?

The use case for homomorphic encryption is that I encrypt my own data with my public key. I then ship this data to the cloud. The cloud can perform operations on those ciphertexts. But, since the cloud does not have the private key, the cloud cannot decrypt the results of the operations.

Once the operations have been performed, the cloud sends the resulting ciphertext back to me. I can decrypt that to get the answer.

So the key is allowing another untrusted party access to encrypted versions of my data that they can compute on, but can't get the results of the computations. If someone else encrypts their private data with your public key and sends it to you, you will be able to get their private data since you can decrypt.


How to clock a linear feedback shift register?

The keystream 01010101000110101100 can be deduced from its first 8 bits and the polynomial $f(x)=1+x+x^5+x^6+x^8$, as follows.

Start with $b_0=0$, $b_1=1$, $b_2=0$, $b_3=1$, $b_4=0$, $b_5=1$, $b_6=0$, $b_7=1$ (according to the first 8 bits of the keystream in reading order). And for $i$ increasing from $0$ apply the recurrence $b_{i+0}\oplus b_{i+1}\oplus b_{i+5}\oplus b_{i+6}\to b_{i+8}$, where the integers following $_+$ are the orders of the non-zero coefficients in the polynomial. That is:

$b_8\gets b_0\oplus b_1\oplus b_5\oplus b_6=0$
$b_9\gets b_1\oplus b_2\oplus b_6\oplus b_7=0$
$b_{10}\gets b_2\oplus b_3\oplus b_7\oplus b_8=0$
$b_{11}\gets b_3\oplus b_4\oplus b_8\oplus b_9=1$
$b_{12}\gets b_4\oplus b_5\oplus b_9\oplus b_{10}=1$
$b_{13}\gets b_5\oplus b_6\oplus b_{10}\oplus b_{11}=0$

This is using a Fibonnaci implementation of the LFSR, which is convenient since it is such that the first bits output are also the initial state of the LFSR. According to the convention used to define Fibonnaci and Galois implementations, we might be using the fact that the polynomial for a Fibonnaci implementation is the reflection of the polynomial for a Galois implementation (that is, the coefficient for the terms of order $j$ and $d-j$ are swapped, where $d$ is the degree of the polynomial).

If we wanted to apply a Galois implementation, we'd have to deal with the fact that the initial state of the LFSR is not the first bits of output, and thus not immediately known in the context of the question: by common conventions, the first bits of the given keystream simply are NOT the initial state of a Galois LFSR with polynomial $f(x)=1+x+x^5+x^6+x^8$ producing the rest of the sequence immediately afterwards.


Single-scalar multiplication with sign bit

Using $x$-coordinates only, given a point $G = (x_0,y_0)$ on an elliptic curve $y^2 = x^3 + ax + b$ and a scalar $r$, the Montgomery ladder outputs the $x$-coordinate of $rG$.  However, a closer look at the algorithm shows that the other accumulator used in the computation contains the $x$-coordinate of $(r+1)G$.  Letting $x_1$ the $x$-coordinate of $rG$ and $x_2$ the $x$-coordinate of $(r+1)G$, we have that

  $y_1 = \dfrac{2b+(a+x_0x_1)(x_0+x_1)−x_2(x_0−x_1)^2}{2y_0}$

is the $y$-coordinate of $rG$.  Given $y_1$, its sign can readily be obtained.

See e.g. Éric Brier and Marc Joye, Weierstraß elliptic curves and side-channel attacks. In D. Naccache and P. Paillier, Eds., Public Key Cryptography, vol. 2274 of Lecture Notes in Computer Science, pp. 335-345, Springer-Verlag, 2002.


Does a cryptographic oracle have to be a server?

In Theory: No. How the Oracle is implemented or named is not important, only how it works.
In Practice: Everything that leaks information can be abstracted as an Oracle. So it is also possible to use the client as an oracle, or the systems processing the cryptosystems. The Server Client system is only the most common way how stuff works and communicates in the world wide web, but the important aspect is, that cryptography is used for a lot more that only "the internet".
A good example are operating systems. They are (for simplicity) offline systems, but you could also identify oracles and other mechanism in the cryptographic applications used for the OS. OS also use block ciphers, therefore it can be possible to make an offline padding oracle attack.
I hope I was able to give an adequate answer!


GMAC vs HMAC in message forgery and bandwidth

Saarinen in his work GCM, GHASH and Weak Keys says that;

This paper is not very clear and has led many people into regrettable confusion about universal hashing authenticators.

The paper—both the manuscript you cited and the conference paper at FSE 2012—contains misleading claims and misattribution of ideas; describes attacks that apply only beyond the bounds of safe usage in standard security advertisements; and proposes a remedy that neither raises the forgery probability nor addresses any practical concerns, in security or performance, of GCM.

The paper doesn't identify the three main realistic shortcomings of GCM: the danger of truncating tags because of the $O(\ell/2^n)$ term in the forgery probability instead of $O(1/2^n)$ for $n$-bit tags on messages of length up to $\ell$; the quadratic term in forgery probability arising from the use of a block cipher (it is misattributed to universal hashing); and the prohibitive cost to constant-time GHASH evaluation (as well as AES evaluation) in software, which invites leaking secrets through timing.

    The GHASH algorithm belongs to a widely studied class of Wegman-Carter
    polynomial universal hashes. The security bounds known (this and this) for these algorithms indicate that a $n$-bit tag will give $2^{−n/2}$ security against forgery.

    It can be argued that universal hashes sacrifice some communication bandwidth for convenience as traditional hash-based MACs are designed to reach the information theoretic $2^{−n}$ bound against message forgery.

These statements are both misleading at best, and simply false if taken literally on their faces.

Neither universal hashes[1] (paywall-free: (a), (b)) nor the Carter–Wegman method of authenticating multiple messages[2] (paywall-free) gives a quadratic term in forgery probabilities, or ‘$2^{-n/2}$ security’, phrasing which is too glib to distinguish offline computation afforded by an attacker from online forgeries limited by your application's bandwidth[3], and which obscures the intermediate block size vs. the possibly truncated tag size.  It is the use of a permutation like AES—or DES, as originally suggested by Shoup[4]—that causes quadratic terms to appear: use functions instead of permutations, and the quadratic terms vanish.

Universal hashes can actually attain the optimal bound $2^{-n}$ on forgery probability for an $n$-bit tag.  Indeed, the very first authenticator in history of Gilbert, MacWilliams, and Sloane in 1974[5] (paywall-free), published before the concept of universal hashing was named by Carter and Wegman in 1979, attains this forgery bound—by using a key as long as the message.

Carter and Wegman's innovations[2] were to compress the key to a constant size at a linear cost in forgery probability, and to extend the authenticator to multiple messages by encrypting each authenticator with one-time pad to conceal the structure of the universal hash.  Shoup's contribution in 1996[4] was to use DES on a per-message nonce to generate the pad, and proved that if the sender sends no more than $\sqrt{2^n\!/\ell\,}$ messages of length $\ell$ then the forger's success probability after $f$ attempts is bounded by $2 f \ell/2^n$ (Theorem 2).

Details.

GHASH is a family of functions $H_r\colon \{0,1\}^* \to \operatorname{GF}(2^{128})$ for $r \in \operatorname{GF}(2^{128})$ defined on a bit string $m$ by interpreting it, suitably padded, as a sequence $(m_1, m_2, \ldots, m_\ell)$ of elements of $\operatorname{GF}(2^{128})$, and giving $$H_r(m) = m_1 r^\ell + m_2 r^{\ell - 1} + \dots + m_\ell r.$$  In other words, we interpret a message $m$ as a polynomial of degree $\ell$ with zero constant term, and evaluate it at the point $r$.  (GHASH is one of several polynomial evaluation hashes in cryptography; Poly1305 is another popular one, over the prime field $\mathbb Z/(2^{130} - 5)\mathbb Z$.)

GHASH is a universal hash family, or, more precisely, GHASH has difference probability $\Pr[H_r(x) - H_r(y) = \delta]$ bounded by $\ell/2^{128}$ for any $\delta$ and any messages $x$ and $y$ of up to $\ell$ blocks.  Proof: The solutions in $r$ to $H_r(x) - H_r(y) = \delta$ are the roots of the polynomial $x(r) - y(r) - \delta$ in $r$.  This polynomial has degree at most $\ell$, so it has at most $\ell$ roots among $2^{128}$ possible values in $\operatorname{GF}(2^{128})$.

The one-time authenticator $m \mapsto H_r(m) + s$ for independent uniform random $r, s \in \operatorname{GF}(2^{128})$ on messages of up to $\ell$ blocks has forgery probability bounded by $\ell/2^{128}$.  Proof: For any $m \ne m'$, $a$, and $a'$, and for independent uniform random $r, s$,

\begin{align}
  \Pr&[H_r(m') + s = a' \mid H_r(m) + s = a] \\
  &= \Pr[H_r(m') + a - H_r(m) = a'] \\
  &= \Pr[H_r(m') - H_r(m) = a' - a] \\
  &\leq \ell/2^{128}.
\end{align}

A forger who attempts up to $f$ forgeries can't have better probability of success at a single forgery among all the attempts than $f \ell/2^{128}$.  Notice that there's no quadratic term here.  Only the bound on difference probabilities, and independence of $r$ and $s$, figured into this analysis—you could use any other hash family with bounded difference probabilities to prove a similar forgery probability bound.  For example, the one-time authenticator $m \mapsto m_1 r_1 + m_2 r_2 + \dots + m_\ell r_\ell + s$ with the message-length key $r = (r_1, r_2, \ldots, r_\ell)$ would give a bound of $f/2^{128}$, with no factor of $\ell$.

To authenticate many messages, Carter and Wegman suggested[2] using a uniform random key $r$ with independent uniform random $s_1, s_2, \dots, s_q$ to authenticate each of up to $q$ messages $m_i$ with $m_i \mapsto H_r(m_i) + s_i$.  They proved the forgery probability is still $f \ell/2^{128}$.  Notice that there is still no quadratic term in the forgery probability $f \ell/2^{128}$ of Carter and Wegman's method, and it is even independent of the number $q$ of messages sent.

The quadratic term arose when Shoup opted[4] to generate $s_i$ by the permutation $\operatorname{DES}_k(i)$.  The standard lemma about substituting a permutation for a function adds $q'(q' - 1)/2^{n - 1}$ to the forgery probability bound, where $q'$ is the number of calls to the permutation, which in AES-GCM is $1 + (1 + \ell) (q + f)$.  There are somewhat better bounds[6][7], but the point is that there is a quadratic cost to using a permutation like DES or AES.

More recent schemes like NaCl crypto_secretbox_xsalsa20poly1305 do away with the permutation and the Carter–Wegman method and instead simply generate $r$ and $s$ independently by a PRF for each message, as suggested by Lange[8].  But let's come back to GHASH and GCM.

  What is the convenience of universal hashes provides?

Universal hashes can be extremely cheap to evaluate—much cheaper than block ciphers, pseudorandom functions, and especially collision-resistant hashes.  There is no inherent limit to the parallelism attainable in evaluating polynomials by precomputing $(r, r^2, \dots, r^t)$ if you can perform $t$ simultaneous multiplications in your vector unit.  GHASH in particular is difficult in software because it is defined in terms of a binary field, with a kind of weird bit ordering[9], but there are other universal hashes friendlier to software, like Poly1305, which can run in under one cycle per byte in software.

  How much GHASH increase on the communication?.

GCM/GMAC adds a 128-bit tag.  Because the forgery probability is $O(\ell/2^n)$ rather than $O(1/2^n)$, you should avoid truncating the tag much[10].  For example, if you accept messages of up to 16 MB or $2^{20}$ blocks, then the forgery probability for a single 32-bit tag is $2^{-12}$ rather than $2^{-32}$ as you might hope.  Note that truncating the tag does not affect the quadratic term $O(q^2\!/2^b)$ arising from the use of a $b$-bit permutation instead of a $b$-bit function: the block size and tag size costs scale separately.

  Why one should not use an information theoretic bound HMAC instead should use a lesser one?

Mu.

The bound above is information-theoretic.  There is a corresponding information-theoretic bound for the HMAC model $$m \mapsto f\bigl((k \oplus \mathrm{opad}) \mathbin\| f((k \oplus \mathrm{ipad}) \mathbin\| m)\bigr)$$ with a uniform random function $f$, or for a Merkle–Damgård hash $f$ with a uniform random compression function, and it involves the collision probability of $m \mapsto f((k \oplus \mathrm{ipad}) \mathbin\| m)$.

But you need to choose an actual $f$ to make a practical system.  Universal hashing gives us strong guarantees with extremely cheap options; with HMAC we typically use conjecturally collision-resistant functions like SHA-256, which are orders of magnitude more expensive to compute for conjectured security that we don't even care about in this application (collision resistance).

But let's suppose you chose a comparable function to use with a 256-bit key giving a 128-bit tag, maybe one without collision resistance: MD5.  As it happens, HMAC-MD5 doesn't provide much security after $2^{64}$ messages either[11].  Oops.

(The fact that MD5's collision resistance is broken is irrelevant here; what's relevant is the 128-bit hash size.  The same generic attack on HMAC works when $f$ is a random oracle, which by definition is collision-resistant.)

There is an advantage to HMAC-MD5 over, e.g., AES-GMAC (which is AES-GCM with an empty ciphertext) or Poly1305-AES (another Carter–Wegman–Shoup MAC with AES): HMAC-MD5 doesn't need a nonce, whereas AES-GMAC and Poly1305-AES do; and HMAC-MD5 works not just as a MAC but as a long-input short-output PRF, whereas GMAC and Poly1305-AES don't.  But you can also fashion a good, fast, nonceless long-input short-output PRF out of a universal hash and a short-input short-output PRF[12].  For example, AES-GCM-SIV does just that (and fixes the bit ordering in GHASH too).

  Since GHASH provides at most $2^{64}$ security against forgery in TLS 1.3, and that is standard that cannot be changed, are there any other suites that provide information theoretical security against forgery.

You can use ChaCha20-Poly1305.  This avoids the quadratic cost in forgery probability of using a block cipher, and it doesn't present a conflict between speed and security in software implementations.

The CCM cipher suites all have the same disadvantage as GCM of $O(q^2\!/2^b)$ in the forgery probability from using a permutation instead of a function of $b$ bits, and they require $\ell$ AES calls rather than 1 AES call per message just for authentication.  The advantage they have over GCM is $O(1/2^n)$ instead of $O(\ell/2^n)$ in the forgery probability, and some hardware has dedicated AES circuits that might run faster than software to evaluate ChaCha20 or Poly1305.


Are the following schemes based on a pseudo-random permutation secure?

Looks rather OK to me.

As for the first question, XOR with a value won't introduce any duplicate values and now $F$ is a PRP the first part of the answer should be correct. It's clearly deterministic, so no IND-COA or CPA security.

As for the second question $F_k(r ||m)$ seems to me identical to a single block encrypt with CTR mode. However, for CTR mode you require quite a large block size.

You could well distinguish between $m=0$ and $m=1$ given enough ciphertext; you'd get a lot of 00 and 10 results if $m=0$ is prevalent, which would be different from the 01 and 11 results. Concatenation in general should be considered dangerous.

So I think it could be CPA secure, but only when $n$ is somewhere around 128 bits or higher and/or the amount of messages is restricted. Without additional restrictions the answer should be no IND-COA or CPA security. Learning that a particular value is prevalent is already enough to break IND-COA:

e.g from Wikipedia about ciphertext-only attacks:

  The ability to obtain any information at all about the underlying plaintext beyond what was pre-known to the attacker is still considered a success.


You are absolutely right! The random self-reducibility goes in the other direction, and this variant of the DDH assumption does not follow from it. I have no idea what the author was thinking when he wrote it :-). In any case, the paper has now been updated in ePrint and fixed. Thank you for catching this.

I include the proof of this variant here:

Consider the following DDH variant that states that for every probabilistic-polynomial time non-uniform distinguisher $D$ there exists a negligible function $\mu$ such that
\begin{equation}
\left|\Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^r)=1] - \Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^{r+1})=1]\right| \leq \mu(n)
\label{eq:ddh}
\end{equation}
where $\mathbb{G}$ is a group of prime order $q$ with generator $g_0$, $g_1\in\mathbb{G}$ is a random group element, and $r\in\mathbb{Z}_q$ is randomly chosen. This assumption can be proven to be to be true if the standard DDH assumption holds. In order to see this, observe that by the standard DDH assumption
\begin{equation}
\left|\Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^r)=1] - \Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^s)=1]\right| \leq \mu(n)
\label{eq:ddh1}
\end{equation}
where $g_1\in\mathbb{G}$ and $r,s\in\mathbb{Z}_q$ are randomly chosen. In addition, observe that the distribution over $(g_0,g_1,(g_0)^r,(g_1)^s)$ is identical to the distribution over $(g_0,g_1,(g_0)^r,(g_1)^{s+1})$. Thus, a straightforward reduction to the standard DDH assumption gives that
\begin{equation}
\left|\Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^s)=1] - \Pr[D(\mathbb{G},q,g_0,g_1,(g_0)^r,(g_1)^{r+1})=1]\right| \leq \mu(n).
\label{eq:ddh2}
\end{equation}
In order to see this, a distinguisher $D'$ receiving $(g_0,g_1,h_0,h_1)$ can run $D$ on $(g_0,g_1,h_0,h_1\cdot g_1)$. If $D'$ received $(g_0,g_1,(g_0)^r,(g_1)^r)$ then it generates a tuple of the form $(g_0,g_1,(g_0)^r,(g_1)^{r+1})$, and if $D'$ received $(g_0,g_1,(g_0)^r,(g_1)^s)$ then it generates a tuple of the form $(g_0,g_1,(g_0)^r,(g_1)^{s+1})$, which as we have mentioned is identical to $(g_0,g_1,(g_0)^r,(g_1)^s)$. Thus, if $D$ can distinguish with non-negligible probability in this last equation, then $D'$ can use $D$ to solve the standard DDH problem. Combining these last two equations, we obtain that the first equation (which is the DDH variant assumption) holds.


Perfect Indistinguishability in shift cipher

I'm assuming that, that attacker produce $m_0$ and $m_1$ and given one of their ciphertext as a challenge.

given $c$, the attacker cannot distinguish whether it is encryption of $m_1$ or $m_2$. Since, he doesn't know the key. He can guess only 1/2 probability. For this attacker, it has perfect indistinguishability.
given $c$, the attacker can distinguish that the plaintext has all characters different. Because the shift cipher's property, $$c = E_k(m_1) \text{ and } c=E_k(m_1) \Leftrightarrow  m_1 = m_2$$ and he output $m_0$ and $m_1$ with all different characters.
given $c$, the attacker can distinguish that the plaintext has all characters different. Because the shift cipher's property and and he was output $m_0$ as $aaa$ and $m_1$ as all different characters.
given $c$, the attacker can distinguish that because the attacker output $m_0$ and $m_1$, on advance he knows that first letter is always an $a$

As a result; 2,3, and 4 can be used to demonstrate that the shift cipher for 3-character messages does not satisfy perfect indistinguishability


Is ISAAC Cipher Cryptographically Secure?

It somewhat depends how you define “secure“, but as far as I know, it has not been broken yet.

Potential attacks and/or weaknesses:

Brute force to find 256-bit key.
~ Obvious.
Paul and Preneel (2006) published an alleged distinguishing attack using $2^{17}$ bytes of output
~ Turned out to be an attack on a cipher different from ISAAC.
Aumasson (2006) labelled various states of ISAAC as "weak."
~ Pointing to weaknesses, but no statements of any attack.

Therefore, I would categorize it to be cryptographically secure indeed. Yet, we have to remember that ISAAC didn’t get as much attention as (for example) AES did. So there may well be weaknesses that have not yet been found and/or published. But looking at what is known, it should be safe. (ISAAC+ would be more recommendable though, as it fixes some weaknesses pointed out by Aumasson).

As to seeding: a securely generated random seed should indeed suffice, as long as it is generated cryptographically secure.


At the current time, is SHA256 the de facto standard for strong cryptographic hashes?

Yes, SHA-256 is currently the de facto standard. The "why" is that MD5 and SHA-1 are unsafe and the only algorithm left which has been extensively studied and deployed and which nobody has found a significant attack against is SHA-256. (There is also SHA-512, but people seem to regard it as being overkill.)

There is widespread uncertainty about whether someone will discover an efficient attack on SHA-256 in the near future. It was this fear which motivated the SHA-3 competition.

You should also consider using a generic length-extension defense such as the "SHA-256d" design by Ferguson and Schneier. SHA256d(x) = SHA256(SHA256(x)). If you don't use a generic length-extension defense then you have to consider the consequences of length-extension attacks in each place that you use a hash function. Such considerations can be tricky, and if you misunderstand one, this can sometimes cause a security vulnerability. This is why it is safer to use a generic length-extension defense every time you use a hash function.

If for some reason you don't want to use SHA-256, and you don't want to use a new hash function such as a SHA-3 candidate, then you might also consider Tiger. It has the distinction of being one of the longest-serving hash functions for which there is no known practical attack. However, it has been seriously wounded (i.e. by impractical but theoretically significant attacks), and I would consider SHA-256 safer than Tiger at this point. If efficiency matters, Tiger is faster than SHA-256, SHA-1, or any SHA-3 finalist on 64-bit hardware. It doesn't come with generic length-extension defense built in, but you can of course define Tigerd(x) = Tiger(Tiger(x)).

I would also regard the current crop of SHA-3 finalists as very likely to be secure: http://ehash.iaik.tugraz.at/wiki/The_SHA-3_Zoo . They are much newer, of course, than SHA-256, but they were all designed with a thorough understanding of the flaws in MD5 and in SHA-1, and they have been subjected to intensive scrutiny for almost three years now. They all come with generic length-extension defenses. My favorites are Blake and Skein, which are faster than SHA-256 on Intel/AMD chips. Unfortunately all of the SHA-3 candidates are slower than SHA-256 on ARM chips.

Don't use MD5 or SHA-1. Please.


Why are ephemeral/session/temporary keys useful?

Why else are ephemeral keys used?

Ephemeral keys are not a specific form of keys, they are just short lived keys within a key establishment protocol. Usually they are not directly trusted as they are generated on the fly.

ECIES may also use an ephemeral private key, to name a single other usage.

  In particular, if I don't care about Perfect Forward Security, and I already have two machines that have a shared symmetric key, is there any reason to use ephemeral keys?

You may want to generate symmetric session keys that can only be used for a specific session. Ephemeral-ephemeral DH key agreement would work fine for that, although other schemes are also possible. You may also want to use separate keys for different senders and for different purposes (such as encryption and MAC).

Otherwise you could for instance replay messages encrypted with the masterkey. Again, there would be other methods that protect against such a situation, but establishing session keys is a common way to do this.

  In AES-GCM, is a 96-bit IV sufficient to not require temporary keys?

Unless you define ephemeral simply as short lived keys the AES keys themselves are not really ephemeral. They are generally used for multiple messages, not just during key establishment.

AES-GCM can, within reasonable bounds, be used with one key for multiple messages. And yes, the nonce can help with that. The bounds have been defined in NIST SP800-38D which specifies the GCM mode for use in US Federal Agencies.

There are good reasons to use session keys within a transport protocol regardless of the security of the cipher, as already mentioned in the second paragraph.


Ok, suppose that we have a ciphertext $(c_1, c_2, ..., c_8)$ that we wish to decrypt.

What we start off with is to make a guess for $p_8$, which is the decryption of the last byte of the block.  Suppose that we guess that it is 0x07; we then need to validate that guess.

What we do is create a two block message; the second block is the challenge ciphertext block $(c_1, c_2, ..., c_8)$; the first block has 7 random bytes; followed by $0x07 \oplus 0x01 = 0x06$.  We then send it to the Oracle for decryption.

Let us recall when CBC mode decryption is; it is $P_i = C_{i-1} \oplus D_k( C_i )$.  In the specific case of the last block, what the decryption process will do is first internally decrypt the last ciphertext block $(c_1, c_2, ..., c_8)$, and get the plaintext block $(p_1, p_2, ..., p_8)$; it'll then exclusive or that with the previous ciphertext block; the last byte of that result will be $p_8 \oplus 0x06$ (because we made the last byte of the next-to-last-block 0x06).

Now, if our guess was correct; that is $p_8 = 0x07$, the result of this exclusive-or is $0x07 \oplus 0x06 = 0x01$; a last block with the last byte of 0x01 is valid padding, and so the message will be accepted.

On the other hand, if our guess was not correct, then the result of this exclusive-or is something other than 0x01.  Now, it's possible that the result will also look like a valid padding (for example, the last three bytes might be 0x03 0x03 0x03), however that would also involve other bytes (which we set randomly), and so that's unlikely.

So, to actually perform this attack, we would make guesses at $p_8$, and send out ciphertexts to test those guesses.  And, once we have determined the likely value of $p_8$, we can start guessing $p_7$ (which works just the same way, except we're targetting the $0x02$ $0x02$ final pattern).

BTW: the Bliechenbacker CCA attack is actually unrelated.


What is the significance of the Period of a Steam Cipher

If you know the period of the stream cipher, you can XOR 2 different encryptions from the same point in the period (integral number of periods apart) and eliminate the pseudo random stream entirely.  All that would be left are 2 plaintexts XOR'd together, and this is something a smart child can break in a short time.


Is there a difference in the security provided by a OTS vs a MTS or FTS? Or are they all just different ways of providing the same service?

The question is quite broad, but the main difference in well designed schemes should be that an OTS can be used once, FTS can be used a few times, and MTS can be used many times.
As an example, with SPHINCS+ you can sign up to $2^{64}$ messages before any degradation in security.
The goal of an FTS scheme (created from an OTS) isn't to add security but to allow one public key to sign a few messages.  Similarly for a MTS scheme (built from OTS and/or FTS), to sign many messages.
That is not to say there is not any difference in security.  It is difficult to answer generally. An MTS scheme built in a stateless way from a combination of OTS and FTS is really it's own beast.  Although it's security will obviously rely on the underlying schemes and how they are used.


How Far Ahead of Academia Are Government Agencies?

Disclaimer: This post is possibly opinion based.

How far ahead (if at all) are governmental agencies of open source (specifically academic) research?

This question is impossible to answer. By definition, this require a knowledge of the state of research in such agencies which is definitively something they want to be kept as secret...
thx to @fkraiem:

However one can get a feeling of it by considering the followings:

Academic research is usually founded by companies or government agencies.
e.g. for the Gimli paper:

This work was supported in part by the Commission of the European Communities through the Horizon 2020 program under project number 645622 (PQCRYPTO) and project number 645421 (ECRYPT-CSA); the Austrian Science Fund (FWF) under grant P26494-N15; the ARC project NANOSEC; the Belgian Fund for Scientific Research (FNRS-F.R.S.); the Technology Foundation STW (project 13499 TYPHOON), from the Dutch government; the Netherlands Organisation for Scientific Research (NWO) under grant 639.073.005; and the U.S. National Science Foundation under grant 1314919. “Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

In the case of important projects, academic research is paired with companies with huge computing power (Google, Microsoft Research...) e.g. SHAttered:

This result is the product of a long term collaboration between the Cryptology Group at Centrum Wiskunde & Informatica (CWI) - the national research institute for mathematics and computer science in the Netherlands - and the Google Research Security, Privacy and Anti-abuse Group. Two years ago Marc Stevens and Elie Bursztein, who leads the Google's anti-abuse research team, began collaborating on making Marc's cryptanalytic attacks against SHA-1 practical by leveraging Google expertise and infrastructure.

Sure such companies may? still not have the computing power of NSA, but the minds in there are definitively on par with such agencies.

I would also advise this to have a look at this: The Moral Character of Cryptographic Work by Phillip Rogaway [paper] [Usenix Talk], specially at the founding part (p. 36). We see a increase in the number of project founded by military agencies.
WARNING: this is a personal assumption, you may chose to disagree with it.
Knowing their missions (cf quote bellow) we can somewhat deduce that their level of research is most likely on par with academic work (why would you heavily fund something that would be bellow your current level of comprehension?)
e.g. for Defense Advanced Research Projects Agency (DARPA) :

The genesis of that mission and of DARPA itself dates to the launch of Sputnik in 1957, and a commitment by the United States that, from that time forward, it would be the initiator and not the victim of strategic technological surprises.
source.

Their goal are the following:

fund academic research
but most importantly know what you are currently researching on! $\Leftarrow$ This is information they want!

TL;DR:  I believe they are on par with current academic research.


Where do I securely store the key for a system where the source is visible?

You can use a password based key, which is a similar approach to the PGP method, create a key somehow (random clicks, random numbers etc.), encrypt it with a password and store it somewhere. When the user wants to access the DB, he enters the password, which is the key for the DB decryption key file and then you get the clear password for the DB.

The main idea is to remove the key from the machine itself, and pass it to the user, and meanwhile generate a unique key for each user (computer), so if I have the SW on my computer, I still don't have the key to another's DB.


The second row of the second table gives you the values of $g^e\pmod{11}$ for $0 \le e \le 10$. Notice that $2^{10}\pmod{11} \equiv 2^{0}\pmod{11}$. This means that $2^{10}$ raised to any power is congruent to $1\pmod{11}$.

With that in mind, it shouldn't be hard to see that $2^{2652557887263}\pmod{11} \equiv 2^3\pmod{11}$. So the answer is $8$.

P.S. I suspect your question may be slightly off-topic for this site, hence the down votes.


How to calculate CPA attack complexity in bits manipulation

The answer would depend on the entropy of the set of bits $M$. Let's say $M$ is a set of all-zero bits; in that case there would be only $1$ possible set of bits you could choose - every bit in every position is zero. If, however, you had a random set of bits for $M$ you'd approach ideal security; ideal security meaning $m\, P\, (n-(n/2))$ possible keys to brute-force.
How we calculate ideal security:
We know why we use the permutation function, but why use $n-(n/2)$? Let's imagine we have a random set of bytes, each unique; we have less than 256 bytes in our set so we can avoid repeats. The possible unique states would become $\infty$ meaning $m\, P\, (n-(n/\infty))=m\, P\, n$. But if we get each byte twice we end up with half the possible unique sets of choices - for every byte I select I could just as well select another byte and get the same result. As such, for $n$ bits the repeats will be defined by $n / 2$ since there are $2$ unique possible states for each bit. For sets of bytes it would be defined by $n/256$ meaning the complexity would me $m\, P\, (n-(n/256))$. This is because the frequency of repeats is based on the number of possible non-repeating states.
Therefore, if you want the scheme to be secure you should make $M$ as random as possible. A nonrandom value $M$, or a value specifically chosen to be weak would cripple the entire system; if $M$ is all-zeroes that's effectively a base-1 system which means each (bit-like-thing-with-only-one-state) has only $1$ possible state, giving me $m\, P\, (n-(n/1))=m\, P\, 0=1$ possible key.
CPA attack possibilities:
If the attacker can find the value $N$ for 1 block, they now know the position of $n$ bits within $M$. If they repeat this for multiple blocks, they will eventually get enough bits to brute-force the rest; so the difficulty of a CPA comes down to whether the value $N$ can be figured out from the plaintext-ciphertext relationship, which is dependent on the specifics of your FEC. This applies in the same way to known-plaintext attacks. Thus, your system would be secure from chosen-plaintext attacks iff (if and only if) it is secure against known-plaintext attacks.
Update:
I noticed an error where I forget to account for the fact that the repeating bits can themselves be permutated. This lowers the number of possible states significantly. I have updated the formulas accordingly, and the information should be correct now.


Are there any many to one encryption frameworks available?

What you ask for is possible, but only (I'm pretty certain, although I don't have any sort of formal proof) if there is a central authority who has a separate, secured connection to each user. Also, the concept of public keys becomes unnecessary. If the encryption and decryption key is a function of "public keys", then any user who at any point was a member of the system will be able to encrypt or decrypt messages. To show what I'm talking about, let's build the following system.

We have users $u_1, \ldots u_n$. Let's say that $u_1$ is the authority, and can revoke any user's access to the system. We have a shared encryption key, $k_s$, which is known to all $u_i$ and $k_s$ is determined by some key derivation function $KDER(pub_{u_1}, \ldots pub_{u_n})$.

If $KDER$ is public (i.e., the new key is derived by each user from the public keys), then we have the following problem. Let's say the user getting booted is $u_{n}$. If $KDER$ is public, it is trivial for $u_n$ to attack the system, as they know $KDER$ and know $pub_{u_1}, \ldots pub_{u_{n-1}}$, and can therefore derive the new key.

So the concept of using public keys doesn't quite make sense. So instead of referring to them as $pub_{u_i}$, let's consider them as $tok_{u_i}$, which is private token randomly generated by the central authority. Now, $KDER$ is private, and $u_1$ must distribute the new encryption key using his secure channels. At this point, the users can all use the new key for sending messages, and the booted user won't be able to attack the system.

Having a central authority seems like it should work for you, because of the line:

  My use-case also needs that some of these users only have temporary access which can be revoked externally

Which seems to imply that there is some sort of authoritative actor within or without the system. But if this is not the case I don't believe what you're asking for is possible. For this to be decentralized, every user within the system, including the user who was just removed, must have the ability to create the new key. Crypto has some nice tools for granting access after an amount of time $t$ (proof-of-work systems and so on, see this question), however I do not believe there are any systems which grant access for some amount of time that do not require a central authority.

I really hope I'm mistaken, because such a system would have some very interesting use cases, but if you think about it it doesn't quite make sense. Someone needs to decide when a user's access is up.


Short Weierstrass equation is non-singular for not 2 or 3 characteristic

By definition, a point on the affine curve
$$
E\colon\quad \underbrace{y^2-x^3-ax-b}_{=:f}=0
$$
is singular if and only if the Jacobi matrix
$$
J_f
=\Big(\frac{\partial}{\partial x}f,\frac{\partial}{\partial y}f\Big)
=(-3x^2-a,2y)
$$
does not have maximal rank at that point, that is (here), vanishes.
Hence precisely the points $(x,0)$, where $x$ annihilates both $x^3+ax+b$ and its derivative $3x^2+a$, are singular points of $E$. Therefore, such a point exists if and only if $x^3+ax+b$ has a multiple root, and this is the case if and only if its discriminant
$$
\Delta=-4a^3-27b^2
$$
is zero.

To be precise, it still remains to prove that the point at infinity $[0:1:0]$ is always non-singular: On the affine patch $\{y=1\}$, the (projectivized) curve equation $y^2z-x^3-axz^2-bz^3$ dehomogenizes to $z-x^3-axz^2-bz^3$. Its Jacobi matrix $(-3x^2-az^2,1-2axz-3bz^2)$ becomes $(0,1)$ at the point at infinity $(0,0)$, hence is non-degenerate for any $a$ and $b$.


Is the inverse of a secure PRP, also a secure PRP?

In theory. No.  The inverse of a secure PRP need not be a secure PRP.

Here is what we can guarantee.  The inverse of a secure sPRP (strong-pseudo random permutation) is guaranteed to be a secure sPRP.  Any secure sPRP is a secure PRP.  Therefore, the inverse of a secure sPRP will be a secure PRP.

FYI, if you are not familiar with PRP/sPRP, the difference between PRP and sPRP is:

a PRP is secure against adaptive chosen-plaintext attacks
a sPRP is secure against adaptive chosen-plaintext/ciphertext attacks

Caution: I've just learned that apparently this terminology is not 100% standard, and some people use different terminology (e.g., weak PRP / PRP or PRP-CPA / PRP-CCA instead of PRP / sPRP).  So, beware, and make sure to translate my statements accordingly if you prefer the other terminology.  I realize this could affect the meaning of your question.

In practice. In practice, when we make statements like "AES is secure", we usually mean that "AES is a secure sPRP".  Sometimes you might see people being sloppy about the distinction between PRP and sPRP, but any modern block cipher that is not broken can usually be assumed to be a secure sPRP.  Therefore, the inverse of any modern block cipher (like AES) will also be a secure PRP.

Proof. For the crypto-purists, here is a proof of the statement that the inverse of a secure PRP need not be a secure PRP.

Define $E_k$ as follows:

$$E_k(x) = \begin{cases}
0 &\text{if $x=k$}\\
\text{AES}_k(k) &\text{if $x=\text{AES}_k^{-1}(0)$}\\
\text{AES}_k(x) &\text{otherwise.}
\end{cases}$$

It is easy to check that $E_k(\cdot)$ is a permutation for each $k$.

It is also straightforward to prove that $E$ is a secure PRP (making plausible assumptions about AES, e.g., that it can be modelled as an ideal cipher).  Why?  Because $E_k(\cdot)$ agrees with $\text{AES}_k(\cdot)$ on all but two input values, and the adversary has no clue what those input values are.  The best the adversary can do is hope to hit one of those two inputs by chance.  The probability that the adversary happens to hit one of those two values by chance is miniscule: after 1 query, the probability is $2/2^{128}$, and after $q$ queries, the probability is $\le 2q/2^{128}$.  If $q$ is bounded by any reasonable value (say $q \le 2^{64}$), this probability is negligible.

It is also easy to prove that $E^{-1}$, the inverse of $E$, is not a secure PRP.  All you have to do is query the inverse on the plaintext $0$, and you get back the key (since our definition of $E$ has ensured that $E^{-1}_k(0)=k$).  So, a single chosen-plaintext query completely breaks $E^{-1}$.

This proves that there exists a cipher that is a PRP but whose inverse is not a PRP, or in other words, that the inverse of a PRP is not necessarily guaranteed to be a PRP.


Required key size for an ideal cipher with a 32 bit block size

The size of the key depends on the security level you want, it is not possible to say "you need exactly $n$ key bits if you have a block size of $m$ bits".

Let's assume that for an ideal cipher, a block size of 32 bits means $2^{32}$ possible input values which can be permuted in $(2^{32})!$ ways. That means you would have at most $\log_2(2^{32}!)$ key bits, to avoid equivalent keys. This is a lot, and in practice only a (very!) tiny fraction of that amount of bits would be used. In fact, one could argue that this upper bound on the key size is so ridiculously large that it's almost meaningless.

For a lower bound (this is probably what you are interested in), you need to look at the required security level.
For example, a 10 bit key is easily bruteforced, but a 256 bit key is secure against brute force attacks (assuming of course there are no other attacks on the cipher).


Need help solving a puzzle (from a layperson)

The hints provide a lot of information about the puzzle.

  1) Run the ecdsa public key trough a base64 decoder.

  When running the public key through various online base64 decoders, the result has been varied on each site. I get everything from Korean characters to random box characters. So I'm somewhat stuck at hint 1.

  2) Open the base64 decoded value in hex editor.

Base64 encoded data is not necessarily text (ASCII, UTF-8 or otherwise). The easiest thing to do is to decode this into standard hexadecimal bytes. So converting the Base64 string to a Hexadecimal string results in

000004d958d91cd84b5cda184c8b5b9a5cdd1c0c8d4d800000021b9a5cdd1c0c8d4d800000104138a1842988e9106991aeda0675fefd089963ca4d72fc66cc1425edf40a0a9e4e4bc3daf94a7bfadf1619e562c1364a3355ee2c34b5c86941ad8bfa4c3b2e1a9240

  3) Public key should be a 65-byte array, starting from byte with value 4, next 32 bytes would be x value, and the next 32 the y value.

This hint is telling us to extract the public key. The data provided is 104 bytes in length but the public key is only 65 bytes. It begins with a 04 byte (that's what "byte with value 4" means), so we look for that pattern in the data.

There are two such places where there is a 04 byte, so let's start with the first one.

If we assume the first 04 that we see corresponds to the public key, then our public key will be:

04d958d91cd84b5cda184c8b5b9a5cdd1c0c8d4d800000021b9a5cdd1c0c8d4d800000104138a1842988e9106991aeda0675fefd089963ca4d72fc66cc1425edf

If we assume the second 04 that we see corresponds to the public key, the the public key will be:

04138a1842988e9106991aeda0675fefd089963ca4d72fc66cc1425edf40a0a9e4e4bc3daf94a7bfadf1619e562c1364a3355ee2c34b5c86941ad8bfa4c3b

  A final clue is this: "First have the name of the digital signature algorithm, then the name of the curve, and then the public component of the key. Got it?"

This clue refers to this string:

  ecdsa-sha2-nistp256

ecdsa stands for Elliptic Curve Digital Signature Algorithm. This indicates the digital signature algorithm that was used.

sha2 indicates that a function in the SHA-2 hash function family was used for signing the message. When signing a message with ECDSA, the message must be hashed with some hash, commonly SHA-256. I will assume this means to use SHA-256.

nistp256 refers to the elliptic curve that was used in ECDSA. It provides us with the other parameters that we need to compute and verify an ECDSA signature.

That is all of the information that can be gotten quickly from the provided hints and initial information. You will have to look through the remaining 39 bytes of data to solve the rest of the puzzle.

Further examination of this shows that it is an SSH public key.


How is the password sent across for verification?

It depends on the particular scheme. In a simple challenge-response scheme, the server sends a challenge, the client "encrypts" the challenge and the password to form a response, and then the client sends the response over the wire.

However, standard logins typically don't use challenge/response. The password is just sent to the server by the client. When using SSL/HTTPs, the password is protected by the encryption of the channel. When using ordinary HTTP, there's no protection whatsoever. With no security on the channel itself, even with a challenge/response protocol, an attacker can simply proxy the authentication portion of the protocol between the client and server and then takeover the authenticated connection after that phase completes.


Is there a function similar to a hash function, but it's reversible?

While not reversible, HMAC seem to be a plausible solution.

HMAC is a construct that adds a "key" to the hash digest, your program generates it with a symmetric key that's somewhat hidden in your program. You verify the player's scores by hashing the score with the key and compare the digest - this is a very typical tag comparison of message authentication code.


RSA: Is it possible to recover the plaintext given that we have the ciphertext and the public key?

It might be feasible, or not.

If "digits" had been binary digits or bits, the answer would have been yes. Anything about 600-bit can be factored by GNFS. The public record is for a 768-bit RSA modulus, factored in 2009. 600-bit is within reach of CADO-NFS and Msieve. That's even packaged into factoring as a service for semi-deep-pocketed script kiddies.

It could be that $N$ was poorly chosen and can be factored much more easily than by GNFS. Since the generation algorithm is unspecified, we can't tell. Poor RSA key generators have happened (see e.g. SmartFacts, ROCA, and predictable SSH hosts keys on way too many platforms).

It could also be that the encryption system used is plaintext RSA, where the ciphertext is $C=M^e\bmod N$ with $M$ the plaintext. This contrasts secure RSA, where $M$ is obtained from plaintext and randomness using a padding scheme such as OAEP. If $M$ is the plaintext (or a known deterministic function of the plaintext), some attacks much easier than factoring the modulus might be possible:

if $M$ is in a known small set (names on the class roll, 16-digit credit-card number), it is possible to enumerate possible $M$, perform encryption, and check against the ciphertext.
if $M=U\cdot V$ with $U<2^u$, $V<2^v$, $u\le v$ (which is likely when $M\ll2^{u+v}$ ) then there's a Meet-in-the-Midle attack with cost $O(2^v)$ time and $O(2^u)$ memory.
if $M<\sqrt[e]N$ we have the $e^\text{th}$ root attack (which can be extended to slightly larger $M$).


What is straight line black box reduction?

A straight-line black-box reduction is one that interacts with the adversary in a black-box manner (read: is given oracle access to the adversary) and "cannot rewind" the adversary.

So, assuming (as an example) that the protocol has the corrupted party receiving $5$ messages, then the straight-line black-box reduction can/will give the adversary the messages $m_1,m_2,m_3,m_4,m_5$. In that order; and in that order only.

Simpler said: a straight-line black-box reduction interacts with the adversary the same way it interacts with a regular party.


Is there an actually an alternative to using Diffie Hellman in TLS handshake?

This depends on the TLS version you're using.

In TLS 1.2, keys can be exchanged via RSA, DH (Diffie-Hellman over a Finite Field), ECDH (Diffie-Hellman over an Elliptic Curve), DHE (DH but the key is discarded after use to provide forward-secrecy), ECDHE (ECDH but the key is discarded after use to provide forward secrecy), PSK (Pre-Shared keys), and SRP (Secure Remote Password protocol).

In TLS 1.3 the insecure and overly-complex methods were deprecated, leaving only DHE and ECDHE for key agreement.

Versions of TLS before 1.2 don't have any unconditionally secure cipher options, and should not be used.

Wikipedia has a nice table, though note that it shows both the key exchange/agreement method and the authentication method in one chart, so there can be multiple rows using a given key exchange/agreement method.


After a diffie hellman key exchange, what is the common secret used for?

It can be used as a key for a symmetric key algorithm.

It can be used to derive a key via a standard key derivation mechanism.


Questions about Key Derivation Functions

Let's start with a general secure KDF construction, as follows. Let $F(k,x) \rightarrow \{0,1\}^n$ be a secure PRF. Then choose $L$ such that $L \times n$ provides as many output bits as you need for all of your generated keys. Let $S$ be your original secret key/entropy. Generate the following string:

$KDF(S,N,L) := F(S, C || 0) || F(S, N || 1) || ... || F(S, N || L)$

where N is a unique value per application that calls the KDF. In the case that you are generating $n$ bit keys, you would simply assign each key $K_i := F(S, N || i)$.

This is similar to your construction, but distinctly different. In your construction, $R$ is fixed across all calls, whereas the PRF above chooses a different random function for each entropy input. In fact, you are essentially trying to emulate the behavior of the PRF by using $R$ and $S$ prefixed to all the inputs. However, I don't know if $R(S || X)$ is as secure as $PRF(S,X)$, and I wouldn't assume that without some proof. At any rate, I don't think we even have any modern algorithm candidates for something like $R$ aside from taking a $PRF(k,x)$ and fixing $k$ to be some constant.

One advantage of the constructed $KDF$ above is that it is more resistant to bad input, namely it will provide unique keys even if the input is improperly provided. Should the same entropy be accidentally given to multiple processes (perhaps due to entropy failure), you still guarantee unique keys are generated in each process due to the $N$ value. And concatenation is safer than XOR when it comes to combining a fixed value with a counter. This is because with XOR, incrementing the fixed value and calling again may create the same value after the XOR with the counter. Eg, fixed value 0x71 $\oplus$ counter value 1 yields 70, as does fixed value 0x72 $\oplus$ counter value 2. In such a case, you'd generate duplicate keys.

1) $AES(k,\cdot)$ can be used as a PRF that outputs 128 bits. (This is the premise behind the counter mode of encryption using AES.) Here, you would use $S$ as your key.

2) Conceptually, hash functions kind of look like random functions, but it is vital to understand that they are not. In cryptography theory, hashes do not have the same constraints as truly pseudo random functions (PRFs). For example, it is entirely possible that a theoretically secure hash function could leak information about the plaintext. In practice I doubt we would like a hash function that did, but nevertheless hash functions are not to be treated as random functions. In contrast, HMAC actually is a PRF, and it is conveniently built using hashes. But the construction of HMAC has advantages over plain hashes of keys concatenated with plaintext, as the latter have very concrete vulnerabilities that arise from the very fact that hashes do not have the same criteria as random functions.

3) You can use HMAC to create a KDF: Have you seen PKDF2? The implementation is fairly simple given HMAC. Or even HKDF, which is yet simpler, but I would recommend PBKDF2. The construction I outlined in the beginning using AES as the PRF would also work.