Why the contrapositive proves a given hash is collision resistant?

The reason is that you are trying to make a statement about the hardness of a problem. You want to prove

  A is hard $\Rightarrow$ B is hard

This is a statement about the non-existence of an easy solution. Every solution for A is hard. You want to show

  every solution for A is hard $\Rightarrow$ every solution for B is
  hard

Constructively tackling this problem would require showing that ALL solutions for B are hard but you probably do not even know all solutions.

By inverting the problem you get

  there is a non-hard solution for B $\Rightarrow$ there is a non-hard solution for A

which only requires a statement about all solutions of A. Which you happen to already have. Namely that there is no non-hard solution.


Why does LastPass hash their passwords with PBKDF2 this way?

Can you explain what using PBKDF2 with 1 iteration is doing in the above?

  Is this the same as just doing something like a HMAC SHA256 hash?

This is mostly HMAC-SHA256, but you can declare how many bits of derived key you want. I assume it is used this way for ease of implementation (it's easier to have one working implementation of PBKDF2 than many primitives arranged in complex way).

  Are there any concerns with something like a compromised server receiving this hash and being able to derive anything from it about the original encryption key or master password (prior to the stored hash being computed)?

No, this is nearly impossible to do because as long as SHA256 is one way. It is very unlikely that SHA256 will be broken in such way (MD5 and SHA-1 have collision attacks only). If anything, this will leak if password was changed, because there is no random part added before it is sent to server, which is design flaw (unless they do something extra which you omitted).

Also, as SEJPM noticed, it is weird that only 5k iterations are done on user device and 100k iterations on their server. This would put server in better position to perform a brute-force attack. However, 5k iterations on client seem very low for most computers, and probably should be adjusted anyway.


In principle raw SHA2 is suitable for deriving an AES key from a DH shared secret.

But the "proper" solution is to use a KDF. My preferred choice is HKDF, which can use SHA256 as the underlying hash function. It allows you to derive several named key and keys longer than 256 bits from a single secret.


The responsibility of the user of Curve25519 for DHKE is Section 3;

The legitimate users are assumed to generate independent uniform random secret keys. A user can, for example, generate 32
uniform random bytes, clear bits 0, 1, 2 of the first byte, clear bit 7 of the last byte, and set bit 6 of the last byte.

This is a guarantee that the legitimate users are not in the small subgroup.  Remember the cofactor ($h = \#E(k)/n$) of the curve Curve25519 is $h=8$ which means that there are small subgroups of Curve25519. The order of the subgroups are  $2,4,8,n,2n,4n,8n$.
Now, the attacker may choose one of the small sub-group to use the Lim–Lee active small-subgroup attacks. This attack is very effective if the co-factor has many small factors. Then, the attackers can use CRT to combine the results.
The attacker will choose a $P$ which has a small order where the discrete logarithm is easy. During the protocol, the legitimate user will reveal $[a]P$ to the attacker. Now, how much information can the attacker learn about $a$ from $[a]P$?

The answer is given as information revealed by $[a]P$ is at most $\lceil log_2 h\rceil$ bits.

If the responsible users select their secret $a \equiv 0 \bmod h$ then $[a]P = \mathcal{O}$ for any small order, so they will expose nothing!
If you don't take responsibility then you need validation! During DHKE, for every public key you have to look at $[8]P \stackrel{?}{=} \mathcal{O}$. This has a cost of 3 doubling; $[8]P = [2]([2]([2]P))$. And, finally, to make sure that $P$ has order check $[n]P = \mathcal{O}$ with a cost of $\mathcal{O}(
log_2 n)$ by the double-and-add algorithm.
Which one is better? Of course, obeying the suggestion, no need for validation and no leak of information about the secret.

The validation can be hard for some curves, There is an article about this;

2003 - Validation of Elliptic Curve Public Keys by Adrian Antipa,Daniel Brown, Alfred Menezes, and René StruikScott Vanstone
They defined a point is valid if

$P \neq \mathcal{O}$
The $x$ and $y$ coordinates of $P$, $x(P),y(P)$ are valid elements of the field.
$P$ satisfies the curve equation ( the twist attack )
Check $[n]P = \mathcal{O}$ for prime curves ($h=1$) and check $[h]P \neq \mathcal{O}$ for non-prime curves ($h>1$).

Twist attack
An attacker, instead of sending a valid point $P$ as a public key, can choose to send a point on the quadratic twist of the curve where the group order is low. If the receiver doesn't check this (3. case) then it may be vulnerable to this. Curve25519 is also secure against this attack if the user takes responsibility during the key generation;

The twist of Curve25519 has an order $4p_2$ where prime $p_2 = 2^{253} − 55484635554744707071703875581767296995$. Therefore. Its small subgroups are $2,4$ and with the choice of the secret key, the user secure against these, too.

Why do we need uniform random secret keys?
There we some protocols [1] [2] that used fixed byte of the key, or low hamming weighted key for performance ( named restricted exponents 3.59 of HoAC). If the Hamming weight is $t$ of $k$ bit than there are $\binom{k}{t}$ such keys, the Shank's baby-step giant step can be modified to search in $\binom{k}{n/2}$-time. This is investigated by Heiman in 1993.

Does this mean that each $x$ coordinate could belong to a point $P=(x,y)$ from Curve25519? Is that even possible?

A point $P$ is in either on the Curve25519 or on its quadratic twist. A point $(x,y)$ is on the curve iff its satisfies the curve equation $$y^2 = x^3 + 486662 x^2 + x \text{ over } \mathbb{Z}/(2^{255} - 19)\mathbb{Z}$$


With known ciphertext and plaintext, find other party's Three Pass Protocol Key?

how difficult is it for me to determine the key that Bob is using?

This is essentially the discrete log problem; Bob's key is a value $b$, and his encryption mechanism is computing the value $P^b \bmod p$.  Given $P$, $P^b \bmod p$, recover $b$ is the definition of discrete log.

Actually, you get two pairs of values encrypted with Bob's key; the plaintext (encrypted in step 1, and recovered in step 4), and the exchanged ciphertext (which you see encrypted in step 2 and decrypted in step 3); however having multiple pairs doesn't actually make the discrete log problem any easier.

So, if the group is large enough to make the three pass algorithm secure (for example, large enough that someone hearing the values in steps 2 and 3 could not recover Bob's key), it's also large enough to make recovering the symmetric keys by you infeasible as well.


How to encrypt sensitive files in a business application? Is it needed?

Or it would be better if we would concentrate on the infrastructure's security, because it is not frequent to encrypt files for a business application?

If an attacker gains access to your server he can just steal, modify or delete all kind of data. This is not a desired consequence to suffer if someone breaks your security. Specially if the sensitive data is in plaintext.

For example, in the case you store files, the attacker can modify them to alter their functionality to install malware in the user's computer.

  If I derive a key from the file uploader's password, other, authorized people won't be able to decrypt the file.

In your scheme, every user will have two keys, one for encryption and the other for providing integrity and authentication via MAC. This is done applying a key derivation function to a Master Key. In the case your server get compromised and the user's data gets modified, the legitimate user will notice the modification since tags are not equal.


How to prove a function is pseudorandom function?

As it is, there is not enough information, in particular on functions A and B, to answer. However, here are elements that may help:

  Is the above function using A and B a pseudorandom function as it is using LFSR to produce cipher text?

As mentioned in the comments, even if the LFSR does outputs completely random numbers (which I doubt), there is no guarantee that F is pseudorandom. As far as we know, A and B could be deterministic functions, always outputting, say 42.

  If the above function is pseudorandom then how to prove it mathematically?

You would have to use a proof by reduction, such as one depicted in this video tutoral. That is, you do not prove directly that your function F is pseudo-random. Rather, you would prove, in your case, that IF the LFSR function (or function B maybe) is pseudo-random, THEN F is pseudo-random.

  Can any function which uses LFSR as the random number generator be considered CPA secure?

IND-CPA is a property for encryption. There is some relation between encryption and pseudo-randomness, but not as you seem to be saying. Generally, an encryption scheme need to use a good pseudo-random number generator (or a truly random number generator) when used in practice, but that does not take part in the cryptographic proof of IND-CPA. Thus, short answer here would be: no, even if LFSR is somehow truly random. You need other assumptions, and to study a particular, fully defined encryption scheme.

Hope this helps. It may be possible to answer more clearly if the functions $A$ and $B$ were defined.


Proof that MACing a hash of the message is also a secure MAC

The generic model for a MAC is the following: the attacker is given access to a block box which implements the $S$ function with a key $k$ that the attacker does not know of. The attacker is allowed to make $q$ requests to the box on messages that he can choose arbitrarily. The goal of the attacker is to make a forgery, i.e. produce values $m$ and $t$ such that $V(k,m,t) = \mathbf{true}$ but $m$ is distinct from all the $q$ messages sent as requests. In other words, the attacker obtains $q+1$ valid message+MAC pairs from only $q$ requests.

Now, suppose that a forgery is possible on $S^{big}$. This means that the attacker can send $m_1$, $m_2$,... $m_q$ to the box implementing $S^{big}$, obtain $t_1$, $t_2$,... $t_q$, and somehow compute $m$ and $t$ where $m$ is distinct from all the $m_i$, and $V^{big}(k,m,t) = \mathbf{true}$. Then look at $H(m)$ and compare it to all the $H(m_i)$; exactly one of the two following must hold:

If $H(m) = H(m_i)$ for some $i$, then, by construction, the attacker found a collision on $H$.
If $H(m) \ne H(m_i)$ for all $i$, then the attacker implicitly made $q$ requests to $S$ (for all $H(m_i)$) and then computed $m$, which means that $H(m)$ and $t$ are such that $V(k,H(m),t) = \mathbf{true}$. The attacker then succeeded at a forgery attack on $S$: he computed a pair containing a short message ($H(m)$) and a token $t$ which are accepted by $V$, and yet at no point was that exact $H(m)$ sent to the box implementing $S$.

It follows that if $S$ is strong against forgeries and $H$ is collision-resistant, then $S^{big}$ must also be strong against forgeries.


What does "learnable with oracle queries" mean?

A family $\mathcal{C}$ of circuits/functions is "learnable with oracle queries" if there is an efficient "learning" algorithm $L$ that, given oracle (or "black box") access to any $C \in \mathcal{C}$, outputs a circuit $C'$ (or other representation) that is equivalent to $C$, i.e., it agrees with $C$ on all inputs.

Oracle ("black box") access to $C$ means that $L$ can repeatedly query any values $x_i$ in the input domain of $C$, and receive $C(x_i)$ as the answer.  Note that $L$ does not see how the output value $C(x_i)$ is computed, how many steps it takes to do so, etc.  It just gets the value itself.

For example, consider the class of functions $\mathcal{C} = \{C_w(x) = \langle x, w \rangle \bmod 2 \}$.  Each function $C_w(x)$ is simply the mod-2 inner product of some fixed $w \in \{0,1\}^n$ with the input $x \in \{0,1\}^n$.  (This is often called the class of "parity" functions.)  This class is learnable with oracle queries: given oracle access to some $C_w$ (where $w$ is initially unknown), the learning algorithm simply queries its oracle on $e_1=(1,0,\ldots,0)$, and receives $C_w(e_1) = \langle e_1,w\rangle = w_1$.  It similarly queries all the other standard vectors $e_i \in \{0,1\}^n$, and receives each bit $w_i$ in response.  After $n$ queries it knows $w$ entirely, which is equivalent to knowing a circuit for $C_w$.

What this has to do with obfuscation: if a class $\mathcal{C}$ is learnable by oracle queries, then one can obfuscate (according to the "virtual black box" definition) any code that computes a member of that class.  The obfuscator is essentially just the learning algorithm: given any program/circuit that computes a function $C \in \mathcal{C}$, the obfuscator simply uses the code to answer the queries of the learning algorithm (by just running the code on the query).  The obfuscator then outputs whatever code/circuit $C'$ the learning algorithm outputs.

This is a VBB obfuscator because a simulator that is given only black-box access to the function $C$ can do exactly the same thing (run the learning algorithm, using the oracle to answer queries).  Notice, however, that this obfuscator is not actually "hiding" anything about the function that it's obfuscating; in fact, it's arguably revealing everything about that function!  This still comports with the VBB definition of obfuscation, however, because any code that computes the function reveals everything about the function.  So one might as well give out a "canonical" representation of the function, like the one computed by the learning algorithm.


Is the hash function $h(x\|y) = AES_x( y)$ collision resistant?

It isn't even second-preimage resistant. Hint:

   $y = \mathrm{AES}^{-1}_{x}(\mathrm{AES}_{x}(y))$

For any 128-bit string $x_1$, $x_2$ and $y_1$,

   $h(x_1||y_1) = \mathrm{AES}_{x_1}(y_1) = \mathrm{AES}_{x_2}\left(\mathrm{AES}^{-1}_{x_2}(\mathrm{AES}_{x_1}(y_1))\right) = h\left(x_2 || \mathrm{AES}^{-1}_{x_2}(\mathrm{AES}_{x_1}(y_1))\right)$

Follow-up question: is it preimage-resistant?

   $h(x||y) = \mathrm{AES}_{x}(y)$ so $y = \mathrm{AES}^{-1}_{x}(h(x||y))$. For any hash value $H$ and any 128-bit string $x$, it's trivial to calculate a preimage that begins with $x$.


Some simple questions about tweakable ciphers

Suppose the tweakable cipher uses a secret key $k$ and a secret tweak $t$, then syntactically you can regard $K=(k, t)$ as the total secret key.  So, in this case, the 'tweakable cipher' is just an ordinary block cipher, with a longer key.  In order to get a notion different from the usual block cipher, you'll need the tweak to be non-secret.


As D.W. said, your questions are not very clear. I interpret your first question as asking how the security of an $\epsilon$-PRP varies with $\epsilon$. The answer to this is quite clear from Tessaro's introduction: $\epsilon=0$ corresponds to the standard definition of PRP (also called fully-secure PRP in the paper). As $\epsilon$ grows, the security weakens. If you push to $\epsilon=1$ (which is not permited by the definition), there is no security left.

So the highlighted sentence in your question means that the assumption that AES is very weakly secure (0.99-PRP) is much weaker (and thus more likely) than the assumption that AES is fully secure.

Concerning your second question: The problem solved in the paper is to show that a cascade of $\epsilon$-PRPs with independent keys becomes more and more secure as the number of ciphers in the cascade grows. For $\epsilon\geq 1/2$, this was unknown from previous papers.


How do disk encryption programs solve the "IV problem"?

The problem is not to store an IV but to store an authentication tag.

I don't know about any other products that solve this problem in a way similar to BitLocker. LUKS uses XTS by default, and TrueCrypt supported LRW and XTS, among other modes. Neither of these two modes provide any diffusion. Information about various modes for disk encryption is available here.


Choosing a Random Number Generator algorithm to encrypt a message

takes a message and a key and encrypts or decrypts the message by using the key as the seed to a psuedo-random number generator that then generates the key to be used to encrypt/decrypt the message.

This sounds like a stream cipher. You should probably stop looking for a pseudorandom generator and instead look for a stream cipher. But “stream cipher” is both overspecific — why a stream cipher rather than another type of cipher? — and not enough — a stream cipher only encrypts, it doesn't guarantee authenticity. Without authenticity, many systems are vulnerable to oracle attacks which can allow an attacker to recover plaintext by submitting modifications of the ciphertext. So in fact you probably need an authenticated encryption (AEAD) algorithm. If in doubt, use crypto_box from NaCl or libsodium, but pretty much any AEAD interface in any reasonably modern cryptography library would be fine.

  I keep getting frustrated at how hard it is to find a good, safe random function no matter what language I try, so I decided to try to make one myself.

If you want to implement a random generator as a learning exercise, go ahead, it's a good learning exercise. But keep in mind that this is only a learning exercise. A well-established crypto library will almost surely do it better than you. Does your implementation properly wipe memory after use? Does your implementation properly report any failure of the entropy source? Might your implementation reveal confidential data via side channels such as timing and memory access patterns? Decried as it is, the authors of OpenSSL have thought about such things. If you haven't then they've done a better job than you.

For the sake of people who came here because the question's title is about PRNG choice: If you really need a pseudorandom number generator, it may help to know that another common name is “deterministic random bit generator” (DRBG). Any of the three algorithms from NIST SP 800-90A (Hash_DRBG, HMAC_DRBG, CTR_DRBG) is a good choice. But once again, note a PRNG has an interface which includes periodic reseeding; you can't easily use it directly to build a stream cipher. If what you want is to encrypt a message then what you want is not a PRNG. A PRNG is what you'd use to generate the key and the IV/nonce. And keep in mind that if you think you need to implement a PRNG, you're probably wrong. Use your operating system and your cryptographic library's random generator interface — as I explain above, they've done a better job than you're likely to.


Well, the question you should be asking "what are my security goals" and only then start addressing which cryptographical primitives (DH groups) meet them.

I rather suspect that your real security goals fall rather short of "unless someone can perform $O(2^{256})$ operations, they can't break it".

So, the real question is "can anyone who will attack my system be able to break the 2048-bit group"?  Note that the largest published effort in this area was roughly equivalent to breaking a 768 bit DH key (actually, that was a factorization effort; it is believed that using Number Field Sieve, the effort involved with solving a Discrete Log on a similarly sized modulus would be approximately the same).  Note that the US Government allows 2048-bit DH modulii to protect sensitive data; it would appear that that's good enough for them.

In addition, as for RFC 3526, the RFC does give estimates of the strength (see section 8; note that it gives two estimates; that's because no one is quite sure how NFS scales, and different knowledgeable people have estimated the exact strengths differently); as for how those were generated, well, those are all of the form $p = 2^n - 2^{n-64} - 1 + 2^{64} \cdot ( \lfloor 2^{n-130} \pi \rfloor + i )$, where $i$ is the smallest nonnegative integer such that both $p$ and $(p-1)/2$ are prime (and they also list the value of $i$).  As for how that was selected (and the reasoning behind it), see RFC 2412 appendix E.


Intuitively anything the honest minority can do the dishonest majority can do as well. So if the minority can force a correct outcome the majority can force an incorrect outcome.

Side note:The question is ill-defined, not mentioning a specific problem where these requirements are to be held, is this a computation? who has the input? In some situations we can deal with a dishonest majority such as limiting them to no more than failing the process.


What Are Secure Limits to Truncate the Authentication Tag (Mac) for Short Messages?

Cryptographic strength of an authentication tag strongly depends on the tag size and you shouldn't use a tag less than 64-bits for any application. 64-bits is really the minimum you should use.

Such a short tag is acceptable for online protocols, where the intent is just to authenticate a packet that has been received. Since 64-bits will not be collusion resistant, previous tags will be reused before ~2^30 messages. To mitigate this, you might need to rotate key frequently.

You can consider using SipHash function which is optimized for short inputs and has an output of 64-bits.

https://eprint.iacr.org/2012/351


Is it possible to generate a hash function that produces similar output to SHA-256?

I was thinking of creating a hash function that produces a similar/correlated output to SHA256, but with an in-built "backdoor" that allows for preimage attacks. Sort of creating a "breakable" version of SHA-256.

That is not possible for arbitrary sized messages and unkeyed hash functions.
Assume that you created a hash function such that $h(m) \approx SHA256(m)$. This similarity is not defined in the question, however, we can consider that it a permutation, or small edit distance, or correlated. Assume that the similarity can be found faster than pre-image attack of SHA256.
Now assume that $h()$ is a weak hash function that you can find pre-images easily. Now;

take $z = SHA256(m)$
use the similarity to find all possible candidates  ( from the premutation, small edit, correlation, or..) $$z_i \in \{ a\;|\; a \text{ similar to } z\}$$
find pre-images of each $z_i$; $$m_i = \operatorname{pre-image-h}(z_i)$$
check all $m_i$ on SHA256 to see that one of them is the pre-image $$ z \stackrel{?}{=} \operatorname{SHA256}(m_i). $$

That is the break of the pre-image of SHA256. Not expected!.


For what does "Rcon" stand for in Rijndael/AES?

Quoting from FIPS 197 (PDF), on page 11:

  Rcon[]   The round constant word array.

So, the answer is obviously "round constant".


If nG and 2nG are known how to find generator point G

You are asking two different questions in the title and the body. The answer to both questions is "You can't", but for different reasons.

Finding $n$:

You're asking how to find $n$, given $X=n\cdot G$ and $2\cdot X=2n\cdot G$, where $G$ is the generator of some group $\mathbb{G}$ and $n$ is sampled uniformly.
We first note, that being given $X$ and $2\cdot X$ is equivalent to just being given $X$. We could just compute $2\cdot X$ ourselves. Consequently, finding $n$ is equivalent to solving the discrete logarithm problem in $\mathbb{G}$. As the discrete logarithm problem is assumed to be hard in the used group, that's not going to happen.

Finding $G$:

You are asking how to find the generator $G$ of group $\mathbb{G}$, given $n\cdot G$ and $2n \cdot G$. This is impossible in general. Most groups have more than one generator, the group you propose to use is no exception to that. Given two generators $G,G'$ there by definition exists an $x$ such that $G = x\cdot G'$. Therefore, $n \cdot G = nx \cdot G'=n'\cdot G'$ and $2n \cdot G = 2nx \cdot G'=2n'\cdot G'$ and given no further information about $n$, it is impossible to decide which of the two generators was originally used.


Are there any applications of Quantum Computation to Cryptography? (besides Cryptanalysis)

As noted by kodlu, you are basically asking about the existence of the whole field of quantum cryptography (which is different from post-quantum cryptography).
All the field was arguably started by Stephen Wiesner’s invention of Conjugate Coding in 1969, but which was rejected remained unpublished until 1983. He proposed a theoretical way to use quantum mechanics to construct unforgeable banknotes. This stayed a pedagogical example until (roughly) the last decade, which saw a renewed interest in quantum money schemes.
The main and best-known application is quantum key distribution (QKD), for which many protocols and have been studied since Charles Bennett and Gilles Brassard’s seminal paper in 1984. These protocols need the capacity to exchange attenuated light pulses (typically single photons or coherent states) between the partners, a capacity which has been recently demonstrated over 400 km. There is currently research going on to build quantum relay, some experimental networks using “trusted relay” are operational, and a satellite has been sent by China last year to serve as a quantum communication relay. Beyond this line of work optimizing the “practicality” of these protocols, theoreticians work to improve the security proofs, going in some cases until device-independent security (the protocol is secure even if the physical device you need has been built by the adversary).
Bit commitment (BC) schemes have been proposed since 1984, in the same paper as QKD, but attacks were always found. In 1997, Dominique Mayers, and, independently, Hoi-Kwong Lo and H.F. Chau showed that unconditionally secure quantum bit commitment was impossible. Since secure  BC protocols have been found in specific scenarios:

Protocols secure against adversaries with limited noisy quantum memories
Non-composable secure protocols in a relativistic setting, where the fact that no information can propagate faster than light is a key part of the security proof.

Other relativistic quantum protocols have been studied for position verification since 2010, but security proofs remain hard to be found. We know that we will be limited to computational security, but the best generic attack is known is currently exponential, which leaves hope for security protocols.
Another line of research is blind quantum computing, the quantum analog of completely homomorphic encryption: it is possible to make a quantum computer (if you have one) perform a commutation on encrypted data in a completely blind way, at a small extra cost. The operator of the computer has no way to know anything about the computation (except its size), while the client, which only needs a small quantum apparatus (similar to the QKD one) gets the result of the said computation.
There are of course other avenues of research in quantum cryptography. If you want to have an idea of some of the subjects of this community, you can look on the web the program of the annual QCrypt conferences, where the slides of many talks are online.


Is it possible to combine true streaming with AEAD?

Yes there are such schemes.

However they aren't standardized by any means yet.
The schemes I'm talking about take part in CAESAR-competition.
If you wait ~1 week (hopefully) you'll see if any mode / cipher makes in in the second round.
This paper provides you with a good overview over the ciphers.
The four ciphers you need are:

ICEPOLE (Sponge based)
KETJE (Sponge based)
Keyak (Sponge based)
TriviA-ck (Streamcipher based)

This schemes can be used. But I'd strongly recommend against using them before CAESAR-competitions has further advanced (a few years?). Until then splitting a message stream into pieces with own tags + IVs seem to be the only method one can think of. To ease up IV management, one could use Message numbers as nonces.


Use of the info parameter in Hybrid Public Key Encryption

I dont understand the use of the info parameter, what does "to fold in identity information" mean?

It essentially is context information; that is, protection so that the ciphertext can't be reused in a different context.
Here is a simple example; suppose I encrypt a message to you, and fgrieu intercepts it.  Now, what fgrieu could do is forward that message to you and claim it was from him (he can't read it, however because I wrote it, he knows it must be good :-)
If that's all the system did, he'd succeed; there is no way that the message wasn't from fgrieu.
However, if we were to routinely put the sender's name in the info field ("poncho" in this case), well, fgrieu's attack wouldn't work - the only way you can decrypt the email is to include "poncho" in the info field during decryption, and you know that the specific email came from me (or some other poncho).


No, it is not always bijective.

A perfect hash guarantees that no two inputs (from the set of valid inputs) collides, so it is clearly a 1 to 1 mapping.  However, in the case where the output range contains more possible values than there were valid inputs, there will be outputs which do not map back to inputs.  hence it is not bijective.

If you restrain the problem dramatically, and define the range of the outputs to be "the set of outputs attained from valid inputs," then you could argue it is bijective because you have constrained the output sufficiently to make such a claim.  However, it would be up to you to explain why this very particular output range is a valid one for whatever topic is being discussed at that time.


Is a larger block size less secure against a brute-force known cipertext attack?

The answer depends on the size of the plaintext you are attacking and the number of ciphertext blocks you have.

Assume that you have a 64-bit block-sized cipher named C64 and 128-bit block cipher named C128.

If you know that the $m$ is smaller than 64-bit than you will have only one ciphertext for C64 and C128. There is a need for padding at the end of the plaintext. This padding can be removed and more importantly it can also be used to detect the correct plaintext like in the DES challanges. There is no difference here.

If the $m$ between 64 and 128 bit than the question, do you have the second block for C64? If not then C128 is better here. Otherwise, the are the same.

Similar comments can be made to other cases. But, in short, if you have the all necessary ciphertexts they are the same. If you have all, the only difference is that you need to run almost C64 double times of C128. But this is not counting the actual running times of the ciphers. C128 is expected to be slower than C64.

Not that: a 64-bit block size is not secure; see sweet32. I've used to demonstrate and historical reasons. We don't have a common 256-bit clock cipher also. Also, brute force is not applicable to block ciphers who have a key size larger than 128. We can see this from the collective power of the bitcoin miners that can reach $2^{94}$ double SHA-256 hashes. Some of the nodes are ASIC that boost the attack. One still needs $2^{34}$ year to break with the enormous collective power.


SHA-256 Partial Collision of initial 36 bits and more

Actually, this sort of programming question is more suited for stackexchange.

However, to answer your question, there are two obvious approaches to speed up a collision search:

Use a Hash table; that is, instead of keeping everything on one big list, divide them onto (say) 1024 different lists (in such a way that you know that items on two different lists aren't "matches").  And, given that you know that the SHA256 is already wonderfully distributed, you can (for example) select the hash table entry that a specific hash is placed on by using the first 10 bits of the SHA256 hash value; that way, you'll never have to explicitly compare two hashes that differ in the first 10 bits.  That reduces the number of comparisons you'll need to do by 99.9%.  Of course, you'll adjust the size of the hash table (that is, how many entries it contains) according to the resources you have.
Use a sort algorithm; that is, use a good algorithm to sort the hashes into ascending order; that way, any 'close' matches will be adjacent, and so that's the only comparisons you'll need to make.  A good sorting algorithm on $N$ elements can be done in $O(N \log N)$ time, hence this is much faster than individually comparing each element.

I don't know which would be better in your situation; however it ought to give you something to think about.


I am not quite sure why you are looking for the kind you have mentioned in your question.

But good old Shamir's polynomial secret sharing over finite fields, look here, provides information theoretic secrecy, i.e., even a quantum computer will not help you to break the secrecy.


How sensitive to change are elliptic curve formulae In layman's terms?

An elliptic curve equation is very sensitive to any change of its parameters.

That small change result in a complete different curve.
Its security could be good or bad, but you have to check it explicitly and cannot make predictions beforehand.

Specifically, your resulting curve will have a composite order whose largest factor is $833860344743147476600479140946265460420135480673538361531$ which implies your curve's security won't exceed $2^{94.5}$.
I said "won't exceed" because I haven't checked all the other security properties of the curve (twist security, transfers, etc), which could result in a security downgrade.


How can I turn this cipher into a perfect cipher by altering only its encryption algorithm?

Two ways to go about it:

Enlarge the key space so that every possible ciphertext is equally likely.
Change the operation from XOR to one that stays in the set of the three values you have.

Either would work, but since you asked for hints I will leave the specifics for you.


Confusing notation in the definition of differential privacy

I had the same problem when I was understanding this because it's not so intuitive. I will answer here in case future people had the same trouble.

Agree with you $\Delta B$ assigns a probability to every element of the set $B$.

$A$ It can be anything I assume from continuos to discrete objects.

$(M(a))_b$ is the probability that the mechanism outputs $b$ when the input is $a$.

The probability space is over the coin flips of the algorithm $\mathcal{M}$. This means you will not know before you apply the mechanism which will be the result. For example, if you toss a coin, you will know what will be the answer? No. What this space is inducing the most important, the randomness. You will see on some papers " The probability space is over the randomness of the algorithm $\mathcal{M}$", which makes more sense.

I made an example to stabilize these definitions:

Let's consider an mechanism $\mathcal{M}$ that will find a $a$ in a list $A=\{(x_0,x_1,x_2,x_3,...,x_n): x_i=\{a,b\},n\geq 2\}$ where the half are a's and the other half are b's. With output $B=1$ if it finds an a and $B=0$ if it doesnt . This is $B=\{0,1\}$. Then the algorithm/mechanism $\mathcal{M}(x_i)=b$ with probability $(M(x_i))_b)$ which is defined by $\{(p_1,p_2)\in \mathbf{R}^2: p_1+p_2 = 1;p_1,p_2 \geq 0\}$ (Probability Simplex) . It means give a value of $p_1$ that $B=1$ happens and $p_2$ that $B=0$ happens . Who define this probabilities ?. The space of randomness, which we will never know for sure will be the result of the mecanism, because in that case wil be deterministic.


Break large exponent calculation into smaller calculations?

One method uses the factorisation the exponent: If $a=bc$ then $x^a \equiv x^{bc}\equiv (x^b)^c \mod m,$
i.e. first compute $y=x^b\mod  m$ and then $y^c \mod m$.

This method will work,  if the largest factor of the exponent has at most 32 bytes.

Otherwise you can always use the square-and-multiply exponentitation
method (see https://en.wikipedia.org/wiki/Modular_exponentiation or https://en.wikipedia.org/wiki/Modular_exponentiation or  https://en.wikipedia.org/wiki/Exponentiation_by_squaring)
looping over the single bits of the exponent.


So please help to decrypt this message

This would appear to be an RSA encrypted message, using a 4096 bit RSA key.  Assuming that the key was generated properly, then it is infeasible to recover the plaintext using only the message and the public key; sorry...


Is there a standard way to use a nonce with HMAC?

Under the assumption that $(K,\text{Msg})\to H_K(\text{Msg})$ is a secure MAC (be it HMAC or any other MAC), and $\text{Nonce}$ does not repeat and is of fixed size, both $H_K(\text{Msg}||\text{Nonce})$ and $H_K(\text{Nonce}||\text{Msg})$ are demonstrably secure, in the sense that an adversary not knowing $K$ can't distinguish either from random, even for iteratively chosen $\text{Nonce}$ and $\text{Msg}$.

When $(K,\text{Msg})\to H_K(\text{Msg})$ is HMAC, and we do no trust the underlying hash, and the weakness of this hash is bad enough that HMAC is not secure, it is hard to tell which of $\text{HMAC}_K(\text{Msg}||\text{Nonce})$ or $\text{HMAC}_K(\text{Nonce}||\text{Msg})$ is likely to be least broken. I wouldn't worry about that, because HMAC is secure with less-than-collision-resistant-hashes both in theory and practice (MD5's collision-resistance has been torn to pieces, but HMAC-MD5 so far stands valiantly). Any remaining security may depend more on what constraints the adversary really has on $\text{Msg}$, and what really counts as a success, than on anything else.


No, or at least, if you can, you have an Extremely Significant result; you've just shown that Paillier is a Fully Homomorphic system, and so it could perform any operation on encrypted data (and in a way that's significantly more efficient than any other known FHE system).

Here's why: The $|a - b|$ operation is effectively an $XOR$; if the ciphertexts $a, b$ are known to be either encrypted $0$ or $1$ values, then the result will be a 1 if they differ, and 0 if they are the same.

In addition with a bit more work, we can compute an $AND$.  To do this, we could first compute $a + b - |a - b|$.  This value will be an encrypted 2 if $a, b$ are both 1, and 0 if either is a 0.  Then, multiplying this value by the constant $(n+1)/2$ (which can be done in $O(\log n)$ homomorphic additions) will give us an encrypted 1 if both $a, b$ are 1, 0 otherwise (or, on other words, an $AND$ operation).

The combination of the $AND$ and $XOR$ operations are complete; that is, any function (computable in bounded time) can be implemented by a sufficient number of them.

We don't believe that Paillier is an FHE system, hence either what you're asking for is infeasible, or we have a really exciting result on our hands.


What do I use as the encryption key and initialization vector in AES cfb128

You can use your HardwareID as basis for the encryption key. If the ID provides enough entropy it'll work. However, if anyone can somehow obtain the ID (which might be quite easy to do) one can decrypt the file.

For CFB-Mode the IV must indeed be unpredictable (but need not be secret), so random is just fine, but DO NOT REUSE AN IV.

Encryption large amounts of data with the same key and different IVs is just fine and no problem at all.

However, I want to propose some improvements for the security level.

Don't use CFB-Mode but EAX/CCM/GCM-Mode, as they are authenticated and hence you've authentication "for free" without any further worries.
As replacement for the Hardware-ID based Key I'd suggest either storing the key (plain - not recommended) on the USB-Stick, or only use a password (+ scrypt) or store the key encrypted (AES-GCM+scrypt) on a stick.
You might want to consider generating a key for each file you encrypt and storing this key (+IV) as a "header" for the encrypted file. The header would be decrypted using the secret key (from USB / from password / from USB+password)


Preferred SHA-2 hash algorithm for MGF1 in RSA

Since the input sizes are fixed, length-extension attacks are not relevant, so any of the SHA-2 functions reasonably implements the random oracle model assumed by OAEP or PSS via MGF1—even the default of SHA-1 works with MGF1.

Obviously it will cost slightly more to use SHA-224 or SHA-384 than to use SHA-256 or SHA-512 because SHA-224 and SHA-384 are effectively truncations of SHA-256 and SHA-512: to get the same amount of output as (say) twelve SHA-384 invocations each costing a SHA-512 computation, you could pay for a mere nine SHA-512 computations instead.  So the truncated options don't provide any benefit.  And, of course, SHA-512 than SHA-256 is generally faster on CPUs with 64-bit adders.

All that said, it is hard to imagine that this could substantially affect security or performance since you're about to do a 2048-bit modular exponentiation anyway, which will be the bulk of the cost—but, of course, you're in a better position to do that measurement in your application!  (Make sure to choose $e = 3$ to minimize time spent in exponentiation.)


How to encrypt letters less than block n using Hill Cipher

Since it's a linear cipher, you should be wary about a guessable padding, otherwise if your last block is only one char long, you will reveal almost your whole matrix on this last block. If you're too afraid of mangling the last word, use something like 'Z'+(random chars). But I really would not use any predictable padding with such a cipher.


Security proof of partially blind signature (schnorr signature based)

It follows by the probing strategy/heavy-row lemma, which traces back to [Oka,FFS]. Read §6 in this paper for a nicer explanation.

References:
[Oka]: Okamoto. Provably Secure and Practical Identification Schemes and Corresponding Signature Schemes. CRYPTO 1992.
[FFS]: Feige, Fiat and Shamir. Zero-knowledge proofs of identity. JoC 1988.


To the best of our knowledge, SHA256 does not leak any additional information from related hashes.

On the other hand, the state of "our knowledge" might not be that comprehensive; this security property of SHA256 cannot be derived from the base security assumptions of a hash function (preimage resistance, second preimage resistance and collision resistance), and as far as I know, no one has studied it.  While it may be (and likely is) secure, no one has really studied it, and so there there might be a semiobvious leakage that no one happened to find yet.

Now, there is an obvious variation on this which has been studied: HMAC.  HMAC is a Message Authentication Code, that is, it has a security assumption that if you give someone (who doesn't know the key) a large number of MAC outputs based on known texts, they still cannot derive the key, or any information about MAC outputs for texts they haven't seen.  That is precisely the security assumption that you are looking for; and so HMAC has been analyzed against the exact problem you're looking for.  HMAC uses a hash function (for example, SHA256) as an underlying primitive, and it does have a small additional cost over the underlying hash; if you can do some precomputation, this additional cost is just one more hash compression evaluation.

As for how you would use HMAC; well, HMAC has two inputs, a "key" and a "message".  You would make your "root" the key and the "salt" the message, and use the output of the MAC as your derived hash.


The security proof of RSASSA-PSS assumes that the private key is used only for RSASSA-PSS purposes, that hypothesis is violated, thus the security proof does not hold (but as long as RSASSA-PKCS1v1_5 remains usable, you do not have a security proof anyway).

Similarly, the wide consensus that RSASSA-PKCS1v1_5 is secure in practice was formulated without taking into account the use of the same key for another purpose, so you are left without a wide consensus.

That said, some deployed systems use the same RSA key for different purposes, and I know no example of ensuing disaster as long as the padding schemes are very different, and each is secure (an example is the European Digital Tachograph, which uses the same RSA key for RSASSA-PKCS1v1_5 signature, and a custom authentication and key agreement protocol using ISO/IEC 9796-2 (scheme 1) signature padding; it was rubber-stamped to ITSEC level E3, and no attack emerged). The situation is similar to using the same key for HMAC-MD5 and HMAC-SHA1: that's theoretically undesirable, but the only clear consequence is that the weaker of the two systems caps the security.

I find improbable that a feasible cryptographic attack exists based only on the option to tell A and B to use RSASSA-PKCS1v1_5 or RSASSA-PSS, because these padding schemes are different enough. What I find much more probable is that an exploitable bug creeps in the specification or implementation, and the increased complexity due to the option increases that risk.


SRP with random, but constant private-value b

If you use a $g^b$ value between sessions, you allow an attacker to test multiple passwords for the second session; this invalidates the security goal for SRP.

Here is how the attack looks like:

For the first session, the attacker logs in using a password he does know.  The server sends the value $B = kv + g^b$; the attacker knows $k$ (that's derived from common data), he knows $v$ (that's derived from the password he knows), and so can recover $g^b$

For the second session, the attacker listens into a login that uses a password he does not know.  Again, the server sends the value $B = k'v' + g^b$ (where $k', v'$ are different values for this session), as he now knows $g^b$ (and can derive $k'$, he can recover $v'$; he can then go through his dictionary, and test the various passwords against $v'$.


Explanation of protocol secure under random oracle but insecure with any hash fuction

I believe the "simple" examples are of the form

adversary can send honest party arbitrarily-long messages

messages sent by honest parties in that context all start with 0

when an honest party receives a message in that context that

starts with 1, if the rest of that message encodes a circuit then:

The honest party evaluates that circuit and the oracle at a secret value.

If the outputs are equal then the honest party does something obviously insecure.

.

This paper shows that even Fiat-Shamir can fail.


No, it doesn't have to expose information. Of course, any data in the last part of the file can be used to deduct information about the encrypted plaintext. Furthermore, it seems you want to perform in-place encryption. That's fine, but ciphers generally require an IV to make sure that the ciphertext is random even on identical plaintext. Using an IV generally means expanding the ciphertext size compared to the plaintext size.

There is one mode of operation that is perfect for encryption like this: CTR or counter mode (it may have even different names in other libraries). Here a counter is encrypted, and the resulting block is part of the key stream. You can simply XOR that key stream with the plaintext at the same offset to create the ciphertext. There is one big "but" (yo' mamma): CTR mode is completely unsafe if the counter is ever repeated, and the initial counter value is the IV. So you do need to store the IV somewhere where it can be related to the ciphertext. Possibilities are storage at the beginning or end of the file or in the meta-data of the (modern) file system.

It is also possible to calculate the IV, e.g. by performing a SHA-256 of the full path of the file name, and then taking the leftmost 128 bits. But note that any movement of the file will lead to corrupted plaintext (and possibly no way to decrypt if the path cannot be reconstructed).

If copy protection is used then leaving part of the file encrypted may indeed destroy the copy protection, if the bytes are taken into account e.g. for signature generation, using a hash over the encrypted data. However, without more info about copy protection (which comes in many forms) then we cannot tell for sure. Of course if you can fully restore the file before copyright protection takes place I presume you are secure.


Is there a way to confirm that a homomorphic division (multiplication with inverse) using ElGamal produced the correct result?

I've included some discussion in general, but "El Gamal" here is a red herring. Your confusion is with the difference between "division" in $\mathbb{R}$, and "division" in $\mathbb{F}_p$. I discuss this more in detail at the end.

El Gamal's ciphertexts are of the form:
$$\mathsf{Enc}_{g, h}(m) = (g^y, mh^y)$$
Note that $h = g^x$, where $x$ is the secret key.
This admits a (multiplicative) homomorphism, as you mention:
$$\mathsf{Enc}_{g, h}(m_1)\ast \mathsf{Enc}_{g, h}(m_2) = (g^{y_1+y_2}, m_1m_2 h^{y_1+y_2})$$
I believe your confusion stems from confusion over what $m_1m_2h^{y_1+y_2}$ means.
Like many cryptosystems, El Gamal is defined over what is known as a "finite field" (in particular $\mathbb{Z}/p\mathbb{Z}\cong\mathbb{F}_p$). This is a number system that allows you to add, subtract, multiply, and divide (just like with $\mathbb{R}$), but the operations are somehwat different than you are used to. Fix $p = 5$ (although any prime number works). Then addition is defined "mod 5", so:
$$3 + 3\bmod 5 \equiv 6\bmod 5\equiv 1\bmod 5$$
So in this number system, $3 + 3 = 1$.
Multiplication is similarly defined "mod 5".
So:
$$3 \times 3\bmod 5 \equiv 9\bmod 5 \equiv 4\bmod 5$$
So $3\times 3 = 4$ in this number system.
What does "division" mean in this number system?
Well, one can show that for any (non-zero) $x\in\mathbb{Z}/p\mathbb{Z}$, there is a unique $y$ such that $xy \equiv 1\bmod p$.
Over $\mathbb{R}$ this is true as well (instead with the equation $xy = 1$) --- if $x = 2$, then $y = 1/2$.
But in $\mathbb{Z}/5\mathbb{Z}$, if we have that $x = 2$, then $y = 3$ means that $xy\bmod 5\equiv 6\bmod 5\equiv 1\bmod 5$.
So, in $\mathbb{Z}/5\mathbb{Z}$, we have that $2^{-1} = 1/2\equiv 3\bmod p$.
This is now when we get to your point --- if we have $x,y\in\mathbb{Z}/p\mathbb{Z}$, then $xy/y\equiv xyy^{-1}\equiv x\bmod p$, so "when $y$ divides $xy$, division is like you would expect over $\mathbb{R}$".
But the situation can be more complicated in general.


I think this is formalized as non mallability of hash functions. However, you do not find it as a requirement e.g. in the SHA-3 competition and I think that practical hash functions are not analyzed in this direction. For non-mallability you might want to take a look at
http://eprint.iacr.org/2009/065


DLP based crypto systems with multiple independent generators

It's not impractical.  Choosing a random generator $g$ is easy and can be done efficiently.  It's efficient enough that it wouldn't be a problem to generate a random generator when you generate your keypair.  I think your premise (your assumption that this is a problem or that it should be discomforting) is not valid.  Consequently, I don't see the relevance of the question.
Let me elaborate a bit.  There are two kinds of values that might be floating around:

Domain parameters are parameters that are shared by many users.  For instance, in a discrete-log based cryptosystem, if the modulus $p$ is shared by everyone, then it is a domain parameter.

Individual parameters (to coin a term) are values that are used by a single party, and are generated by the same party who uses/relies upon them.  For instance, a user's private key is an individual parameter, since it is generated by that user and only used by that user.

These two different kinds of values have different security and verifiability requirements:

Domain parameters are critical and particularly sensitive, since they're generated by one person (e.g., a CA or trusted authority) but used and relied upon by everyone else.  If the CA secretly and dishonestly constructs a domain parameter in a way that introduces a backdoor (rather than following the algorithm they were supposed to use), everyone loses.  That's very bad.  The standard mitigation is to provide everyone a way to verify that the CA generated the domain parameter honestly.
In summary, domain parameters must be verifiable.

Individual parameters don't have this problem.  There's no reason for Alice to secretly embed a backdoor in her private key, since the only person's security who is harmed is Alice's (at worst others may obtain the ability to eavesdrop on messages encrypted to Alice, but a malicious Alice could always have achieved a similar effect simply by publishing all the messages she receives, and there's no way for others to verify Alice hasn't done that).  There's no way for Bob to verify that Alice has kept the messages he sends her secret.  Therefore, there's no reason why Bob would need to verify that Alice generated her private key honestly.  For instance, we don't require that RSA provide a way for Bob to verify that Alice generated her RSA secret key using the algorithm she was supposed to use; if she does something different, we say it is her tough luck.  There's no point in trying to prohibit what you can't prevent.
In summary, individual parameters do not need to be verifiable, and there's no clear value to verifiability.

This means that your question is based upon a faulty premise.  Your premise is that there's something wrong with a cryptosystem if the public key (an individual parameter) is not verifiable.  This premise is not accurate; actually, there's nothing wrong with a cryptosystem where the public and private keys are not verifiable by third parties.  We use cryptosystems like that all the time.  Therefore, the best answer to the question is to un-ask the question.
I am making numerous assumptions about what you are asking.  I confess I might not have understood what you really wanted to know, and what problem you are trying to solve; if so, my apologies.


Input Hash Size of ECDSA Signature over Curve secp521r1

The hash output length does not need to be larger than 512 bits; the ECDSA specification can handle any length. The curve secp521r1 is usually considered to provide 256 bits of security (even though it provides a bit more), see Table 2 of NIST SP 800-57 for example. Therefore, a 512-bit hash, i.e. SHA-512, should be fine ("The security strength of the hash function used shall meet or exceed the security
strength associated with the bit length of n", NIST FIPS 186-4)

Regarding cSHAKE (you probably meant SHAKE; cSHAKE is its customizable variant that is used to define KMAC and TupleHash), you could use any output equal to or larger than 512 bits. The NIST FIPS 186-5 draft mandates SHAKE256 with 512-bit output.


Can encrypting well known files hurt the security of the key?

Fgrieu answered my question in a comment to show that my key will be protected even despite the fact that I encrypted well known files.

  As a general rule, any modern encryption program should aim at security under chosen plaintext attack, and that's a goal of GPG, thus encrypting well known files should not hurt the security of your private key or otherwise compromise the confidentiality of your encrypted files; other causes with a much higher potential for that abound. [edited]


Doesn't this reduce the search space for the primes P and Q by half?

I can't see how it does.  After all the attacker can see $N$, and so can determine what bits are set.  Allowing, say, a 2047 bit composite (rather than a 2048 bit) doesn't make his job any harder; he can see whether the composite in front of him is either 2047 or 2048 bits long.

What you might mean is that we generally pick the two prime factors to be both precisely $L/2$ bits long; you could try to say that reduces the attackers search space (because, for example, he doesn't have to search for a factor thats, for example, $L/2 - 10$ bits.  However, that line of reasoning doesn't appear to work out; there are far too many primes of length $L/2$ (for any $L$ that we're interested in) for anyone to search through; and the practical factoring algorithms against numbers this size (NFS, ECM) can't take advantage of knowledge of the length of the factors.


Using ChaCha20 on very short messages with high packet loss

If I remember correctly, ChaCha doesn't need an unpredictable IV, so a simple counter will do. (Combined with sender id if you have multiple senders using the same key.) If you had a totally lossless link, you wouldn't need to send the counter value at all.

But as some packets can be lost, you need to send at least part of the counter. The least significant 8 bits should do fine against random packet loss, just make sure to increment the next bits when overflowing the sent part, so you don't end up repeating the same 256 IV values. Even if each packet had an independent 90 % chance of being lost, the odds of losing 250 packets in a row would be less than $10^{-11}$.

Non-independent packet loss would be another thing, but with one message per minute, you'd need to lose four hours worth of packets in a row to lose synchronisation. Might happen if there's a power-out at the receiver during the night but the transmitter keeps sending.

Speaking of power-outs, your transmitters would need to have some persistent storage for the counter so that it doesn't reset in case the device loses power. A real-time clock as a counter would also do, as @otus commented.

Also note that you don't seem to have any authentication for the messages, so you're only protected against passive attackers.


You need to choose e such that it is co-prime relative to PHY(n). Since you do not want to get involved in factorization of PHY(n), the best way is to choose e randomly, and better let it be a non even prime. Common values are 2^16+1, 3, etc. Most of the primes you choose will have GCD(e,PHY(n))=1.


Why develop Edward curve formulas that deviate from unification?

Edwards curves can be implemented using a unified formula for addition and doubling; i.e., one can implement addition such that
$$\mathrm{dbl}(P)=\mathrm{add}(P,P).$$
Performance wise it is however more efficient to consider both functions separately, since the doubling can be implemented more efficiently than the addition.

Depending on the representation and the formulas, the unification property will be preserved or not. For instance, in "Twisted Edwards curves" by Berstein et al., there is a formula for $\mathrm{add}(P,Q)$ and a faster one for $\mathrm{dbl}(P)$, but the above property still holds. In "Twisted Edwards curves revisited" by Hisil et al., there are also two separate formulas, but the above property doesn't hold anymore.

I think the unification property looks great in a paper as it makes the description cleaner; however one does not necessarily need it in practice. Some examples:

Example 1: "Scalar multiplication (based on Exponentation by squaring)". When the factor is lower than the order of the group, you know that the next doubling is always higher than the accumulated value, so that an addition will always take place between two different points.
Example 2: "Addition of random points". The order of the group is in general so large, that the probabilty that two randomly chosen points are equal is negligible.

So in many situations the absence of the unification property does not seem to be an issue. It will of course depend on what precisely you are doing with the curve.


Optimal memory-hard KDF parameters when faced with small, slow memory

It depends. There is no answer that is the only right one.

Increasing the memory for Argon2 increases also time needed to process it. Test your system, what is the correlation. May be increasing memory usage 2x will reduce the performance not 2x but 6x or 10x.
It depends on design/architecture of your system. Namely, do you need to use Argon2 in every single request or only in some requests, let say in 1% of requests? In the 1st case high usage of Argon2 will cause high power consumption. Then, considering you have a lowe-power system, the solution should be preferred that uses CPU less, i.e. less iterations and slow memory. In the 2nd case both approaches are possible. Launch the desired number of parallel requests and check with which parameters you get the desired response times - when you use slow memory and less iterations or when you use fast memory and more iterations.
How important is that your system is low-power? If it is very important to consume as little power as possible, and if you have to use Argon2 in every or in many requests, then the approach with less iterations and more slow memory can be preferred. Again, first test how much more power (the total power of your system, not only CPU) is used if you use more memory.

I would assume that A) little power consumption is very important, B) that increasing used memory increases used power non-proportionally less, C) there are only a few simultaneous requests and parallel processing is not important. Then I would prefer to use more memory for Argon2, means slow memory, and less iterations.

Regarding combination of two: I would suggest not to do that. Why? Suppose you decide to spend 50% of time many iterations with the fast memory and 50% for less iterations with slow memory. If an attacker has fast memory, then for brute forcing he run many processes in parallel for your part with many iterations. Since the 2nd part is very quick, the attacker will not need as many processes for the 2nd part as for the 1st part. That's why the 2nd part (with more memory) will be for an attacker of no much importance and effectively brute forcing and protection will depends on your 1st part. It means that the 2nd part of your 2-step scheme will be more or less waste of resources. In other combination, it can be that brute forcing the 1st part is for attacker much cheaper than the 2nd part. Means, in such case the 1st step you would do would be wasting of resources and protection will depend on the 2nd step only. Where as if you decide for one step only, the attacker will have to repeat exactly this combination always, and no of your resource will be wasted.

Resources for brute forcing: Consider also the resources needed to brute force your passwords. Suppose you use password of 15 chars which means ~6bit x 15 =~90 bit =~10^30 passwords to try. To keep it simple, suppose 1 iteration of Argon2 with 1K memory costs 1FLOP (actually much more). The most powerful supercomputer Sunway TaihuLight can give about 10^17 FLOPS. To brute force your password it would needed 10^13 seconds =~ 10^5 years = 100 000 years. If you use all super computers in the world, this would be not more than 100 of its size. Means, with all super computers in the world would need 1000 years to brute force such password.

What can you do for protection? Make sure passwords are long enough and complex enough, better - that they are more or less random. If users use words from a normal dictionary with small modifications or use random but short passwords, the entropy will be small and one doesn't much resources to brute force it. If you enforce proper password policy, even a small number of iterations and a small amount of memory can be quite sufficient to make your system very secure.


Why does FIPS 186-4 require specific sizes for keys?

I don't remember whether there is an official NIST publication on the topic, but there are definitely advantages to having a small set of possible key sizes. Contrasting RSA and DSA is instructive in this respect. A 170-bit $q$ wouldn't be less secure than a 160-bit $q$ if implemented correctly, but offering the choice is less secure.

Security strength

The lack of guidance on choosing an RSA key size has led to some users picking insecurely low sizes, or occasionally, conversely, needlessly high (and thus slow) sizes. The original DSA standard (FIPS 186-1) allowed a range of $p$ sizes from 512 to 1024; the current version imposes the higher end of the range and does not allow going further. NIST now publishes a list of correspondence between key size and security strength in SP 800-57.

Interoperability

When an algorithm may be instantiated with different key sizes, interoperability requires that all cooperating implementations support compatible key sizes. For example, with a signature algorithm, all verifies must support key sizes that are generated by any signer. This means additional implementation complexity (never a good thing for security, and a pain for implementers anyway) imposed on everyone. This also means that communication protocols may need an extra step to negociate key sizes, which is both extra overhead and a risk of security downgrade if one party is malicious (or due to a man-in-the-middle, but that would mean the protocol is flawed).

Implementation flaws

Allowing variable key sizes means additional implementation complexity, and more complexity means more risk of bugs. FIPS 186-1 already restricted $p$ sizes to a multiple of 32, the word size on many machines, to avoid bugs that were not all that uncommon with RSA implementations in computing the size of intermediate values, the memory requirements, etc. For example, there have been (and probably still are) RSA implementations that don't produce the expected modulus size when that expected size is odd, or that calculate the byte size from the word size by dividing by 4 and rounding down instead of up; DSA is not prone to these particular bugs.

Testing

Given the risk of bugs, every size must be tested, or at least a sufficient sample. Testing every RSA size, for example, is impractical. Testing schemes generally require testing an algorithm at each size they will be used for. This is again extra work which is not required if there is a single standard size.


Does a public key absolutely need to be used to initiate an encrypted session?

First recommendation: Don't invent your own protocol, but use an existing one. Use SSL/TLS, in the newest version possible if you don't have to provide downwards compatibility to existing clients. This will take care of most problems here, you simply put in a pair of plaintext data streams, and get a pair of encrypted streams. There are TLS implementations for most programming languages available, I'm quite sure that .NET has one, too.
TLS is quite flexible about the key exchange, authentication and encryption algorithms (bundled together as "cipher suite"). You'll have a public key for the server (usually with a certificate, whose subscribing key can already be embedded in the client application), and then use (for example) Diffie-Hellman key exchange with public-key authentication. There are also password-based key exchange algorithms, then you even don't need a public key (but client and server need some other way to first get the common password).
To your questions:

SSL/TLS works fine with a constant public key, not a different one per-client. Of course, if the private key gets leaked, all future connections are broken. If you did use the simple "encrypt session key by public key" model (RSA key exchange), also all past connections can be decrypted. Diffie-Hellman provides forward-secrecy, as the key is generated from random input of both sides, and the public key is only used for authentication.
If you create a new key pair per-client, you'll need some way of the client to tell its name (or key ID or similar) before the actual connection.

I have no data about how long key generation nowadays takes, sorry. You also have to take care of having enough entropy for your keys. But as said before, there is no need to generate new keys regularly.

Instead of doing this yourself, have a look on the secure remote password protocol for generating a shared session key authenticated by a password. This is also available (standardized) as a key exchange method for TLS, though I'm not sure if it is supported by .NET's implementation.

You can use whatever cipher you want, but as said by others, AES is actually more likely to be secure than other ciphers. Also, modern processors have actually AES-instructions build in, which could make the performance difference quite small or even negative (i.e. AES-128 could be faster than CAST-128), if you use a library which actually can make use of these.


Can you find the salt if you have the original password in plaintext and the hashed version?

No. It's impossible to find the salt if you don't already have it unless something is seriously broken or unusual.

You may already have the salt because it's common practice to store the hash together with the salt. Many password hashing interfaces even output a hash string which contains the “real” hash, the salt, and additional metadata identifying the algorithm and the iteration count. For example, the output of the Unix crypt() function looks like $5$salt$hash where 5 identifies the hash algorithm, salt is the salt encoded in Base64 and hash is the output of the underlying function also in Base64. The PHC string format, promoted by the Password Hashing Competition, has a very similar format.

But if all you have is the hash itself, then for anything remotely resembling a proper password hash and even for most things that aren't, the only way to find the salt is by trying every possibly salt until you find the right one, just like the only way to find the password is by trying every possible password until you find the right one. Even something broken like MD5(password + salt) (broken as a password hash because it's far too fast) makes it impossible to find the salt without guessing it. That's preimage resistance, and even hashes like MD4 and MD5 that are badly broken with respect to collision resistance still have preimage resistance.

With the password, guessing is a real risk: most users choose passwords that are at best a slightly modified dictionary word, which can be guessed in seconds of computer time with a broken hash like MD5 and may still be barely manageable but slow with a properly slow hash. But the salt is not chosen by a human. It's usually generated randomly so brute force among all possibilities is the only way. And it's usually long enough that brute force is not feasible. You'll only realistically be able to find the salt if either it wasn't generated randomly (or with a non-cryptographic random generator, or with a badly seeded generator), or if it's too short for comfort.


Besides key and ciphertext sizes what are other advantages of elliptic curve versions of various protocols?

Computations on elliptic curves are more efficient. Roughly speaking, when the base field has size $n$ (for DH/ElGamal/DSA, the size in bits of the modulus $p$; for elliptic curves, the size of the field for point coordinates) and a "security level" $t$ (e.g. $t = 80$ for "80-bit security" as can be expected when using a 160-bit subgroup and a 160-bit hash function), the computational cost of a private key operation (decryption, signature generation) is roughly $O(n^2t)$, both for the modular and the elliptic curve variants. The big-O notation hides a constant, which is about $10$: for the same $n$ and $t$, the elliptic curve variant will be 10 times slower than the older modular algorithm.

However, elliptic curves tolerate much lower $n$ for a given security level. Basically, for $t = 112$, we need $n = 2048$ for the modular algorithms, but $n = 224$ is sufficient for elliptic curves (these comparisons are always a bit subjective, see this site for details). Report the values in the formulas: even with the factor 10, the elliptic curve variant will be more than 8 times faster than the modular algorithm of comparable strength.

Another point is binary fields. When the implementation platform is a dedicated ASIC/FPGA, or even when the platform is a small CPU which does not offer a very optimized multiplication opcode (e.g. the ARM Cortex M0), then curves on binary fields give a huge implementation boost, especially Koblitz curves. It also has benefits for memory-constrained systems, see for instance this presentation. The "modular" algorithms cannot really benefit from binary field computations (it can be defined, but discrete logarithm on binary fields is easier than modulo a random prime, so a binary field variant of modular DH or ElGamal would require a $n$ twice larger, hence a four-fold slowdown).


Security of pairing-based cryptography over binary fields regarding new attacks

Antoine Joux announced the computation of discrete logarithm over $\mathbb{F}_{2^{257 \times 24}}$, which is now pretty close to what was being used in pairing-based cryptography.

According to Joux, "a direct consequence of this record is that supersingular curves (of
genus 1 or 2) defined over GF(2^257) cannot be used securely for
pairing-based cryptography."

It seems now that pairing-based cryptography over binary fields is dead.


How are the primes used to generate RSA keys?

Textbooks say the one-way function is merely two primes...

Yes, that's the key part.

It turns out that if you have a number that's a product of two large primes, deducing which primes factor that number is quite difficult.

So, what we understand from this is that if you have $n = pq$, and you know $p$ and $q$, you can generate $n$, but if you have only $n$, it is hard to generate $p$ and $q$.

These are not keys by and of themselves - they're parts of a process used to find a key. Specifically, a number $e$ is chosen and then you need to find $de = 1 \mod (p-1)(q-1)$. I've covered the mathematics in detail here, but the essential part to understand is that it is difficult to compute $p-1$ or $q-1$ without $p$ and $q$, which you don't have if you have only $n$. Thus, if you know $e$, you have no way to get to $d$ (it's important to understand it isn't theoretically impossible. It's just very, very hard practically).

$e$ and $d$ form the key - $e$ is chosen and $d$ is usually computed, although not always by the mechanism I described.

  ...if ... the one-way function could be broken by a third party, then could they decrypt the message with a key generated by the other prime?

Yes. The message wouldn't be generated by another prime in the case of RSA, but if they could somehow undo the one-way function, then the cryptosystem is broken and all your messages would be readable.

  Would it matter which prime was used?

It does not matter. They just need to be big! At one time, the choice of prime did matter, for resistance against  Pollard's p-1. However, it is now thought that for more advanced methods this is not the case.

For Textbook RSA you can actually interchange the keys $d$ and $e$, which makes RSA a trapdoor permutation, however, in this case $d$ the product of two primes is still the private component, even though it is used in the "role" of encryption.  If things are done properly using "production quality" crypto like PKCS# 2.2 then the keys are not interchangeable as the functions for encryption and signatures are different.

  What i am wondering is what is the process whereby the primes behind the one-way function are converted into keys and is that process the same regardless of encryption used?

The $de = 1 \mod (p-1)(q-1)$ process is not the only way to relate $d$ to $e$. You can also use $\lambda(n)$, the Carmichael function, which is what happens in PKCS#1.

Other public key systems have different conversion functions, not all of which rely on the use of prime number factorisation. Common examples are the discrete logarithm problem and point multiplication over elliptic curves.


Did Merkle invent cryptographic hashing?

I think the first paragraph of this document show be helpful.

The Rabin reference at the bottom of the text is from 1978, and the impression I get from p3 of this document is that he came up with a linear iterated hash function in that 1978 paper. So maybe Rabin invented it.

I think we can be pretty sure it was either Merkle, Rabin or Yuval (if you must choose one), but that sounds like an answer correct for a good deal of history questions in this field.

Alt link


How is message length involved in public/private-key encryption?

First let me emphasis again that signatures are something entirely different than public key encryption. Please read the comments to your question and keep those in mind.

That said, in both cases (signature & public key encryption) schemes are designed for fixed message sizes. For RSA signatures and encryption the maximum message length is determined by the size of $N = pq$ (assuming the school book notation for RSA). You can neither sign longer messages nor encrypt them.

What applications will do is using a cryptographic hash function in case of signatures to reduce the message length to a fixed small value. In case of encryption they will use hybrid encryption, i.e. the application will generate a random secret key for symmetric encryption, encrypt it using the public key scheme and encrypt the message using symmetric encryption with the generated secret key.


Why choose an authenticated encryption mode instead of a separate MAC?

If you look closely at the definition of authenticated encryption modes, you will see they all are, actually, the combination of symmetric encryption and a MAC.

Using traditional encryption and an independent MAC has a few tricky points, none of them being unsolvable:

The encryption mode will use a key, and the MAC will also use a key; using the same key may trigger unwanted weaknesses (e.g. if the encryption uses CBC mode and the MAC is CBC-MAC). Solution: derive both the encryption key and the MAC key from a "master key" through a Key Derivation Function.
The encryption uses an Initialization Vector, and the MAC may also use an IV of its own. Using the same IV for both may, then again, imply weaknesses, especially since the requirements for both IV may be distinct. Solution: use a KDF to derive two IV from a "master IV"; or use an IV-less MAC such as HMAC (that's the great advantage of HMAC: no IV; hence, it is very hard to get it wrong with HMAC).
A MAC may (theoretically) leak information about the processed data. This is the whole mac-then-encrypt or encrypt-then-mac debate. Solution: encrypt-then-mac is the "right thing" but it is easy to get it wrong by forgetting to MAC the encryption IV and/or the encryption algorithm identifier. SSL/TLS does the "wrong thing" but gets away with it because HMAC is "sufficiently different" from block-cipher based encryption.

An Authenticated Encryption mode is designed to solve these questions and do "the right thing" so that the requirements for the user are as light as possible (e.g. a single IV with just a "non-repeating" clause, not needing unpredictable randomness or uniform distribution).

Summary: authenticated encryption should not be opposed to traditional encryption combined with an independent MAC; authenticated encryption is "combined traditional encryption and independent MAC, done properly".


How can there be AES-256-GCM, when GCM is defined for 128-sized blocks?

AES has a block-size of 128 bits in all its variants. The number in AES-128/192/256 is the key-size. Rijndael, the block-cipher that became AES, also supports 256 bit blocks, but that part was not standardized as AES.

Since the block-size is 128 bits, GCM works exactly the same way for AES-256 as it does for AES-128.


If I would choose a factor of 2 it would make the record (=packet/payload length???) twice the original size. Is that correct?

No; if you set a factor of 2, then the encrypted record size would always be even (that is, if it would have been odd, a padding byte would be added).
In general, a factor of $x$ would increase the size of the encrypted record from 0 to $x-1$ bytes.


Lower Bound on the Probability an LWE Matrix is Primitive

I think you're overthinking it.

Hint

The event in which $A\cdot \mathbb Z_q^m \neq \mathbb Z_q^n$ is the event in which the matrix $A$ has a rank defect, which is "contained" in the event in which (say) the first row is a linear combination of the other rows.
Now, what's the probability of the latter event?


Generalizing a CBC-MAC collision with a common final message block

CBC-MAC is calculated by iterating a block cipher in CBC mode over the blocks of the message, using a start value of 0 - i.e. $CBC{-}MAC(a)$ is actually $CBC{-}MAC(0,a)$.

Since the first part of the messages (i.e. $a$,$b$) in your example have sizes that are multiples of the block length, the $CBC{-}MAC$ of each of them creates a chaining value that can be used as the input to $CBC{-}MAC$ of the second part of the message ($c$,any $d$)

For your example:

$CBC{-}MAC(a||c)$
$= CBC{-}MAC(0, a||c)$
$= CBC{-}MAC(CBC{-}MAC(0, a), c)$

So $CBC{-}MAC(a||c) = CBC{-}MAC(b||c)$ when $a = b$, but more generally when $CBC{-}MAC(a) = CBC{-}MAC(b)$

When this is true, it's easy to see that $CBC{-}MAC(a||d) = CBC{-}MAC(b||d)$ for all $d$.
i.e. once a collision is found with $CBC{-}MAC$ for two messages $a,b$ whose lengths are multiples of the block size, then the $CBC-MAC$ of $a||d,b||d$ will also be equal for all $d$.

I'm not sure why the exercise focuses on this property (except to illustrate what's obvious from the CBC basis of the design).


Using a stream cipher for mass generation of "random" bytes is a fairly good solution, however the risk is loosing Forward Secrecy at some point. The trick then is re-keying the cipher often enough, and having a good source of random data with which to rekey your cipher.

See Fortuna.


Why does a nonce prevent a replay attack?

Given no knowledge of the MAC key and that M1 != M2, it is not possible to compute MAC(K, M2) from MAC(K, M1).

More generally, it isn't possible to determine the MAC of any message you haven't already seen. (Again, without the key.) The definition of a nonce is a number which is only used once with a given key.

Bob ensures that nonces are only used once by rejecting requests unless the nonce value Alice submits is strictly increasing.

There are other problems with this protocol. I assume it's meant to be used to authenticate users. No information is transmitted besides what is basically just proof that Alice knows K.

The protocol functions a lot like a one time password scheme and has the same limitations. It doesn't prevent MITM attacks, session hijacking, or server impersonation. It is not a full communication protocol.

Sometimes people comes up with schemes like this to control locks or appliances. It is unsafe to use such a protocol with "toggle" signals. An authentication request could be blocked, leaving a user's device in the state opposite from the state they believe it is in.

It is also possible to combine blocking Alice's requests with a replay attack. One could block Alice's request to engage a lock, trespass, then play back Alice's message to make it look like the lock was engaged the whole time.

Delayed playback can be solved by Alice instead sending MACK(NA || timestamp). (As long as Alice and Bob have trusted synchronized clocks.) An acknowledgment message could allow Bob to tell Alice that the command was received. The ack would needs its own authentication tag, otherwise it could be spoofed.


Can multi-encrypted file be decrypted with one password only?

Theoretically speaking, there is a possibility that a specific hashing algorithm can hash two separate passwords that both result to the same hash, however the odds of such an event making much of a difference in a brute force attempt is minimal. In addition, if there are two separate file containers (one inside the other), a brute force attempt would stop after decryption the outside container. My recommendation for encryption would be AES-256 encryption with SHA-512 hashing as those are currently accepted as industry leading algorithms. Should you care to, veracrypt will give you an option nest encryptions such as Serpent-Twofish-AES which will in turn make decryption take more time.


The exercise is not about ElGamal in the slightest. I would even call it bogus:

"$n$" would be the modulus, which is clearly not prime, being divisible by $2$.
The values $pk,g,n$ seem to be in decimal, the values $c_1,c_2$ in hexadecimal - but nowhere stated what kind of encoding is used.
It looks like exponentiation in the integers was used, but $c_1$ isn't a power of $g$
Trying around in WolframAlpha how those values were generated I got nothing, but $c_1$ isn't divisible by $n,pk$ or $g$ when considering them as decimal or hexadecimal encoding.
Is it a coincidence, that if you want to do some WolframAlpha computations with these numbers in decimal, the input field is just not long enough? $c_1$ alone fits, but it leaves you just with 5 more input characters. Using all numbers in hex works, tho.

Since the source you quoted is another question how to interpret this, this is definitely not the author.

At this point I can only suggest looking for reliable sources, e.g. exercise material from universities, textbooks or examples on Wikipedia. Looking at any kind of material where you don't know the author and the background has the potential to actually damage your learning progress.


Is a single md5 hash a good way to generate an AES key?

Assuming that the password/phrase is in fact a password/phrase, and does not already contain sufficient complexity to prevent guessing (e.g. is not a cryptographically strong random string)...

  Is this true?

No. An attacker will simply guess at the password, and a fast hash function will help them to guess faster. An attacker can try a truly ridiculous number of md5 hashes per second, and will certainly break any password/passphrase that was not generated to be cryptographically strong.

  Why is something like bcypt/scrypt not required?

Slow hashing is required, and the information in the article is not good advice. Choosing MD5 because it offers the right digest size out of the box is not justifiable: Stronger 256-bit hash functions exist (e.g. SHA256), and a larger hash digest could easily be truncated down to 256 bits

A cryptographic hash function is not appropriate for use on passwords/passphrases.

  Is AES slow enough to prevent a brute-force attack?

No, and it is not the ciphers responsibility to be slow to prevent brute-force attacks on the key. Assuming that they key is strong enough to be called a key (e.g. a uniformly random bit string), then having a slow cipher is completely non-productive.

So the responsibility for being slow to prevent guessing attacks falls to a step before encryption takes place, namely, the key derivation step. Functions such as Bcrypt/Scrypt/Argon2 are explicitly designed for the purpose.

Alternatively

If the passphrase was generated randomly and designed to possess sufficient entropy, then using a slow key derivation process is not really necessary or beneficial. In such a case, using something like HKDF would probably be the most appropriate.

In any case

Selecting MD5 from a list because it seems fine is not a good sign...


The person who asked the original questions seems to have deleted the account, so here's a full solution for future reference instead of just a hint:

Assume that $G':\{0,1\}^{n-1}\to\{0,1\}^{m-1}$ is pseudorandom and $f':\{0,1\}^{n-1}\times \{0,1\}^{n-1}$ a one-way function. We construct the functions
$f:\{0,1\}^n\to \{0,1\}^n$ and $G:\{0,1\}^n\to \{0,1\}^m$ as follows

$$f(x) = x_1f'(x_{2,\ldots,n}),\;\; G(x)=x_1G'(x_{2,\ldots,n}),$$

where $x_1$ denotes the first bit of the input and $x_{2,\ldots,n}$ the remaining bits. Clearly, $f$ is one-way and $G$ is a pseudorandom generator. As distributions, we then have

$$G(U_n) = U_1 G'(U_{n-1})$$

and

$$f(U_n) = U_1 f'(U_{n-1}).$$

It's then trivial to construct a distinguisher for $(f(U_n),G(U_n))$ and $(f(U_n),U_m)$. The distinguisher gets as input a pair $(x,y)$ and checks whether the bits $x_1=y_1$. If this holds it will return $1$ and if $x_1\neq y_1$ it returns $0$. If the input comes from $(f(U_n),G(U_n))$ we always return $1$ and in the other case we return $1$ by probability $1/2$. The distinguisher therefore has advantage $1/2$, so the distribution $(f(U_n),G(U_n))$ is clearly not pseudorandom.


What does SSL use? RSA? El-Gamal? Elliptic curves?

Well, what SSL uses to negotiate the symmetric keys depends on the ciphersuite that both sides agree upon.  By far, the most common method is that the client picks a random value (the premaster secret), and encrypts it with the server's RSA public key.  However, it is not that unusual for the ciphersuite to specify that the client and the server agree upon a premaster secret using the Diffie-Hellman algorithm (or the Elliptic Curve version), with the DH exchange generally (but not always) being protected via some sort of signature operation.

El-Gamal isn't generally used; in fact, I don't believe that there's a standard ciphersuite that specifies it.


Ed25519 is a specific implementation of EdDSA using the Twisted Edwards curve:

x^2 + y^2 = 1 + (121665/121666) * (x^2)(y^2)

It's known as high speed high security signature algorithm. For using the code you pointed out, you need to feed sk, pk, m, sm.

So first you need to call publickey function with sk, then call signature function with m, sk and pk. PK is byte array returned from publickey function.

An example entry:

9d61b19deffd5a60ba844af492ec2cc44449c5697b326919703bac031cae7f60d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a:d75a980182b10ab7d54bfed3c964073a0ee172f3daa62325af021a68f707511a::e5564300c360ac729086e2cc806e828a84877f1eb8e5d974d873e065224901555fb8821590a33bacc61e39701cf9b46bd25bf5f0595bbe24655141438e7a100b:

It's sk:pk:m:sm

You can find more info at:
http://ed25519.cr.yp.to/index.html


How is pre-master secret encrypted when ECC is used?

How then is the pre master secret encrypted?

It isn't.
What you're looking at is the ECDHE key exchange for TLS.
The short description is that the server and client run a classic Diffie-Hellman  key exchange (on an elliptic curve) and use the resulting shared secret as the pre-master secret. This is unlike the RSA Key-Transport case where the client picks a pre-master secret and sends a public-key-encrypted copy to the server.

Now for the technical details (from RFC 5246: "The Transport Layer Security (TLS) Protocol Version 1.2"):
The client sends its list of supported cipher suites (in ClientHello) and the server responds with the cipher suite picked, which is TLS_ECDHE_ECDSA_CHACHA20_POLY1305 in this case (happens in ServerHello). In the same run the server sends its public, ephemeral ECDH key (in ServerKeyExchange) which is most likely a point of Curve25519. The client receives this and responds with his hown public key (again a point) and the client also computes the shared point and then uses the full x-coordinate as the pre-master secret. As soon as the server receives the client's public key it also computes the pre-master secret (ie the x-coordinate of the shared point).

Now both parties share the same pre-master secret, exchanged using ECDHE.


Is it possible to successfully encrypt/decrypt in DUKPT using different sized BDKs?

As this is symmetric key encryption the key used to encrypt the data must be used to decrypt the data so if a double-length TDES key encrypted the data, the same double-length TDES key can decrypt the data. A triple-length TDES key cannot decrypt data encrypted by a double-length TDES key and vice versa.

The P2PE requires that the minimum length for a TDES key be triple-length, i.e. 192-bits (168-bit excluding parity). However, if implemented as part of a DUKPT key management scheme, the TDES keys may be double-length. This is detailed in the footnotes of Appendix C.


Why can an elliptic curve private key be 1?

By the same argument, they would have to forbid $d = 1234$; after all, an attacker can trivially compute the value of $1234 G$; and if they see it, then they can immediately infer $d$ without having to complete a discrete log over an elliptic curve.  Of course, this logic would forbid all possible values of $d$...

The issue is that if the attacker gets lucky and guesses $d$, he wins (and there's nothing special about $d=1$ in this).  However, he is quite unlikely to get lucky (and again, there's nothing special about $d=1$ in this either).


What would a backdoor in symmetric key cipher look like?

As usual, inserting a backdoor in a symmetric cipher becomes a lot easier if you have knowledge your adversaries lack.

DES is a pretty good (counter)example of how a backdoor could be introduced in a symmetric cipher.

Back in 1974, IBM and the NSA both knew about differential cryptanalysis, but they did not publish their findings. Some 16 years later, differential cryptanalysis was rediscovered and published by Biham and Shamir. As they found out, DES's S-boxes – which are precisely the part of DES prople suspected to contain a backdoor – were surprisingly resistent to differential cryptanalysis.

As it turned out, the S-boxes were designed to to repel this type of attack. In theory, since the NSA knew about differential cryptanalysis but the general public didn't, they could have chosen S-boxes that were exceptionally vulnerable to it. That would have been a backdoor.

Another example would be the use of apparent trapdoor functions with a known inverse.

To see how this could be exploited, suppose nobody knew about RSA. Define $R(X)$ as the RSA encryption of $X$ with a certain public key and design a cipher that generates the stream $$R(1\times K) || R(2\times K) || R(3\times K) || \cdots$$ where $K$ is the secret key for your stream cipher.

If you know the associated private key, you can easily compute $R^{-1}$. Now, if you know enough plain- and ciphertext to figure out part of the stream – let's say $R(1\times K)$ – all you have to do is apply $R^{-1}$ to figure out $K$.

Nobody will be able detect the vulnerability without essentially discovering RSA.


Why PS does differ between PKCS1 v1.5 padding for signature and for encryption?

Maarten Bodewes answer is correct, but it is missing one important point.

It is actually NOT secure to have randomness in PKCS#1V1.5 padded signatures, otherwise signatures could be forged via bleichenbacher's e=3 attack.

Take a look at https://blog.filippo.io/bleichenbacher-06-signature-forgery-in-python-rsa/ to see what happens when signature verification implementations forget to assert that those bytes are actually 0xFF.


How to Compute C^2 in AES MixColumns Matrix?

hi Ruby i know how it comes. But before that i assume you have a good knowledge of finite field.

Actually, it's the problem of how to calculate $$C^2(x) = (\{03\}X^3 + \{01\}X^2 + \{01\}X^1 + \{02\})^2$$. Becuase the character of $K$(as in the paper) is 2, so $$C^2(X)=(\{03\}X^3)^2+(\{01\}X^2)^2+(\{01\}X^1)^2+(\{02\})^2$$.  But you have to know the meaning of $\{03\}$  $\{02\}$ and $\{01\}$. They are elements of $F_2^8$. For example $\{03\}$ stands for $x+1$, so $(x+1)^2=x^2+1=\{05\}$. Like this we get:$$C^2(X)=\{05\}X^6+\{01\}X^4+\{01\}X^2+\{04\}$$
Next as $R=K[X]/(X^4+1)$, you have to put them in $R$ by  $mod(X^4+1)$$(X^j mod (X^4+1)=X^{j mod  4})$. so we get:$$C^2(X)=\{05\}X^2+\{01\}+\{01\}X^2+\{04\}$$.
Next as $\{05\}=x^2+1,\{01\}=1,\{04\}=x^2$, so when we 'add'(this add in the finite field means XOR)then we get:$$C^2(x) = \{04\}X^2 + \{05\}$$


Formal modeling and automated verification of a remote attestation protocol

Maybe this is a good starting point:
"Formal Analysis and Implementation of a TPM 2.0-based Direct Anonymous Attestation Scheme", which appeared at ASIACCS 2020:
https://people.inf.ethz.ch/rsasse/pub/eccdaaimp-asiaccs20.pdf
It uses the Tamarin prover, and the Tamarin model files are available for download.


Do Chosen-Chiphertext attacks only apply to public-key cryptosystems?

No, there are also CCA games for private key encryption schemes. There you have additional encryption oracles that you can use, to obtain encryptions for messages of your choice (in a private key encryption scheme you can not encrypt yourself, because this requires the secret key).
See here for a concise explanation and comparison:
http://crypto.cs.uiuc.edu/wiki/index.php/IND-CCA


The main differences between Sketch of Proof and Full proof

The answer to this question is not straightforward and has a lot to do with the "conference culture" of computer science. Unlike other fields, the main publication venues for CS are conferences and not journals. This isn't to say that journals don't have an important role; rather, you don't follow journals to see what research is being done - you follow conferences. (Note that also unlike other fields, conference papers ARE peer reviewed. So, some basic validation has already been done.) Journals are mainly there to validate correctness in a more rigorous way. Much has been said about the advantages and disadvantages of this culture and there are certainly both. Conference culture enables a very fast dissemination process, but it also means that people work towards deadlines and don't always have full proofs.

Ideally, one would expect researchers to have full proofs of security and then cut them down to proof sketches in the conference version. However, in many cases, this just isn't true, and this can lead to errors. Note that even when writing full proofs you can have errors, and I've had my fair share of published mistakes. However, at least I try to do my best in writing a full proof (which also makes it easier to spot the mistake if it's there). To be honest, though, I haven't written full proofs for all my papers as well, and I too am negligent in that.

Having said all of the above, some things are so obvious to the experienced researcher that writing them out in full is actually a disservice. We all know how a standard hybrid argument works, and therefore writing it out will only fill up the paper with useless details that don't help at all in understanding the result. My recommendation is to always write out the full hybrid to check that there is no subtlety. Then, if it turns out to truly be standard, writing "the full proofs follows a standard hybrid" is not only OK but also better. So, sometimes proof sketches are not laziness or lack of rigor, but a way to make a proof more readable to the experienced reader (and the inexperience would be best served by learning this in Goldreich's book anyway).

In summary, why aren't proof sketches always written?

Sometimes the full proof is just a difference of obvious details and not good to publish
More often, it's due to the conference and not journal culture. This can be due to the fact that the researchers are working to a tight deadline and never wrote a full proof [VERY BAD IN MY OPINION] or due to the fact that the conference limits the page numbers and so it can't be put in [ALSO PRETTY BAD].

The right thing to do scientifically is to have a full proof (modulo details that are not worth putting in as in the previous item) and then cut it down to a proof sketch for the conference version. In this case, a full version should always be put on your homepage or ePrint, and if it's an important result then it should be sent to a journal.

One last point, conference papers are now rarely actually printed, making the page limit quite unnecessary. Of course, it's not possible to review the entire paper in the conference refereeing procedure, but the published version can be considerably longer and numerous conferences are doing this. Still, in many cases, it's not long enough for a truly full version and this should be posted as mentioned above.