Bijection Between Real View and Simulated View

I came up with something which, I believe, avoids the probabilistic reasoning for Sigma protocol, but I will be very happy for your constructive criticism.  Before I proceed, please have a look at my modelling of sigma protocol in Coq, specifically the axiom Special_Honest_Verifier_ZKP.

Module Type SigmaProtocol.
  Parameter (Statement : Type) (* Statement x *)
            (Witness : Type) (* witness w *)
            (Rel : Statement -> Witness -> bool) (* decidable relation *)
            (RandCoin : Type) (* random coin *)
            (Commitment : Type) (* commitments *)
            (Challenge : Type) (* challenges *)
            (Response : Type) (* response *).

  Parameter  (initial : RandCoin -> Commitment)
             (challenge : Challenge)
             (response : Statement -> Witness ->
                         RandCoin -> Challenge ->
                         Response)
             (verify : Statement * Commitment * Challenge * Response -> bool).

  Parameter (simulator : Statement -> Challenge -> Response ->
                         Statement * Commitment * Challenge * Response)
            (extractor : Challenge -> Response -> Challenge -> Response -> Witness).

  Axiom Completness : forall (s : Statement) (w : Witness) (r : RandCoin)
                        (e : Challenge),
      Rel s w = true -> verify (s, initial r, e, response s w r e) = true.

  Axiom Special_Soundness : forall s c e1 e2 r1 r2,
      e1 <> e2 ->
      verify (s, c, e1, r1) = true ->
      verify (s, c, e2, r2) = true ->
      Rel s (extractor e1 r1 e2 r2) = true.

  (* Probablistic Reasoning could have made it nicer *)
  Axiom Special_Honest_Verifier_ZKP  : forall (s : Statement) (w : Witness) (e : Challenge),
    forall (r : RandCoin), verify (s, initial r, e, response s w r e) = true <->
                      forall (z : Response), verify (simulator s e z) = true.

End SigmaProtocol.

Let's take a brief detour, assume that we were doing a probabilistic reasoning, then our real view and simulated would have looked like:

Real_view (s : Statement) (w : Witness) (e : Challenge) := do
  r <- G (* generate a random value from some group G *)
  let a := g^{r} (* commitment *)
  let z := r + e * w  (* compute the response *)
  return (s, a, e, z)

Simulator_view (s : Statement) (e : Challenge) := do
 z <- G (* random element from some group G *)
 return (s, g^z s^(-e), e, z)$

 Special_Honest_Verifier_ZKP  (s : Statement) (w : Witness)
  (e : Challenge) (H : Rel s w = true) :=
  Pr [Real_view  s w e] =
  Pr [Simulator_view s e]

Based on two probabilistic view, we could have shown that two are equal. Intuitively,
in $Real\_view$, statement $s$, witness $w$, and the challenge $e$ is fixed, so the only thing that vary is the
random coin drawn uniformly from some group $G$. The probability of drawing an element uniformly
from a given set $S$ is 1/|S|, so the value of $\Pr [\text{Real_view  s w e}] = 1/|G|$.
By the same token of reasoning, $\Pr [\text{Simulator_view s e}] = 1/|G|$ which concludes that
both probabilities are equal. However, the only problem is that we are not doing probabilistic reasoning,
but not all all hope is lost.
One key observation to escape this probabilistic reasoning is
that we can make the randomness $r$ and response $z$ as
explicit parameter. Consequently, our probabilistic program would turn into
a deterministic Coq program.

Real_view (s : Statement) (w : Witness) (e : Challenge)
  (r : RandCoin):=
  let a := g^{r} in (* commitment *)
  let z := r + e * w in  (* compute the response *)
  (s, a, e, z)

Simulator_view (s : Statement) (e : Challenge)
 (z : Response) :=
 (s, g^z s^(-e), e, z)

Now that our views are deterministic, we need to find a way to model
the probability distribution of the two views. We solve this problem
by showing a bi-implication  between  the real view and simulated view.
We show that real view and simulator's view align with each other.
In terms of Coq, it is expressed as:

 (* Probablistic Reasoning could have made it nicer *)
 Special_Honest_Verifier_ZKP  (s : Statement) (w : Witness)
  (e : Challenge) (Rel : Statement -> Witness -> bool)
  (H : Rel s w = true) :
  forall (r : RandCoin), verify (Real_view s w e r) = true <->
  forall (z : Response), verify (Simulator_view s e z) = true;

The axiom $Special\_Honest\_Verifier\_ZKP$ says that for any  given
fixed statement $s$, witness $w$, challenge $e$, relation $Rel$, and assumption that $Rel$ $s$ $w$ holds,
then for every random coin $r$  and a accepting real transcript, simulator can construct
an accepting transcript from all random response drawn from response space.


Is there any identification for common encoding/encryption?

I'm not aware of any scheme. Of course, an encrypted value is often indistinguishable from random (or close to indistinguishable for most asymmetric algorithms).

You can use heuristics to determine the type of encoding, but even then you cannot always tell e.g. base 64 from encrypted base 64, or even base 64 from hex (ABCD is both valid in base 64 and hex, to name just one example). It is also generic text. Even if you determined that something is base 64 encoded then you'd be not much further. You can decode the binary value inside, but now you'd have to test what kind of value it represents.

If we suspect hashes then commonly 16 bytes is used for MD5, 20 bytes for SHA-1 and 32 for SHA-256 and so on. However, even then RIPEMD-128, RIPEMD-160 and SHA-512/256 (or SHA3-256) would have the same size, and it is possible to simply use, say, 128 bits off a larger hash function as well.

There are of course encodings that explicitly tell you what they are, such as PEM or XML encoded keys. ASN.1 / BER encoding is used a lot so testing if it complies with that is always a good idea. EC public keys (also used for ECIES encryption) commonly start with a byte valued 02, 03 or 04 and so on and so forth. PGP container format is usually easy to distinguish as well.

The type of ciphertext can usually best be determined by a human being. I'd expect the NSA to have some kind of application to guess encodings or test against classical ciphers, but commonly you need info on the protocol used to do anything useful with it.

A lot of times the used scheme is not kept as a secret if just because of the Kerckhoff principle. In that case guessing is not required.


Does salt size affect password hash security?

So, here's my question: is there a point where the salt size doesn't matter anymore in terms of security and where it might even decrease it?

The purpose of a salt is to prevent the attacker from targeting multiple users' passwords with the same try or caching common passwords' hashes in a table. You need enough salts that each user has a unique salt. After that, having more won't help, nor will it hurt (within reason).

  If there isn't a maximum salt size, does it mean that the size we choose is actually a sweet spot among performance/space for salt storage/protection against precomputed tables?

Basically, yes, although it's parallel attacks on your whole user database, rather than precomputed tables that I'd worry about.

However, there's definitely diminishing returns. If your salt is 64 bits you'd need a billion users before collisions are remotely likely. Double that to 128 bits and you can be pretty sure no one anywhere will use that same salt. With a sufficient number of users there's still a chance that someone, somewhere has used that salt value, so 256 bits would be an even more conservative choice. No use going beyond that, though.


Can Pohlig-Hellman encryption be done over elliptic curves?

I was wondering if this could be trivially adapted to be done over elliptic curves

If you don't mind the plaintexts being confined to points on the curve (as opposed to elements of $\mathbb{Z}^*_p$), then it's easy; pick a key $k$ that's relatively prime to the curve order $q$ (easy to do if you pick a curve with prime order), and then:

$$\begin{align}
Enc_k(P) &= kP\\
Dec_k(P) &= (k^{-1} \bmod q)P
\end{align}$$

Now, if you can't live with that restriction, one obvious possibility would be to use a curve with "twist security" (e.g. Curve25519), and so if the curve order is $q$, and the twist order is $q_T$ (note: $q$ and $q_T$ are the order of the curves, not the prime subgroups), then,

$$\begin{align}
Enc_k(P) &= kP\\
Dec_k(P) &= (k^{-1} \bmod q)P&&\text{if P is on the curve}\\
Dec_k(P) &= (k^{-1} \bmod q_T)P&&\text{if P is on the twist}
\end{align}$$

Curve25519 point multiplication can be done only using the $x$ coordinate, and so we can treat arbitrary values between 0 and $2^{255}-19$ as points.

Now, this construction preserves some of the properties of PH (for example, $$Enc_a(Enc_b(M)) = Enc_b(Enc_a(M))$$
but not others, for example, the question that was recently asked about combining two keys into a third that had $Dec_c(Enc_b(Enc_a(M))) = M$; that doesn't work as well; we can't define a $c$ that'll be able to decrypt both messages on the curve and messages on the twist (and giving someone both would allow them to potentially recover the values $a, b$)


Does Shannon perfect secrecy imply a deterministic encryption algorithm?

In Shannon perfect secrecy, it is assumed that $|K| = |M| = |C|$. Does this imply that $Enc$ is deterministic

Actually, the standard definition doesn't actually imply that.  It is necessary that $|K| \ge |M|$ and $|C| \ge |M|$, however in neither case does equality have to hold.

In any case, I'll proceed with the assumption that we have $|M| = |C|$ (the length of the key turns out not to matter for your question)

  Does this imply that $Enc$ is deterministic?

Yes; the pigeon-hole principal is your friend.

Consider any fixed key $k$, and all plaintexts of length $n$ (there are $2^n$ of them).  If you encrypt any one of them with the key, it will result in a ciphertext of length $n$ (and, again, there are $2^n$ possible ciphertexts).

We assume that the encryption process is invertible (that is, $Dec_k(Enc_k(m)) = m$ for any $m$), and so two different plaintexts must result in different ciphertexts.

There are $2^n$ plaintexts mapping to $2^n$ ciphertexts, and so each plaintext must map to precisely one ciphertext (pigeon-hole principle; if there was a plaintext that could map to two different ciphertexts, there must be a plaintext that doesn't map to any, and we assume that doesn't happen).

Hence, the encryption for any specific key is deterministic; that means that encryption for all keys is deterministic.


MAC tag size in AES CCM, when using CTR + CBC-MAC (not CBC MAC only)

There are different "brute force" attacks related to CBC-MAC:

Key search, which depends on key size and not the length of the authentication tag.
Tag guessing, where you just try a random tag for a modified message succeeds with probability $2^{-t}$ if the tag is $t$ bits long.

The first is not related to the tag length at all and even if you use AES-128 you are secure from it. (As long as it's a random key, anyway: e.g. a password derived key could still be guessed with a non-brute force attack.)

The second works the same whether you use plain CBC-MAC (with prefix free messages) or in CCM where the authentication tag is encrypted. By using a tag smaller than 128 bits you increase the probability of the attacker creating a correct tag at random. Whether the tag is encrypted or not, the probability is always $2^{-t}$.

Where the encryption may matter is security after the birthday bound. CCM may offer authenticity even after you have used the key too many times to offer full privacy (i.e. close to $2^{64}$ blocks). Even there the tag length gives an upper bound for security, so that fact does not justify using a shorter tag.

None of that means you must use a 128-bit tag, of course. Forging a 64-bit tag, for example, would be very unlikely. It comes down to how sure you want to be about authenticity.


Even relatively modest values for the memory and time parameters will make it very hard for an attacker to do an offline brute-force attack on your users' passwords, since they have to try so many passwords to find one.
So you should pick values that allow your servers to perform acceptably, even given the maximum rate of login attempts that you permit. Denial-of-service (DOS) attacks are a risk, so you need to use appropriate methods to limit the number of simultaneous login attempts, and throttle repeated attempts before they overwhelm your memory and CPU.
See advice on
Blocking Brute Force Attacks | OWASP via CAPCHAS, secondary delays, device cookies, unpredictable behavior, lockouts by IP address, etc. See also more generic advice on defending against Denial of Service.


Encrypting credentials and reusing them securely

The property you really want here is called Isolation.
You want all the three processes (Database, Scraper, Webserver) to run fully isolated from each other such that a compromise of the DB or the webserver doesn't end in a compromise of the passwords. So before we dive into how you can achieve this separation, let's just quickly assume we already established it and are bothered with the communication between the three modules.

Let's just quickly forget about the communication between the three modules except for when the passwords are involved (they're the most interesting part here). So you hand a public key to the webserver. Whenever a user enters his credentials for storage, you encrypt them using this public key and send the result to the database. Then your scraper will have the corresponding private key and fetch the encrypted credentials from the database, decrypt them and then fetch the data and store that in the database or send it to the webserver or whatever really.
As for the choice of primitives here: Use RSA-2048 with OAEP to encrypt a random AES key and IV and encrypt the credentials using this AES-GCM. Alternatively you may use RSA-OAEP directly on the data but this limits you to less than 200 bytes for the credentials. Alternatively you can consider using the OS's crypto services, a TPM, a secured SGX enclave or a proper HSM for private key storage.

But what does this fancy transport mechanism help you, when your webserver is compromised and an attacker can just read the private key out?
This is where isolation comes into play. Here are a few things you could do:

Clearly specify what queries the scraper and the webserver can make to the database and enforce the limitation from each individually to these queries using the database's credentials.
Consider logically or physically separating the services, ie by putting them all into different [chroot][8] jails, into separate VMs or running them on different machines.
Prefer separating the database server and the scraper script context-wise to ensure that a database server compromise doesn't lead to a credential compromise.
Depending on how often you restart the script, consider encrypting the private key of the scraper with a password, which you'd have to supply on every restart. To convert the password into a strong key, consider using Argon2d.


Differential and Linear trail propagation in Noekeon

This is due to the duality between linear and differential trails.
Let $L$ be an invertible linear map on $\mathbb{F}_2^n$, think of it as a matrix for convenience.
In general, a nonzero differential $\Delta_1 \to \Delta_2$ over $L$ must satisfy

$$\Delta_2 = L\,\Delta_1.$$

A nonzero linear approximation $u_1 \to u_2$, however, must satisfy

$$u_2 = L^{-\top}\,u_1$$

An elementary way to see this is to observe that $u_1^\top x = u_2^\top (Lx)$ is equivalent to $u_1^\top x = (L^\top\,u_2)^\top x$. This holds for all $x \in \mathbb{F}_2^n$ whenever $u_2 = L^{-\top}\,u_1$, and otherwise for half (some hyperplane) the $x$.

If $L$ is orthogonal, then $L^{-T} = L$. So then we have both $\Delta_2 = L\Delta_1$ and $u_2 = L u_1$.


Encryption based solely on XORing with concatenated hash values

1) is this a good source for randomness? Why not?

It is certainly not a cryptographically secure PRNG. In order to be a cryptographically secure PRNG, it must not be possible to predict the next output based on the current output. With your algorithm, the next output is predictable, since it's just H(previous_output) and, according to Kerckhoff's principle, you should assume the attacker knows the hashing algorithm.

  2) Does the attacker having a look at this output have any advantages in guessing the plaintext for large n?

The attacker only has to guess or know the first block of plaintext. Once the attacker knows this, decrypting the rest of the plaintext is easy: for the first block, the ciphertext C is H(password) ^ M, so H(password) = C ^ M. So once the first block of plaintext is known, the attacker knows H(password), and can calculate H(H(password)), H(H(H(password))) etc.

  3) Why is the following encryption a bad idea? You have some file you want to enrcrypt. Hash the file with a good hash function (e.g. Keccak). Then concatenate this hash with a password you choose. From this you derive a hashconcatenation like above until it is as long as the file you want to encrypt lets call it (hashchain). Then XOR your file with the hashchain and when you are finished you write the hash of the original file to the beginning of your encrypted file. Destroy original file and hashchain.

Password have the habit of having low entropy, which makes them excellent targets to brute-force. If the first block of the file's plaintext reveals any information about whether the file is successfully decrypted, the attacker only has to calculate H(plaintext_hash || password) and xor the first block to see if the attack is successful. Most hash functions are fast, and attackers can easily try millions of passwords per second.

Even if the first block does not reveal any information, if you reuse the same password, an encryption oracle attack with a chosen plaintext can choose an all-zero plaintext. Then the first block simply becomes C = H(plaintext_hash || password) ^ 0 = H(plaintext_hash || password). Since the attacker knows the plaintext hash, the password can still be brute-forced in the same way.

Given my experience with cryptography, that's probably just the tip of the iceberg.


So does that mean the advantage is: $1 - (2^{-3})$ ??

That would be the advantage if the attacker knew apriori that the key was 000; however in this model, the attacker knows that the key is one of the eight listed values, but doesn't know which one (and each of the eight possibilities are equiprobable).

So, if the attacker doesn't know what the key is, what strategy of inputs can the attacker use to get the optimal advantage?  Hint: if the attacker is restricted to a single query, what's the probability distribution of the output of the block cipher; how does that compare to the probability distribution of a truly random output?


ECDH and ECDSA are two different cryptographic primitives. The one isn't build directly upon the other. ECDH and ECDSA both rely on the same computationally hard problem of elliptic curve cryptography of course.

ECDH is a method of performing key agreement. Both parties can establish a secret value by sending only the public key of their ephemeral or static key pair to the other party. If the key pair of one of the parties is trusted by the other party then that key pair may also be used for authentication. This is however not that common. ECDH is the elliptic curve form of the Diffie-Hellman protocol (the DH in the acronym).

ECDSA is, as the name implies, a digital signature algorithm (DSA). It's the elliptic curve form of DSA. It can be used to authenticate the handshake of the TLS protocol. This authentication includes the key agreement parameters used to derive the master secret. The authentication therefore includes the correctness of the session key.

As you can see above, the actual ECDH and ECDSA may be used together in the handshake of the TLS protocol. They are however independent of each other with regards to operation. This is also why ECDH and RSA combinations can exist. ECDH and ECDSA just happen to share the same cryptographic principles.


Voronoi regions of lattices with dimensions $\leq 16$

Micciancio and Voulgaris [https://cseweb.ucsd.edu/~pvoulgar/files/voronoi_full.pdf] gave a $\tilde O(4^n)$ algorithm to computer Voronoi relevant vectors, which should be reasonable for $n=16$.
However, this may be painful to implement exactly this algorithm. Though an important remark of that paper is that you can you can deduce the $2^n$ Voronoi relevant vector by solving CVP, relatively to the $2^n$ cosets of $\frac 1 2 L$ in $L$.


Finding output given an S-box input of 8 bits

The S-Boxes of DES map from 6 bits to 4 bits. $2b$ written in binary representation is $10\ 1011$, not $001\ 01\ 011$ as you said. Now taking the first and last bit (as usual for DES S-boxes) yields us $11_{bin} = 3_{dec}$ which is the last row in your table. Taking the middle 4 bits equals to $0101_{dec} = 5_{dec}$. Now we can read the final result from the table as $9_{dec} = 1001_{bin}$


What kind of multiparty computation is this?

There are roughly two common techniques for multi-party computation, garbled circuits and secret sharing. Either may work for your situation, so I've detailed some info and recommendations about each below.

Garbled Circuits
GC is most often applied to the 2 party case. It can be made to be secure against malicious adversaries and can be fairly efficient (a single execution of AES in 1 sec on a massively parallel machine). Against a semi-honest (or honest-but-curious) adversary, a single execution of AES takes about 0.2 seconds (this is on a single thread/process).

Secret Sharing
There are many secret sharing based protocols out there. They typically aim for as many parties as desired (with a cost of extra communication & computation per party). They also can be made to work in the malicious model. Any secret sharing technique can theoretically be used, but the most efficient protocols have used (somewhat) homomorphic encryption.

The SPDZ protocol was recently used to compute an execution of AES in less than half a second with up to 10 parties. The timing result only takes into account the online phase. There is a preprocessing phase which takes more time (haven't been able to find exact numbers), but still appears to be manageable.

Fully Homomorphic Encryption
Fully-homomorphic encryption can easily be used to compute on encrypted data, in the malicious model. But, it comes with its tradeoffs. The communication complexity is much less than any of the other protocols, but (currently) the computation complexities are too large to be practical. For example, homomorphic evaluation of AES was shown to take a few days using the best of the best available FHE systems.


Key strenth in Cipher cascades (Veracrypt)

What you would do in such a case is take a master key (which could be derived from a password) of a certain length (in your cases probably 128 or 256 bit long) and use a key derivation function (like HKDF) to derive three distinct keys of equal length which can be used in one algorithm each.

This way, each of the encryption keys will have the same strength as the original masterkey and the leakage of one of the encryption keys won't affect the other ones.

  Veracrypt uses the first 1024 byte of the file so that would make a
  4096 bit master key and a 1365 bit key for every cipher in the cascade
  if I understood that right.

Just taking 1024 byte of some file will yield something with the length of 8192 bit, but the key won't have a security level of that size, since the data you are using is probably not uniformly distributed.


There is no known mathematical trick to compute iterates of SHA-1. Getting high throughput in software involves:

Use of parallelism if at all possible; that is, if starting from multiple points. Depending on why one computes iterates of SHA-1 that is possible, or not.
Specializing the code to compute the hash of a 20-byte message obtained as as hash, removing endianness conversion and padding in the main iteration. That is, to compute an $n$-iterate of a message per SHA-1:

hash the message per normal SHA-1;
convert the (bytestring) result to 5 native-endian 32-bit words, yielding the current iterate;
repeat $n-1$ times:

perform a single SHA-1 round, starting from the SHA-1 Initialization Vector 0x67452301 0xEFCDAB89 0x98BADCFE 0x10325476 0xC3D2E1F0, hashing the 16-word block consisting of the 5 words of the current iterate, 9 zero words, the word 0x000000A0 (for 160 bits), and a zero word; yielding the new value of the current iterate, manipulating 32-bit (or wider) quantities only;

convert the current iterate to (bytestring) result.

Coding and micro-optimizing carefully, perhaps in assembly. That a 73% throughput increase was achievable merely by changing compiler is telling that this counts. Among techniques likely to help:

Fully unroll the 80 rounds
Take advantage of constant words in IV and 16-word block hashed
(b&c)|((~b)&d) is ((b^c)&d)^c and that might help (or not) for rounds 0..19
(b&c)|(c&d)|(d&b) is ((d|b)&c)|(d&b) and typically helps for rounds 40..59
Schedule and choose what goes into what register wisely.

Update: on selected CPUs, there are special instructions; see this Intel whitepaper and reference code.

For the ultimate in speed, there's FPGA; an ASIC would be even faster, but wasteful.


One of the many verifiable computation schemes would be the way to go.

Something like zkSNARKs would allow a prover, Alice in this case, to prove that she performed a computation correctly without revealing the inputs to her function. These schemes require Alice to initially send a commitment of her input to the verifier. In your setup, the chunk of data Victor signs may be a commitment to the original data he sent.

To learn more about zkSNARKs, I recommend the already linked Winter School, as well as the following primer provided by Zcash: https://z.cash/blog/snark-explain.html.

Edit Just encountered this work that is relevant: ADSNARK: Nearly Practical and Privacy-Preserving Proofs on Authenticated Data (https://eprint.iacr.org/2014/617)


Can/Which encryption algorithms be daisy chained to create a cryptographic computational puzzle?

Can encryption algorithms be used daisy chained like this to create a simple computational puzzle…

It can be done, but remember encryption algos are built to be (among other things) fast/speedy while hash algos generally tend to be slower (which is the main reason why — as an example — Bitcoin uses SHA256d for its POW). This is one of a few reasons I would recommend to not use encryption algos for blockchain-alike Proof Of Work thingies.

Instead, I would recommend using hashes. An alternative would be hash based MACs (HMACs) as they allow to tweak things using a secret (what some call the password value) or maybe even things like Argon2 which allow further tweaking which (among other things) can influence speed (read: hardness to solve, while avoiding some of the main probs arising from potential ASIC and GPU implementations).

  …which encryption algorithms would be ideal for the task?

Depending on the length of your puzzle, it's going to be less a question of encryption algo, but more a question of algo type (stream cipher or block cipher) and (when using block ciphers) the mode of operation.

Last but not least, related to your

  …takes an average computer minutes to solve, …

you should be aware that computer systems differ greatly and recent CPUs even have AES functionality embedded which raises an even bigger problem when trying to balance out the several systems out there to make your puzzle fair.


Yes, Poly1305-AES can safely be modified to use AES-256 rather than AES-128; but if AES is implemented in software beware of not introducing a timing vulnerability in the implementation.

Change of the cipher in Poly1305-AES is explicitly endorsed; quoting D. J. Bernstein's The Poly1305-AES message-authentication code

  There is nothing special about AES here. One can replace AES with an
  arbitrary keyed function from an arbitrary set of nonces to 16-byte strings. (..)
  Perhaps AES will be broken someday. If that happens, users should switch to Poly1305-AnotherFunction. Poly1305-AnotherFunction provides the same security guarantee relative to the security of AnotherFunction.

The reference implementation of Poly1305-AES in software has AES carefully optimized to reduce cache-induced timing dependencies; beware that whatever AES-256 implementation is used is at least as good from this standpoint. If AES is implemented using AES-NI, in hardware, or otherwise in constant time (e.g. on a CPU without cache), that's a non-issue.

More generally, in any system using AES-128, if we can double the key size, we can safely use AES-256 instead from a theoretical standpoint; and if we can tolerate the slightly slower operation, and do not introduce a vulnerability (in particular by timing of cache misses), that's fine from a practical standpoint.


Pad ciphertext with arbitrary number of bits

After a bit of additional reading I realized that appending noise to the ciphertext doesn't affect decryption of the plaintext part. The solution is therefore quite simple:

Encrypt length + plaintext with AES, then pad the ciphertext with as many random bits as necessary. HMAC the result including the random bits.

To get the plaintext back, first validate the MAC, then trim the ciphertext down to the nearest AES block size. You can then decrypt the result back to length + plaintext + garbage.


You seem to be confusing a few things here, mainly OTP schemes and TLS.
There really is no strong relation between the two, except for maybe the case that more often than not, you use OTP schemes over TLS.

The IBM Knowledge Center links makes a reference to the pre-master secret which is encrypted using the server's public key and then used (along with client's and server's nonces) to derive the actual master secret in TLS.

In OTP schemes, the shared secret is usually generated at random with the appropriate length and then encoded for better handling.

With common RSA connections, the server doesn't actually look at the pre-master secret and just takes what you give him. More often than not, he doesn't care what it actually is.

The fact that the OTPauth string was encrypted using the server's key was probably meant as a security measure to enforce access to the server's private key to be able to give out / verify OTPs. Or it may indeed as suggested be an try to let the client pick the shared OTP secret so not all clients are screwed in case of a partial leak of the secrets.

The numbers before the secret should encode usage parameters and / or give the secret a name for further processing.


What does the "x" operator stands for in cryptography?

$\mathcal X=\mathcal M\times \mathcal R$ simply means that all elements of $\mathcal X$ have the form $(m,r)$ with $m\in\mathcal M$ and $r\in\mathcal R$. So this is an operator that takes two sets and then joins them in a tuple. This is also called Cartesian product.


Can any one explain Circuit Privacy using fully homomorphic encryption from Gentry's thesis?

Let $\rho$ be the 'initial noise level' of ciphertexts output by FHE.Enc. Fix any such ciphertexts $c_1$, ..., $c_k$.

Fix some function, written as a circuit $C$. Let $\rho_f$ be the 'final noise level' of ciphertexts output by FHE.Eval($C$, $c_1$, ..., $c_k$).

And observe that it should be easy to distinguish a ciphertext $c$ with noise-level $\rho$ from a ciphertext $c'$ with noise-level $\rho_f$, since they will be in geometrically different regions of the lattice (due observably differing noise levels).

Now, to achieve circuit privacy, we define the goal to have the distribution of ciphertexts output by FHE.Enc and the distribution of ciphertexts output by FHE.Eval be indistinguishable. Clearly, this is initially not the case (given the above discussion about noise levels).

So: To fix the problem, we "drown out" both the noise terms of size $\rho$ and size $\rho_f$ by introducing a MUCH BIGGER noise term $\rho^*$. To be specific, this means adding $c^*$ (a ciphertext encrypting 0 with noise level $\rho^*$) to the outputs of BOTH FHE.Enc and FHE.Eval.

E.g. define ciphertext $c_{re-rand} \stackrel{\rm def}{=} c + c^*$, and ciphertext $c'_{re-rand} \stackrel{\rm def}{=} c' + c^*$. (And from here on, we will be comparing the distribution of ciphertexts $c_{re-rand}$ vs the distribution of ciphertexts $c'_{re-rand}$, generated in these respective ways.)

In fact, we will set $\rho^*$ to be super-polynomially larger than $\rho_f$. Thus, statistically, since $\rho^* \ggg \rho_f > \rho$, we only need to consider the $\rho^*$-sized noise terms when arguing indistinguishability.

But since the noise terms in both $c_{re-rand}$ and $c'_{re-rand}$ that are of size $\rho^*$ were drawn independently (and from the same distribution), the distributions of re-randomized ciphertexts are indistinguishable, as desired.


No, you don't have to convert to a 32-bit string.

A "32-octet octet stream" means an octet stream with a length of 32 octets. An octet stream is also known as a byte array. In older times bytes could have different lengths (7 or 9 byte lengths have existed). An octet is always 8 bits; nowadays octets and bytes should be considered synonyms.

So basically they are saying: treat the bit string as a stream of octets of the same length (as $32*8=256$), then base-64 encode it. Now most crypto libraries already treats the output of SHA-256 as byte array (octet stream). So you just are left with encoding the output to base 64.

One small warning: some crypto libraries already contain encoding internally. You will need to explicitly choose raw byte output for those libraries, unless you can specify base64, of course.


Is RSA vulnerable to possible PRNG + Miller Rabin test weaknesses?

RSA is vulnerable to poor choice of the primes of the modulus, and there are quite a few examples of that: RNG that generates the same output on different calls (see CVE-2008-0166, smartfacts and an example in usenix 2016's best paper); or dubious mathematical shortcut to make the generation faster (see the Roca attack).

It is much less common that a bad implementation of the primality test cause disaster, because a single iteration of a correct implementation of the Miller-Rabin test is actually quite solid when the number generated is random (see FIPS 186-4 appendix F); and accidentally choosing a non-prime would most often be caught on the first use of the RSA key: an RSA encryption/decryption is a Fermat primality test for its factors, and this has excellent chances of catching a composite.


Why do general encryption key generators also take the algorithm as input?

Is it mainly for validation purpose to ensure that the input key size is correct. So, for e.g. if algorithm is AES, the key length has to be 128, 256 or 192.

Yes, indicating a name to an algorithm may be used to check for valid generation parameters, including the key size that is generally present.

For Java - the principal language assumed in the initial question - it was commonly possible to assign invalid key sizes - at least before the key is generated. In that case the code may unfortunately only fail at a later stage when the key is used. In other words, it is not a given that the implementation adheres to the fail fast design principle. There have certainly be implementation differences between versions with regards to such tests.

It is important to check if the fact that sizes are validated is specified as such in the API. Many API's will however not be clear on that, which means that you will have to test or trust the implementation; it is probably better to check for valid key sizes yourself if they are made configurable.

  Or is there more to it, that I'm not aware of?

You may not want to use a key that was generated for one specific algorithm to be used for another. Nowadays symmetric algorithms will often use fully random keys, but that wasn't always the case. For instance, DES - and by extension triple DES -  will have parity bits that should be set. Those parity bits should not be set for AES keys as they would decrease the amount of possible key values and thus the key strength.

Another reason for indicating the algorithm is for keys to be stored in hardware modules or other key stores. For instance, in a HSM the key is not just stored as a byte array. It also includes the type of the key, so it can only be used by the algorithm it was intended for. For such HSM's it is required to indicate the object type during key generation. This is only an issue for API's that allow for hardware engines / providers (this question was initially Java specific) to be configured.

In principle you could also abuse the algorithm name to indicate other configuration parameters, such as the key store. Generally you would use different generation parameters for that though. Of course you would also want to make sure that other possible generation parameters besides the name / key size are correct for the specific algorithm that you selected - which is another use case for specifying a name up front.


Why does openssl use SHA1 in ECC when I use secp384r1 curve

I need a small clarification that why openssl using SHA1 in ECC when I am using secp384r1 curve, but in rfc they are saying we should use SHA2.

OpenSSL uses SHA-1 because RFC 4492 defines the use of ECC on SSL with SHA-1. It should also support SHA-384 as defined in RFC 5289.

Which hash algorithm is used in TLS depends on the cipher suite. For example:

TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA (uses SHA-1)
TLS_ECDHE_ECDSA_WITH_AES_128_CBC_SHA384 (uses SHA-384)


Can a One way function also be its inverse?

One-way function doesn't mean that it's impossible to reverse on EVERY output.
One-way function means that's it's hard to invert on an output picked at random over the set of the outputs.

You can read in more details the definitions given in the following link:

https://crypto.stanford.edu/pbc/notes/crypto/oneway.html


SIV - Synthetic IV - S2V Construction? Benefits over a MAC or Hash?

Rogways's paper on the algorithm goes deeper into detail: http://web.cs.ucdavis.edu/~rogaway/papers/keywrap.pdf and discusses more about design rationale and provides proof (more than the RFC).

I find a lot of benefits in SIV and S2V. For me, the most important is that it can be used without nonce. The second most important is that the mode builds on widely available modes of operation, but on the other hand just using single 128-bit cipher (typically AES, just the forward cipher function). If the implementor has some SW crypto library or FIPS 140-2 validated cryptographic module available, chances are that those have AES-CTR algorithm and AES-CMAC algorithm (if they have AES-CBCMAC or AES-CBC then AES-CMAC can be built easily).

But the question was not about these benefits. So I address the questions:

Answering the first question

The operations doubling and xor in S2V construct are primarily intended to be easy to implement yet sufficiently secure. Thus,

$MAC( MAC($x$0), ... MAC($X$i)) $

instead of

dbl_Xor( MAC($x$0), ... MAC($X$i))

invokes the MAC function one more time. For typical amounts of segments in S2V this is for many implementations a slow down.

The most typical amounts of input strings to S2V include:

Plaintext or authenticated data without nonce
Plaintext or authenticated data with nonce; or plaintext with additional authenticated data without nonce
Plaintext and additional authenticated data with nonce

Because the designers wanted a function that can easily handle any of these cases, they designed S2V, which can handle any of these cases and more. It is common that additional authenticated data is factually combination of multiple separate fields and thus it can be seen as nice convenience that it can be fed to S2V as multiple separate fields rather than needing to specify format that combines the fields.

Answering the second question

The SIV mode generates 128-bit IV for AES-CTR and authentication tag with the S2V algorithm. Therefore, perhaps the most prominent benefit of alternative MAC algorithms, larger tag size, would not be realized with SIV mode. Currently many modes of additional authenticated encryption aim at simplicity to have their design depend on as few underlying ciphers and other components as possible. Using separate algorithm for MAC would go against that goal.
Additionally, similar pre-existing algorithms like AES-CCM (not cipher misuse resistant, but otherwise for many of same uses than SIV-AES) already require just one 128-bit block cipher and use only forward function.


Guessing encryption algorithm based on key and ciphertext

The normal method is to reverse-engineer whatever software produces or consumes the ciphertext. The underlying idea is that in a practical attack situation, the attacker has some known interest in breaking the system; there is context. The context usually indicates what kind of algorithm is in use.

In some cases where the code to reverse-engineer is not immediately apparent, other clues can be gathered. For instance, a smart card which can encrypt data at relatively high speed must necessarily use some dedicated hardware, so data sheets from the smart card vendor can point to what algorithms are possible.

Many communication protocols strive for algorithm agility and therefore include an explicit header about what algorithm is used. For instance, in SSL/TLS, the set of algorithms which will be used by client and server is negotiated in plain view, so what encryption algorithm is used is perfectly known to everybody, including any attacker.

Now, if you envision a formal, unrealistic setup where you are just given a black box which encrypts data with an algorithm and a key that you do not know, then guessing the algorithm details would amount as a break, in an academic point of view. Good encryption is supposed to be indistinguishable from randomness, which implies, in particular, that any secure encryption algorithm is supposed to be indistinguishable from every other secure algorithm.


Is it possible to generate an infinite number of collisions given an infinite amount of strings?

Yes and no.

SHA-512 is by definition limited to strings of at most $2^{128}$ bits long.  So there is only a finite set of possible inputs, not an infinite set.  But you're guaranteed to have many collisions even in that finite set, because there are only $2^{512}$ holes to put $2^{2^{128}}$ pigeons into.

SHA3-512,* in contrast, is not limited to any finite input space.  So there are collisions of infinitely many strings, in principle.

But you're not likely to find any.  Unless you know something about SHA-512 or SHA3-512 that I don't, you would have to try approximately $2^{256}$ before you would be likely to find a single collision.  I assure you most decidedly that ain't nobody got time for that.

* It's also silly to use SHA3-512 for any purpose.  Its design was selected for political, not technical, reasons after certain well-known news in 2013.  There's no substantive reason to use it instead of SHAKE256-512.


For us to make it exciting, let's first define the meaning of two sample messages:

$m : $ "yes, in case of m.a.d., do fire the missiles"
$m' : $ "no, do not fire missiles"

Let's guess that the current president has chosen $m$ as the message, and we the adversary (and holder of share 1) want to change it to $m'$.

Recall that the polynomial is of the following form:

$$p(x) = a_1x + m$$

We know share 1. In other words we know a value $y_1$ such that :

$$y_1 = a_1 + m $$

So now we have two values. This is enough to get the original polynomial back. We now know the original polynomial, and can reconstruct the second share:

$$
\begin{align}
p(x) &= (y_1 - m) \cdot x + m \\
y_2 = p(2) &= (y_1 - m) \cdot 2 + m
\end{align}
$$

During the recombination phase of the algorithm, the secret $m$ will be constructed by computing $2y_1 - y_2 = m$. We can rewrite this equation and compute a new forged $y_1'$:

$$
y_1' =
\frac{m' + y_2}{2} =
\frac{m' + (y_1 - m) \cdot 2 + m}{2}
$$
Which simplifies to:
$$
y_1' = y_1 + \frac{m' - m}{2}
$$

Now we have constructed a new share which will, together with the second share, combine to the new secret message $m'$.

We see that in your (my?) case we could indeed choose any new message $m'$.


So let's start with the hash functions:

$$H_n:A\times B\times C \rightarrow D$$ is the mathematican's notion for a function called $H_n$ that takes arguments from the sets $A,B,C$ (in this order) and maps it to $D$, where $B,C$ are optional. You're facing three types of sets for this:

$\{0,1\}^*$ is the set of binary bit-strings of arbitrary size, e.g. any data that can be represented as a sequence of bits
$\{0,1\}^{n+k_0}$ is the set of binary bit-strings of length $n+k_0$, e.g. any data that is exactly $n+k_0$ bits long.
$\mathbb Z_q^*$ and $\mathbb Z^*_p$ are the sets of all natural numbers smaller than $q$ and $p$ respectively.

The tricky part is instantiating these functions now. You can instantiante them using KDF2 (combined with optional concatenation) and / or using HKDF or HMAC which can all be based off SHA-256.

The input is quite simple: You just feed the data (in the appropriate representation) into the KDFs and you're done.
The binary output is also simple: The KDFs can produce arbitrary-sized outputs and you truncate what is too much (they usually run in some sort of CTR-mode internally).
The really tricky part is converting the binary hash string to an integer. The best you can do is to generate a string a little bit longer (a few bits) than what is needed for the modular reduction and then apply the modular reduction (e.g. $\bmod q$) to the converted integers. This should give a "good-enough" distribution

  Correct me if I am wrong $x$$H_1$ $(ID_A,w_0)$ means $x \times
 H_1(ID_A) \oplus H_1(w_0)$ where $x \in Z_q^*$

No, you're supposed to take it literally. You call $H_1(ID_A,w_0)$ and multiply the result (which is in $\mathbb Z^*_q$ by definition) with $x$ which is also chosen from $\mathbb Z^*_q$, e.g. $x\times H_1(ID_A,w_0) \bmod q$.


Introduction to LLL algorithm applied to linear modular inequalities

The short answer is that LLL (or more generally, lattice reduction methods) is useful when you can convert your problem into finding a small linear combination of known vectors.
Let's take your example and make it concrete. Let $m = 2^{64}$, $a = 7244019458077122845$, $b=1$, and the we have a generator that outputs the upper 16 bits of the state at each iteration:
sage: k = 16
sage: n = 4
sage: m = 2^(n*k)
sage: a = 8 * floor(m*pi/64) + 5
sage: b = 1
sage: x0 = 5183095426420329486 # randint(0, m)
sage: x = x0
sage:
sage: l = 6
sage:
sage: X = []
sage: Y = []
sage: Z = []
sage: for i in range(l):
sage:   x = (a*x + b) % m
sage:   X.append(x)
sage:   Y.append( x - x % 2^(n*k - k) )
sage:   Z.append( x % 2^(n*k - k) )

Here we have 6 outputs; that'll be enough, as we'll see later. The vector $\mathbf{X}$ represents the full state at each iteration; the vector $\mathbf{Y}$ represents what we obtain from the generator (conveniently multiplied by $2^{48}$), and the vector $\mathbf{Z}$ is the information we are missing. Obviously, $\mathbf{X} = \mathbf{Y} + \mathbf{Z}$.
Now we can indeed turn this into a less recursive function. We can represent each element of $\mathbf{X}$ as
$$
X_i = a^i\cdot x_0 + b\cdot \sum_j^i a^j \bmod m\,,
$$
where $x_0$ here is the seed we are looking for.
sage: A = [ power_mod(a, i, m) for i in range(1, l+1) ]
sage: B = [ b * sum([ power_mod(a, j, m) for j in range(i) ]) % m for i in range(1, l+1) ]
sage: assert( X[i] == (A[i]*x0 + B[i]) % m )

What we have now is a vector relation:
$$
x_0\cdot \mathbf{A} + \mathbf{B} = \mathbf{Y} + \mathbf{Z} \pmod{m} \,.
$$
We can move the $\mathbf{B}$ vector to the other side:
$$
x_0\cdot \mathbf{A} = \mathbf{Y} + \mathbf{Z} - \mathbf{B} \pmod{m} \,.
$$
Because we do not know $\mathbf{Z}$, we can't solve this, of course. But because $\mathbf{Z}$ is relatively small—made up of only 48-bit coefficients—we can do something else. All of the possible elements on the left side can be represented as combinations of the rows of the following matrix:
$$
\begin{pmatrix}
  m &   0 & \dots & 0 \\
  0 &   m & \dots & 0 \\
  \dots & \dots & \dots & \dots \\
  0 &   0 & \dots & m \\
  A_0 & A_1 & \dots & A_{l-1}
\end{pmatrix}
$$
Every vector of the lattice spanned by these rows is given by $(v_0\cdot m + v_{l-1}\cdot A_0, v_1\cdot m + v_{l-1}\cdot A_1,$ $\dots$ $, v_{l-1}\cdot m + v_l \cdot A_{l-1})$, for some integer vector $(v_0, v_1, \dots, v_l)$. Note that the multiplications by $m$ disappear when reduced modulo $m$; they are there purely to represent the modular relation over the integers (seeing that $x \bmod m = x + m\cdot k$ for any integer $k$). By definition we know that there is some point in this lattice that is equal to $\mathbf{Y} + \mathbf{Z} - \mathbf{B} \bmod m$.
Our hope is that we can find some vector in this lattice that will be in the vicinity of $\mathbf{Y} - \mathbf{B}$; that is, even if we don't have $\mathbf{Z}$, if $\mathbf{Z}$ is small enough we may be able to find $\mathbf{Y} + \mathbf{Z} - \mathbf{B}$ anyway. Let's try:
sage: t = vector([ ZZ( (Y[i] - B[i]) % m ) for i in range(l) ])
sage: L = diagonal_matrix(ZZ, [m] * l, sparse=False)
sage: L = L.insert_row(l, A)
sage: from sage.modules.free_module_integer import IntegerLattice
sage: from fpylll import CVP, IntegerMatrix
sage: v = vector( CVP.closest_vector(IntegerMatrix.from_matrix(IntegerLattice(L).basis_matrix()), t) )
sage: v
(13248830508827011990, 14756727165374399998, 10872974672493767622, 3944908843490556782, 9056698072341178742, 12371060381645645918)
sage: (vector(Z) + vector(Y) - vector(B)) % m
(13248830508827011990, 14756727165374399998, 10872974672493767622, 3944908843490556782, 9056698072341178742, 12371060381645645918)

It works! (Don't pay much mind to how this vector is found; let's pretend it's a closest vector blackbox).
Having this vector it is now straightforward to obtain $x_0$. We can use linear algebra, for instance:
sage: L.change_ring(Zmod(m)).solve_left(v)
(0, 0, 0, 0, 0, 0, 5183095426420329486)
sage: x0
5183095426420329486

Why does this work? It's complicated. But the basic idea is, if you have a lattice given by a matrix $L$ of rank $n$, its volume is given by the determinant, and the shortest (resp. closest, with some caveats) vector is known to be at most $\sqrt{n} \mathrm{det}(L)^{1/n}$ distance (usually in $L_2$ norm). In our case, that is
sage: (sqrt(L.rank())*IntegerLattice(L).volume()^(1/L.rank())).log(2).n()
53.9751060324574

But our expected distance to $\mathbf{Y} - \mathbf{B}$, i.e., the norm of $\mathbf{Z}$, is shorter than that, having norm approximately $2^{48}$ (since we are missing 48 bits of state):
sage: (t-v).norm().log(2).n()
48.4871956406101

Therefore it is highly likely that the closest vector to $\mathbf{Y} - \mathbf{B}$ is indeed our solution.
This also explains why when you leak too few bits the method stops working: the norm of $\mathbf{Z}$ becomes larger than the norm of the expected closest vectors, so you start getting unrelated vectors as the closest point. If $\mathbf{Z}$ is 63 bits, then your distance is approximately 64 bits long, which is much higher than $2^{53.97}$.
But we haven't used LLL yet. In fact, LLL does not even find closest vectors! However, up to some approximation error (exponential on the dimension), LLL does find very short vectors. If the error is not too large, LLL can serve as a decent replacement to a shortest vector blackbox. So one common approach is to turn closest vector problems, such as this one, into shortest vector problems that LLL can tackle.
One option, which uses LLL internally, would be to use the Babai nearest plane method to find a close vector. But there is a simpler trick, due to Kannan, to (heuristically) embed a closest vector problem into a shortest vector problem. The idea is to extend the lattice such that the closest vector is a short vector in it. Coupled with LLL (or BKZ), we can obtain a solution that way:
$$
\begin{pmatrix}
  m &   0 & \dots & 0 & 0 \\
  0 &   m & \dots & 0 & 0\\
  \dots & \dots & \dots & \dots & 0 \\
  0 &   0 & \dots & m & 0\\
  A_0 & A_1 & \dots & A_{l-1} & 0 \\
  Y_0 - B_0 & Y_1 - B_1 & \dots & Y_{l-1} - B_{l-1} & M
\end{pmatrix}\,,
$$
where $M$ here is an approximation of the expected distance, that is, the norm of $\mathbf{Z}$. Because we expect $\mathbf{Z}$ to be small, the vector $x_0\cdot \mathbf{A} - (\mathbf{Y} - \mathbf{B})$ is expected to be short as well, and hopefully LLL gives us a solution.
sage: t = vector([ ZZ( -(Y[i] - B[i]) % m ) for i in range(l) ])
sage: L = diagonal_matrix(ZZ, [m] * l + [0], sparse=False)
sage: L.set_row(l, A + [0])
sage: L = L.insert_row(l+1, list(t) + [2^(n*k - k)])
sage: L.LLL()
[                 0                  0                  0                  0                  0                  0                  0]
[    84830033144727     99493793228572    193251317565997    195477621437466     41221639930099    247621686570632    281474976710656]
[  -687665523248565   -558678928843390  -2831909104870979    783681348831084   3591271679705919     61017834323238    844424930131968]
[ -1823548220242427   2253638642602902  -3569730745364989   3416755876477276   -751301580596367  -2032834227000110   1407374883553280]
[  7621930640779355   -105157344785070  -3265673334549427   1969120201701820  -1755046640220593  -2112569643194890    844424930131968]
[ -1177023352112110  -3396609545281551    557994199985972  10658623678942411    804267325513190    663710453352693  -7036874417766400]
[  4998293895365537  11389134223649311  -2635952223845275   2485610916234323   4530338313613385   2884351148040487  -8444249301319680]
[  -192992080812070   5962407351033287  11672086573074080   -997631747809227   8935027883752214 -19143574866262125   5910974510923776]
sage: vector(Z)
(84830033144727, 99493793228572, 193251317565997, 195477621437466, 41221639930099, 247621686570632)

The shortest nonzero vector in this lattice is exactly $\mathbf{Z}$ (plus an extra element), the missing information to get us to $\mathbf{Y} + \mathbf{Z} - \mathbf{B}$. We can now solve for $x_0$ as before.
Long story short, if you are able to  coax your problem into a question of finding linear combinations that are either short or near some known vector, lattices might be of use. This, of course, does not even begin to scratch the surface of what you can do with lattices. The article by Joux and Stern entitled Lattice Reduction: a Toolbox for the Cryptanalyst is a good—and far more rigorous—introduction to this topic.


Crypt-analysing modified AES algorithm with no shift-rows, and no key-expansion

AES works by operating on the 16 input bytes as a 4x4 matrix of values. The state looks like:

$$\begin{bmatrix}
    x_{1}       & x_{5} & x_{9} & x_{13} \\
    x_{2}       & x_{6} & x_{10} & x_{14} \\
    x_{3}       & x_{7} & x_{11} & x_{15}\\
    x_{4}       & x_{8} & x_{12} & x_{16}
\end{bmatrix}$$

Sub Bytes

The subBytes operation operates on one entry of the state at a time, and it replaces the value of each entry $x_{n}$ with another value.

Mix Columns

The mixColumns operation operates on a column at a time, independently:

$$\begin{bmatrix}
    x_{1}\\
    x_{2}\\
    x_{3}\\
    x_{4}
\end{bmatrix}
\begin{bmatrix}
    x_{5}\\
    x_{6}\\
    x_{7}\\
    x_{8}
\end{bmatrix}
\begin{bmatrix}
    x_{9}\\
    x_{10}\\
    x_{11}\\
    x_{12}
\end{bmatrix}
\begin{bmatrix}
    x_{13}\\
    x_{14}\\
    x_{15}\\
    x_{16}
\end{bmatrix}
$$

and it outputs a new column such that each entry in the column depends on all of the entries in the column.

Shift Rows

The shiftRows operation transposes individual entries from each column so that each output column consists of 1 entry from each input column:

$$
\begin{bmatrix}
    x_{1}       & x_{5} & x_{9} & x_{13} \\
    x_{2}       & x_{6} & x_{10} & x_{14} \\
    x_{3}       & x_{7} & x_{11} & x_{15}\\
    x_{4}       & x_{8} & x_{12} & x_{16}
\end{bmatrix}
\rightarrow
\begin{bmatrix}
    x_{1}       & x_{5} & x_{9} & x_{13} \\
    x_{14}       & x_{2} & x_{6} & x_{10} \\
    x_{11}       & x_{15} & x_{3} & x_{7}\\
    x_{8}       & x_{12} & x_{16} & x_{4}
\end{bmatrix}
$$

Removing Shift Rows

If you don't use the shiftRows operation, then there is no mixing of values between columns of the state. The state would effectively consist of four separate columns that do not influence each other.

Since there are four 8-bit bytes in each column, each column would effectively become a 32-bit permutation, instead of the 128-bit permutation that AES is supposed to be.

Breaking it

32-bits is easily within the range of brute force, and is usually considered small enough to be amenable to a lookup table. While you would have to perform 4 separate 32-bit brute force attacks to recover the key, this does not take nearly as much time as a single 128-bit brute force attack. This is because each column can be attacked independently and in parallel.


What can we recover with an invalid curve attack

Weierstrass Curves point addition formulas
Consider the Weierstrass equation
$$y^2 = x^3 + a  x + b$$
Let $P=(x_1,x_2)$ and $Q=(x_2,y_2)$ be two point in the elliptic curve.

$P+O=O+P=P$
If $x_1 = x_2 $ and $y_1 = - y_2$ and $Q =(x_2,y_2)=(x_1,−y_1)=−P$ then $P + (-P) = O$
If $Q \neq -P$ then the addition $P+Q = (x_3,y_3)$ and the coordinate can be calculated by;

\begin{align}
x_3 = & \lambda^2 -x_1 - x_2  \mod p\\
y_3 = & \lambda(x_1-x_3) -y_1 \mod p
\end{align}
$$
\lambda =
\begin{cases}
\frac{y_2-y_1}{x_2-x_1},  & \text{if $P \neq Q$} \\[2ex]
\frac{3 x_1^2+a}{2y_1},  & \text{if $P = Q$} \\[2ex]
\end{cases}$$
The addition law on Weierstrass curves doesn't use the constant $\color{red}{b}$. This is the core of the attack.
Invalid curve attack
Consider that the used curve is Secp256k1 with curve equation $y^2 = x^3+7$.
Now, using the fact that the addition formulas don't use $7$, an attacker $A$ can choose a public key $(x_a,y_a)$ such that it is on another curve $$y^2 = x^3+c$$ with small order $n$. Now, you did not validate this public key and used $[a](x_a,y_a)$ as an input for the KDF to derive the key. Now the attacker can try all $n$ possible values $[i](x_a,y_a)$, $ 0 \leq i <n$ and validate the result form the encrypted message that you send.
Now, you are not aware of anything and $A$ doesn't stop there, next time chooses another point on the same curve with a different small order or carries the attack on another curve. Finally, they combine all extracted information with the Chinese remainder theorem (CRT).
Now the attacker accessed the key, and use it.
TLS
If the public key of the attacker is not validated with a CA and you assume that as it is then you have a problem.
In pre-TLS 1.3 the EDHK doesn't have to be ephemeral (ECDHE). In this case, it is called static. If you use static then the attacker can extract your key. The recorded past communications are no longer safe.
Since you computed the exchange points during any DHKE by $[d]Q_b$ with $Q_b = [d_b]G$ is the Bobs public key then they can recalculate $[d]Q_b$. After that, we can decrypt all recorded sessions.
If you use TLS 1.3 (you should) then you have to use ECDHE. In the ephemeral case, the private and public keys are generated on the fly. They are protected with signatures. In this case, the attacker can only recover the current private key that is not used for any other session.
This is good since it is the forward secrecy as defined in the original DHKE paper. To achieve forward secrecy the old keys must be deleted and this is exactly what TLS does.
Therefore it can be dangerous in pre-TLS 1.3 where static DHKE is allowed.
The countermeasures

Validate the point
The CA verifies the point and you trust the CA by a chain of trust.
Use compressed points on your protocol, during the uncompressing the validation is included.
Use EDHKE


Public key exponent coprime with totient proof

First, if $e$ is the public key exponent, then the private key exponent $d$ is the (unique) multiplicative inverse modulo $\phi(n)$, or alternatively $ed \equiv 1 \pmod{\phi(n)}$. The reason we want $d$ to have this property is because by Euler's theorem, which says $a^{\phi(n)} \equiv 1 \pmod{n}$ for essentially all values of $a$, so $(a^e)^d\equiv a^{ed} \equiv a \pmod{n}$ ensures we can always decrypt $a^e$ to $a$.

Now, how do we know $d$ is the unique multiplicative inverse of $e$? Because if there were another value of $d'$ such that $ed' \equiv 1 \pmod{\phi(n)}$, then $0 \equiv 1-1 \equiv (ed-ed') \equiv (d-d')e \equiv (d-d') \pmod{\phi(n)}$, where the last congruence holds because $\gcd(e,\phi(n))=1$. Thus, $d$ is unique.

Finally, if $\gcd(e,\phi(n)) \ne 1$, then $e$ does not have a multiplicative inverse mod $\phi(n)$. This is because, assuming $e^{-1}$ exists, then there exists some integer $k$ such that $k\phi(n) + ee^{-1} = 1$, which implies $\gcd(e,\phi(n)) = 1$.

In practice, $e$ not having a multiplicative inverse means that the sequence $a^e, a^{2e}, a^{3e}, \ldots$ may never attain the value $a$ modulo $n$.

As fgrieu points out, there are other values of $d$ that can serve as private key exponent (besides the multiplicative inverse of $e$) but we can always choose $d$ to be $e^{-1}$ and we are guaranteed that this choice will work with high probability.


Are there any practical ways to transfer random data securely?

Is it possible to securely transfer random values in such a way that they are still viable for use in cryptography?

Yes and this is done all the time.

If you use a TLS_RSA cipher suite, the client uses RSA to encrypt key material, i.e. random values, and transfer that securely to the server for key derivation.

  The owner of the random.org service recommends that you do not use randomly generated numbers from their website for use in cryptographic keys.

The reason for this is not the security of transferring the random numbers (random.org is available through TLS), but the fact that you cannot be sure they are not storing or manipulating the numbers:

  We should probably note that while fetching the numbers via secure HTTP would protect them from being observed while in transit, anyone genuinely concerned with security should not trust anyone else (including RANDOM.ORG) to generate their cryptographic keys.

So it is possible, but you would have to trust the one generating and sending the random numbers.


Can a server's ECDSA fingerprint be spoofed during SSH?

Yes OpenSSH's fingerprint is a hash of the publickey, and (except SSHv1 keys aka -t RSA1 which is long broken and should never be used) specifically of the publickey format stored in base64 in (usually) /etc/ssh/ssh_host_${alg}_key.pub which is the wire encoding in the relevant KEX-reply message depending on key type (currently RSA, DSA, ECDSA, ED25519). See https://superuser.com/questions/421997/what-is-a-ssh-key-fingerprint-and-how-is-it-generated

Traditionally this hash has been MD5, and displayed in hex with colons between each byte. OpenSSH recently (6.8 in March 2015) switched to SHA256, displayed in base64, by default; you can get the old one with FingerprintHash option on client, or -E option on ssh-keygen -l; see the man pages for ssh_config and ssh-keygen if you have a recent version, or see online http://www.openssh.com/manual.html for the latest version.

OpenSSH also supports displaying this hash (now either SHA256 or MD5) in an ASCII-art form that is supposedly easier to compare visually. IME this is rarely used. But then IME users rarely verify the fingerprint at all.

Yes, if a MitM can intercept your first connection to an SSH server AND feed you a wrong fingerprint you are pwned. The most conservative advice is you should get the fingerprint from an admin or other 'reliable' person face-to-face, or over the phone if you know their voice well enough to distinguish from an imposter, or other out-of-band secure means like registered mail. But in today's world, especially when dealing with lots of systems and many of them far away or in the cloud, this is often impractical.
If the fingerprint is on an HTTPS website (with certificate, ciphersuites and protocol version up to current standards) -- and the website itself isn't hacked (which has been known to happen) -- that's usually good enough.

But SSH clients are supposed to, and OpenSSH in particular does, remember the previously seen publickey (the whole key, not just the fingerprint) for each server, so if you get the first connection securely and MitM intercepts a subsequent connection it detects the discrepancy and gives you a big ugly error message with lots of uppercase and atsigns about 'WARNING! REMOTE HOST IDENTIFICATION HAS CHANGED! Someone could be eavesdropping on you!'.

However, if the server legitimately replaces its key(s), as they sometimes must or otherwise do, you get this same alarm, so as with all alarms that are often false, most people soon ignore them, or set the option (StrictHostKeyChecking no) to suppress them -- and advise others to do the same.
Also, if the client 'loses' its memory (for OpenSSH in the file ~/.ssh/known_hosts), you are back to the vulnerable initial connection state. For example your PC became obsolete or just unfashionable and was replaced and you didn't copy this file, or it was lost or destroyed (or stolen) and replaced, or the filesystem or disk was accidentally overwritten or corrupted and your data lost, or you just decided to delete it.


Explain mixing bijection with an example

What they are referring to as a mixing bijection is the MixColumns step of the AES round function. It functions to improve diffusion by reversibly scrambling the state of each column. Recall that the block state consists of a 4x4 matrix of byte-sized elements (totaling 16 bytes, or 128 bits), so each of the four columns are composed of four vertical elements. The MixColumns transformation is applied to each column in parallel. It is just one step of several. Together with AddRoundKey, ShiftRows, and SubBytes, it makes up a single AES round. Ten to fourteen rounds are applied to the input for a single block.

It is referred to as a mixing bijection instead of just a bijection to imply that the output is random. Not all bijections appear random of course. This isn't standard terminology, which explains the confusion. Just think of it as a bijection whose output appears fairly random, making it useful for diffusion.

I strongly recommend you read A Stick Figure Guide to the Advanced Encryption Standard (AES). It is a wonderful explanation of the intrinsics of AES, including MixColumns, and is very easy to understand.


How to properly apply the AES Mixcolums?

Do you mean where we come up with 0001 1011 (also known as 0x1B)?  That's actually mentioned in the answer:

  Multiplying by $2$ is what your question is about: it is equivalent to shifting the number left by one, and then exclusiving-or'ing the value 0x1B if the high bit had been one (where, in case you're wondering, the value 0x1B came from the field representation)

That is, the $GF(2^8)$ representation that AES uses is a polynomial representation, based on the irreducible polynomial $x^8 + x^4 + x^3 + x + 1$; 0001 1011 (or 0x1B) are the lower 8 bits of that polynomial.

If you don't understand that, well, just assume that 0x1B is a magic value that just happens to make things work...


Why is SRP considered to be resistant to MITM attack?

As has already been commented:

The fact that you can intercept and relay all messages does not actually constitute an attack on the protocol because you do not know the shared key afterwards. If the protocol partners encrypt their traffic with that key you cannot eavesdrop on it.

If this was an attack on the protocol none of the network hardware that is commonly used would be allowed to work because forwarding messages is exactly what it does.

Indeed, that means that participating in the protocol by relaying messages does not suffice for authentication.

Edit: It would be like thinking that all of your letters have been sent by the mail man. ;)


Here’s a link that shows how to implement ECDH with long term public keys and ephemeral shared keys. You could just add this authentication after the TLS handshake as it’s own layer. Think about the openID protocol.  You can publish the keys at a well-known-endpoint,  it’s not necessary to wrap them in a certificate.


Encryption in popular compression file formats - 7zip, RAR, Zip

The hash that is generated from the password is actually the derived key, and is definitely not stored inside the file (there are exceptions). It is not compared to any data, it is used for encryption and decryption.

There does not have to be something in addition to the ciphertext for the software to determine the password is correct. In many cases, decryption follows authentication, but it is not necessary to determine anything. The file will be decrypted, and decompression will most likely fail in the case of an incorrect password, if it does decompress the data will be junk.

That is of course not optimal from a usability standpoint. It is best for the user if they know the password is incorrect. That has to be done in a manner that does not give a huge advantage to an attacker. There are a several easy methods to accomplish this, here are a few of them.

1: A checksum or hash of the compressed data is added prior to encryption. Upon decryption, the data is then hashed, and compared against the decrypted hash. If it matches, it decrypted properly. This can also be done at a block level, such as every 16KB, so the correctness of the decryption can be determined earlier.

2: A "magic string" is the more common method in older encrypted archive formats. The compressed data includes some known prefix or suffix such as 0x52 0x61 0x72 0x21 0x1A 0x07 0x00 and 0xC4 0x3D 0x7B 0x00 0x40 0x07 0x00 in the case of WinRAR, and since the position of these strings should be in an expected location, decryption of those locations will reveal the string if the password is correct and the data is unmodified. This is not necessarily the way WINRAR handles it, but is just an example.

3: A secondary data encryption key is encrypted with a key derived from the password. This allows the password to be changed without reencryption of the data, and will also allow authentication of the data key component to know the password is correct, without having to look at the encrypted data of the archive.


How can I follow the validation and verification recommendations of the NaCl (sodium) secretbox library?

This is advice to you, the application protocol designer, on how to use the cryptography.  The word ‘separately’ applies to the packets, not to encrypt and authenticate: use crypto_secretbox_xsalsa20poly1305 for one ≤4096-byte packet at a time.

You should split longer messages into ≤4096-byte packets with sequence numbers.  This way:

The most memory an adversary can force the receiver to waste at a time by sending forgeries is 4096 bytes.
The least bandwidth that the sender needs in order to make progress during a denial of service attack is 4096 bytes.


This introduction and this one are well formed . Also have a look at this thesis . Notes from this course may be helpful . Oded Regev has numerous publications to the field.


How are recovery keys possible if something is encrypted using a password?

Conceptually, a recovery key is usually like a second password.  The data is typically encrypted with a data encryption key and then the data encryption key is then encrypted twice, once with a key derived from recovery key and once with a key derived from the user password.  A significant point here is that the data encryption key never changes.  If you change your password then that just results in the data encryption key being encrypted with a new key derived from the new password.
The specifics depend on the exact product that you're interested in (e.g. Bitlocker or Apple or whatever).
By the way, the above (again at a high level) is very similar to how data is encrypted using PGP and I've read that it's similar to S/MIME as well (though I've never read that spec so cannot confirm that).


How to understand RSA Proofs of correctness at Wikipedia

If $m^{ed} \equiv m \pmod{q}$, then $q\;|\;(m^{ed}-m)$;
if $m^{ed} \equiv m \pmod{p}$, then $p\;|\;(m^{ed}-m)$;
thus $m^{ed}-m$ is a multiple of both $p$ and $q$;
thus $m^{ed}-m$ is a multiple of $\operatorname{lcm}(p,q)$.

Because both $p$ and $q$ are distinct primes, $\operatorname{lcm}(p,q)=pq$ holds;
Thus, $m^{ed}-m$ is a multiple of $pq$.

So $(pq)\;|\;(m^{ed} - m)$ clearly holds.
Thus finally, $m^{ed} \equiv m \pmod{pq}$.


Multiple parties must encrypt and get the same result

Your approach is absolutely not secure.

The problem is mathematical, not technical. The search space is simply too small. There are only a finite possible number of values for an account number, and all an attacker has to do is try them all. If his output matches your stored value, he learns the account number. The technology choice of hashing with SHA-256 or encrypting with AES makes no difference.

Account numbers are 16 digits, so it looks like an attacker has to test $10^{16}$ possible values. To a specially crafted application running on a massively parallel processor like a graphics card, that's no longer a big number. (Machines capable of executing 348 billion hashes per second are now being built by hobbyists.) But account numbers  don't have that much uncertainty. Valid BIN numbers reduce the attackers job by a factor of a hundred thousand.  In your case you said you are keeping half the number visible (masking the other half), so the search space drops to $10^{8}$ possible tests.  I can also use the Luhn check digit to recover an additional hidden digit, meaning I only have to try $10^{7}$ possible numbers.

And I'm just making a guess here, based on the statement that you're revealing "roughly half" the number.  I assume you're revealing the last four digits, because you probably print those on your receipts and don't consider them secret.  And I assume you're revealing the first four digits, because they're the Bank Identification Number (BIN).  But BINs are actually six assigned digits, and given the first four I can probably determine the next two with a fairly high degree of certainty (there are far less than the 999,999 valid BINs suggested by the range).  So knowing 10 digits plus the Luhn algorithm gives me $10^{5}$ uncertain digits.  That's only a hundred thousand attempts, and I can spin through that many tests in a second on my PC without even invoking the graphics card!

The secure approach is to use a service to replace the account number with a non-mathematically-derived value, commonly called a token. Inside the secure service is where you would place the encrypted account number and perform your look-ups. An auto-generated sequence number is fine for this. Instead of giving each group the algorithm to look up an account number on their own, you grant them access to the service.

The service would need to be strongly protected against unauthenticated and unauthorized access, with audit logs tracing whoever is using it. If someone wants to run a million tests, at least you have the chance to detect them.

Also see the PCI Guidelines for advice on handling "multi-use tokens" which is this type of use.


Why is it not possible to increase the size of RSA keys indefinitely?

I've never heard that RSA becomes less secure when the modulus grows. Obviously the strength doesn't grow as fast as the number of bits, but that only means that it grows sub-exponentially.

If it keeps growing (without the growth going near zero) then there is no "trap". Check for instance here where the conclusion is that there is no exponential growth but super-polynomial growth of the time complexity (i.e. strength).

If you take a careful look at the article in Ars Technica then you'll see that the author mainly claims that the growth of the key size is not sustainable for low powered devices. ECC is certainly beneficial in those situations.

The statement "The gap between the difficulty of factoring large numbers and multiplying large numbers is shrinking as the number (ed: the key size) gets larger" is however false as fgrieu correctly identifies. It just doesn't grow as fast as you may at first assume. The key strength cannot be calculated the same way as with keys for symmetric algorithms.


Randomness and reversibility of a sequence generated by taking sha256 hashes of an predictably-changing input?

This is basically how KDF1 and KDF2 work: use a secret, add a (constant sized) label + possible other values such as a salt and then use this as input for a hash value.

Another way to look at it is to view the seed + number as a new number and then reduce the problem to the problem that Richie Frame pointed at.

So:

yes it will behave randomly
no, no information about the seed can be retrieved
truncation of hashes is a well known method, and will not leak any more information


I guess you are referring to this whitepaper, so I will refer to it in my answer.
First, I think you misunderstood part of the protocol (illustrated in Figure 1): the KDF is not AES-CFB8. A KDF is a Key Derivation Function: in this particular case, it basically acts as a hash function, transforming the inputs into a random-like stream of bytes
We assume the client and server share a secret password (or a secret password hash to be more specific). At the beginning, the send each other a random challenge, and use both challenge and the shared secret to derive a session key, using the KDF. Since we assume the server to be honest, its challenge will be random, making the session key change every session (hence the 256 tries).
AES-CFB8 is only involved after, when they encrypt each other challenge with the session key (to show that they successfully derived the session key, proving they know the shared secret).
So both challenges (nonces) are fed to the KDF, along with the password, which give you a session key. Then AES-CFB8 is used to encrypt the challenge you received, with this sesson key.

Considering the 8 bytes long ciphertext, the whitepaper is right. Indeed, raw AES process 16 bytes blocks and output a 16 bytes block. However, CFB8 mode encrypts one byte at a time, by first encrypting the IV (16 bytes, in yellow) and XORing the last byte of the result (in green) with the first byte of plaintext (in blue), and start over shifting the block it encrypt from one byte (see Figure 2). Basically, you will perform a raw AES encryption of one block (so you have the 16 bytes input-output) but you discard 15 bytes of the output (yes, this is a slow way to encrypt).
This means CFB8 make it possible to process a plaintext of arbitrary size $\ell$, without padding anything, and to produce a ciphertext of $\ell$ bytes. Here, the challenges are 8 bytes long, hence the 8 bytes' output!


One Time Pad OTP : Optimal modular base per given plaintext space?

I am assuming that your scheme encrypts $x$ to $x + k \bmod N$, where $k$ is the key and $N$ is the modulus.

If your modulus is less than the alphabet size, decryption does not work.

Suppose your alphabet size is $n$ and you work modulo $n-1$; then the plaintexts $0$ and $n-1$ are considered the same, since $0 \equiv n-1 \pmod{n-1}$. Thus, no matter your key, they will be encrypted in the same way, and when you try to decrypt, you cannot tell them apart.

If your modulus is greater than the alphabet size, you do not have perfect secrecy (hence not an OTP).

This was already covered in answers to the referenced question.


Finding the LFSR and connection polynomial for binary sequence.

This is probably just a difference in notation than any failure in
understanding or implementation. Some people define recurrence relations with subscripts in reverse order than others; the original description given by Berlekamp in his 1968 book Algebraic Coding
Theory began counting from $1$ instead of $0$ etc.  Observe that
$$x^7 + x^4 + x^3 + x^1 = x^7(1 + x^{-3} + x^{-4} + x^{-6})$$
in comparison to your $1 + x^3 + x^4 + x^6$ which you say is the
correct reciprocal of what the web site's answer should be.
So I would say that the web site seems to be following
Berlekamp's original description and giving you an answer that is "off-by-one".


Is it possible to prove the age of a document?

This exact issue was handled in great details in this article that you might want to check. In particular, this article explains in detail how their construction can be applied to timestamp documents. Basically, it shows how the methodology you describe can be made efficient for the verifier. The intuition is that rather to hash a chain, the prover will hash the nodes of a graph with some particular structure (a depth-robust graph, to name it). Because of this structure, the following efficient verification procedure can be used:

The prover hashes the entire graph
The prover computes and sends a Merkle commitment of the entire hash graph (this allows to commit to an arbitrary bit string and open the bits at a given position succinctly, i.e. in time logarithmic in the size of the string)
The verifier queries random nodes of the graph; the prover open these nodes and their parents
The verifier checks that the openings are correct and that each opened node was correctly hashed from its parents.

Because of the structure of the graph, repeating the last two steps a polylogarithmic number of times is sufficient to ensure that the prover correctly hashed a long chain in the graph; if the hash function is inherently sequential, this proves that he invested some long computation time.

Several alternatives to the above method are possible. To list a few:

Proceed exactly as you explained, and add a succinct zero knowledge argument that proves that you did the correct computations. Such a succinct argument can be constructed e.g. using probabilistically checkable proofs in the random oracle model, or from various kinds of knowledge-of-xponent assumption.
Use the following nice idea from this article: some designated verifier generates the secret key for an RSA scheme, and sends the public modulus $n$. "Hashing" is simply done by squaring mod $n$ - i.e., the $t$-time function is $f:x \mapsto x^{2^t} \bmod n$. This is expected to be impossible to speed up without the secret key. However, with the secret key, verification is very fast: the verifier simply computes $t' = 2^t \bmod \phi(n)$ and then $x^{t'} \bmod n$, in total time logarithmic in $n$, and checks that he got the same result.


How many points in RSA, such that $m^e = m \bmod n$

Why is that so?

Well, we have $m^e \equiv m \pmod n$ if and only if both of the following hold:
$$m^e \equiv m \pmod p$$
$$m^e \equiv m \pmod q$$
We know (because of reasoning you accepted) that the number of solutions to the first equation (for $0 \le m < p$) is $\gcd( p-1, e-1) + 1$; we can write out the list as $m_0, m_1, ..., m_{k-1}$ (for $k = \gcd( p-1, e-1) + 1$).
Similarly, we can write out the solutions to the second equation (from $0 \le m' < q$) as $m'_0, m'_1, ..., m'_{k'-1}$ (for $k' = \gcd( q-1, e-1 ) + 1$).
Then, the question comes down; how many ways can we paste $m \equiv m_i \pmod p$ and $m \equiv m'_j \pmod q$ so to satisfy both equations (for $0 \le m < n$).  It turns out (because $p$ and $q$ are relatively prime) that for a specific $m_i, m'_j$ pair, there is a unique value $m$ that satisfies both (and that's the Chinese Remainder Theorem).  Each $m$ which corresponds a solution is formed by such a joining, and so the total number of solutions is the number of $m_i$'s times the number of $m'_j$'s; that is, $(\gcd( p-1, e-1) + 1) \cdot (\gcd( q-1, e-1) + 1)$


How to prove correct decryption in Goldwasser-Micali cryptosystem

Goldwasser Micali encrypts a 0 by sending a quadratic residue and a 1 by sending a non-quadratic residue. So, to prove that the encrypted bit is 0 what you need is a zero-knowledge proof of quadratic residuosity: for a given $b,N$, does there exist an $a$ such that $a^2 = y \bmod N$. There exist such proofs, and it should be easy to find online. However, for 1, that would be harder since in general it's harder to prove that something does not exist (naively, this would be a co-NP statement, which doesn't necessarily have an efficient proof). So, the idea is to try to change what you are looking to prove to something easier. The Goldwasser Micali public key includes a value $x$ that is not a quadratic residue. Then, an encryption of 1 is generated by choosing a random quadratic residue and multiplying it by $x$. Given this, you can prove that a value $b$ is an encryption of the bit 1 by first dividing by $x$ and then proving that the result is a quadratic residue (i.e., prove that $b \cdot [x^{-1} \bmod N] \bmod N$ is a quadratic residue). Note that the inverse can be computed using GCD, so that's easy.


Key exchange is notoriously hard to get right, and I strongly recommend not to do your own (unless your security requirements are really minimal). For example, what you propose does not provide forward security, which is generally considered of great importance in key exchange protocols. The good news is that there is a paper doing exactly what you need; look here. I haven't looked at the details of it, but by the abstract it sounds very efficient (albeit, not as efficient as your proposal, but giving you provable security with properties like forward security as well).


KeeLoq works on 32 bit blocks as opposed to arbitrarily-sized inputs. This by definition makes it a block cipher.

There's even this from the first paragraph of Microchip's description:

  KEELOQ is a proprietary block cipher based on a block length of 32
  bits and a key length of 64 bits.

edit: the diagram is rather unclear. The input and output both end up in the 32 bit register (NLFSR) and the key goes into the 64 bit register (FSR).

For a clearer diagram, see pages 3 and 4 of this Keeloq cryptanalysis paper which at least gives some temporal dimension to the diagram.


What is the impact of the Goppa code distinguisher on the CFS and McEliece?

Why the CFS signature is affected

Let us review the structure of the CFS signature, which is strongly related to the Niederreiter PKE scheme.

In the Niederreiter PKE scheme, a public key is $H \in \mathbb{F}^{n \times k}$, which is a scrambled parity-check matrix of the Goppa codes.
A plaintext is a decodable error; for example, we set $S = \{\vec{e} \in \mathbb{F}^n \mid H_w(\vec{e}) \leq t \}$ for some $t$ as a plaintext space. A ciphertext is a decodable syndrome of $\vec{e}$, that is, $\vec{c} = F_H(\vec{e}) = H \cdot \vec{e} \in \mathbb{F}^{k}$.

This mapping is not surjective. In other words, there are several undecodable syndromes.
The ratio of undecodable syndromes is in proportion to the ratio of the code.
The higher a ratio of code is, the lower a ratio of undecodable syndromes.
Therefore, the practical CFS signature requires the code to be high-rate.

The security proof of the CFS signature scheme goes as follows:

The original security game.
Exploit the random oracle in order to remove inversion. In each query, choose $\vec{e}$ and define the hash value $RO(i,m) \gets F_H(\vec{e})$.
Replace the public key from a scrambled parity-check matrix $H$ to a random matrix $H_{\mathrm{random}}$.
Now, we reduce the game to the syndrome decoding problem.

In several parameter settings, the high-rate code distinguisher falsify the argument at Step 3.

Why the McEliece/Niederreiter encryption is less affected

A one-line answer is that the above PKE schemes can be constructed from low-rate codes.

In the PKE schemes, a decryptor has no need to be able to decrypt any ciphertexts.
Hence, we can employ relatively low-rate codes, on which the high-rate distinguisher you referred fails.


Can GnuPG be used with a login system?

Yes, there are ways you could do that.

But…

While possible, there are two things that immediately pop into my mind:

Public key crypto can be somewhat slow, which might or might not cause resource problems on the clients as well as on your server… depending on the number of users that simultaneously try to login, and how exactly you implement things.
Expecting users to decrypt a file to get a temporary login password (as you describe) doesn't seem to be very handy from a usability and UX point of view. Yet, that doesn't mean your idea would not be possible as a "proof of concept"… I just don't think it would be very practical. After all, you're putting a lot of burden on the client here (additional work of decryption, introducing additional steps since client first needs to download the encrypted password file, etc.) which – if you think about your idea twice – is rather unneccesary if you use a secured (read: HTTPS) connection. And you need to, otherwise, your Public-Key-Login-Adventure might be an easy target for MITM attacks. Sure, you can try to work around those too… but why invent a square wheel (your idea) if there is a good, secure, and working round wheel (SSL/TLS) available already.

I'ld say this boils down to a case of "just because you could, doesn't mean you should".


My name is Zhenfei Zhang. I work for Security Innovation Inc., which acquired NTRU Inc. in 2010.
The R-LWE based key exchange [1] uses a public matrix $a$ which may be manipulated.
For instance, if $a$ is an NTRU style public key, i.e., $a = g/f$ where $g$ and $f$ are short, then one can break the system by recovering $f$.
In particular, the cited paper suggested that one can use Grover to accelerate the search for $f$.
This is a known issue to the community for a while.
The NewHope paper [2] addresses this by having $a$ to be an output of a hash function at the run time of the client.
So under reasonable assumptions, no one is able to manipulate the public matrix $a$.
Will this affect NTRU? The answer is NO, if NTRU is used correctly.
NTRU uses structured public key $a$ to enable efficient computation. Hence it has a trapdoor by design.
So if NTRU is used in a Diffie-Hellman type key exchange, where $a$ is generated by a (trusted) third party,
then yes it may be vulnerable to this threat.
However, the correct use of NTRU, in a key exchange protocol, is to instantiate it via a
key encapsulation mechanism (KEM), such as [3] [4].
In those cases, the client generates the public key (as the public parameter $a$ in R-LWE based schemes).
And only the client knows the trapdoor.
In this case the attacker need to run the Grover's algorithm to find the trapdoor.
This is as hard as using Grover's algorithm to break NTRU.
The parameter sets proposed in [5] ensures that this attack is impossible.

Thank you for your response. Are you referring to the hybrid attack from [5] in the context of the parameters from section 8 in [5]?

Yes.

I also see that you do specifically address concerns related to f(1)≠0mod2 Thank you, again.

It is not just the $f(1) \neq 0 mod 2" part. In [5] the algorithm is a CCA-2 secure encryption algorithm, which rules out the inversion oracle [6] required by the "Unstructured Inversion" paper.

It also looks like the Unstructured Inversion pre-print is focused more on the approximate x-coordinates rather than modifying the public matrix a.

The "Unstructured Inversion" paper is not in enough details, so the following are my guesses, and may be incorrect. Overall, imho the  paper relies on several very strong assumptions.

there exist a trapdoor in (R-)LWE public key $a$, which is not known by the attacker.
This is a rare situation, as either the attacker inserted the trapdoor (as in attacks against [1]), in which case he already know the trapdoor and hence do not need to perform this attack;
or $a$ is generated truthfully by the client (as in the solution in [2]), thus there does not exist a trapdoor. It is a strange case where someone (but not the attacker) generates $a$ with trapdoor but the attacker does not know it. If the client follows the protocol correctly this shall never happen.

the existence of an inversion oracle.
The inversion oracle is a stronger oracle than a decryption oracle used in CCA definitions. In addition, in both newhope style and NTRU-KEM style key exchange, the public parameter/key is used only once. It is very unlikely such oracle exists for ephemeral keys. In other words, if there exist such an
oracle that works on ephemeral keys, there may be much stronger attacks than the one described in the paper.

[1] https://eprint.iacr.org/2014/599
[2] https://eprint.iacr.org/2015/1092
[3] https://eprint.iacr.org/2015/287
[4] https://tools.ietf.org/html/draft-whyte-qsh-tls12-02
[5] https://eprint.iacr.org/2015/708
[6] http://cseweb.ucsd.edu/~pmol/Publications/Recovering%20NTRU%20Secret%20Key%20From%20Inversion%20Oracles.pdf


curve25519 weak points for contributory behaviour

There are actually only 5 unique $x$-coordinates one needs to be concerned about:

$(0, \ldots)$
$(1, \ldots)$
$(-1, \ldots)$
$(x_1, \ldots)$
$(x_2, \ldots)$,

where

$$\begin{eqnarray}
x_1 =& 393823572354896145817230607815530211125 \\
     & 29911719440698176882885853963445705823
\end{eqnarray}
$$
and
$$\begin{eqnarray}
x_2 =& 32560625091655743179598362635611063129 \\
     & 4008115727848805560023387167927233504
\end{eqnarray}.
$$

These correspond to the $x$-coordinates of points of small order on the curve and its twist, as you have pointed out. The remaining values you see are the multiples of those $x$-coordinates below $2^{256}$:

$0 \equiv 2^{255}-19 \equiv 2(2^{255}-19)  \pmod{2^{255}-19}$
$1 \equiv 2^{255}-19 + 1 \equiv 2(2^{255}-19) + 1 \pmod{2^{255}-19}$
$2^{255} - 19 - 1 \equiv 2(2^{255}-19) - 1 \pmod{2^{255}-19}$
$x_1 \equiv 2^{255} - 19 + x_1 \pmod{2^{255}-19}$
$x_2 \equiv 2^{255} - 19 + x_2 \pmod{2^{255}-19}$

These extra values are checked because curve25519 was designed to accept any $256$-bit string as public-key, and each value has one or more 256-bit representations modulo $2^{255}-19$.


Multi signature encryption (multiple people can decrypt)

Sure. First of all, to encrypt a large amount of data you just require a single secret key. So now we've reduced the problem to a single small key instead of a large swath of data. Let's call this key the data key.
Now the easiest way of encrypting for multiple parties is for each party to send you their specific public key. Then you encrypt the data key with each public key and include the results with the ciphertext. This will increase your ciphertext of course, but you should be able to limit to N times the size of the encrypted data key.
There are also schemes such as Shamir's secret sharing where you can do M out of N encryption / decryption.


Corelating between the concept of Universal Hashing wrt Algorithms (hash-table use) & the use of Universal Hashing in a one-time MAC

For simplicity, if I assume a single block of message, then how do I use this universal function to evaluate the hash?

We shift some parameters from being part of the concrete function instance into the key.
For your example of $h_{ab}(d)=ad+b\mod p\mod m$ the following mapping is usual:

$d$ is the input to be hashed
$a$ is the secret key of the instantiation, reusable across multiple invocations
$b$ is the whitening value, it must be freshly random and hidden from adversaries for each invocation
$p,m$ are system parameters that depend on in which field you want to work and into which you have to encode your result, e.g. you could pick $p$ to be a relatively large prime and $m=2^k$ for some $k$.

Alternatively, if you insist on having only two non-parameter inputs, you can also force $a$ to have the same usage constraints as $b$ and declare them both "the key".


Why I can get a key from frequency in Caesar Cipher?

This will make it more clear:

A B C D E F G H I J ...
0 1 2 3 4 5 6 7 8 9 ...

The Caesar cipher starts with the letter and goes through the alphabet using the key, wrapping around after 'Z'. So if 'I' is the most common letter then this is probably the enciphered letter 'E'. And since index('I') - index('E') = 8 - 4 = 4, that's the key that was used.

Note that E is only the most common letter for English text and only if other characters like space are not counted. It may not be the most common letter in small ciphertext.


Steganographic embedding of an RSA-encrypted message into an image

If I'm reading your question correctly, you want to hide an RSA encrypted message within a 256x256 BMP file and you're wondering how this can be done as each pixel only has a range of $[0;255]$.

This is fairly easy, as your message is likely to be shorter than the $256\times256=65536$ least significant bits at your disposal.

You first simply encrypt the message you want to send using standard RSA. This will usually result in a cipher text of length 2058 bits. You then go ahead and inspect the first (= least significant) bit of the cipher text. If it is $0$, you set the least significant bit of the first byte in the first row to zero. If it is $1$, you set the least significant bit of the first byte in the first row to $1$. You repeat this until you reach the end of your cipher text and go until the end of the row. If you reach the end of the row, you go ahead and continue in the next row. Once you reach the end of the cipher text you'll just treat the rest of the message as $0$.


How to get the datapacket from wireshark?

It is expected that is not possible to

  get the application data packet with the length of my tweet data

in clear even if it was additionally obtained all long-term secrets involved. Exceptions involve exploiting deficiencies (e.g. a poor Random Number Generator, some side channel..), or going from passive eavesdropping to performing an active attack (this requires obtaining a rogue certificate, which at least is difficult for most except state actors).

That's because TLS_ECDHE_ECDSA_WITH_AES_128_GCM_SHA256 specifies negotiation of an ephemeral session key using Elliptic Curve Diffie–Hellman key Exchange (ECDHE). That session key is used for AES encryption of the session (including the tweet), then forgotten. This prevents deciphering the application data packet.

But is possible to get at the length of the data packet containing the tweet (wireshark displays packet length), and from that to estimate the tweet length.  Per Dave Thompson's analysys, the packet size minus 24 bytes gives the tweet size (assuming no compression or fragmentation).

In captures of two experiments made with a short then with a long tweet, the packet with the tweet can be identified as the one which size grew by the difference in tweet size.