Can you prove the existance of a PRG $G$ s.t. for each even $k$: $G(k)=G(k+1)$?

@Bush - What you really mean to ask is whether there is a "Cryptographically Secure" PRG (CSPRG) that has the property you describe.  The nature of PRG's and CSPRG's remain to me a bit deep and obscure - and to some extent I think this might be intrinsic, the whole field of crypto may be embedded in this one question on the nature of pseudo-randomness; but I'll give it a go.

Let's start with the PRG.  You can find a definition here.

This basically says that a PRG produces a "scatter" of points on the image set that approximates the uniform distribution.  More precisely, if we consider a set $E$ in the image set of the PRG, then the measure of the set of points that the PRG maps into $E$ is very close to the measure of $E$.

(Since we are essentially always dealing with finite sets and uniform distributions, then we are saying that the fraction of the domain that is mapped into $E$ is very close to the fraction of the image that is represented by $E$.  In technicalese, "the pushforward of the uniform measure on the domain via the PRG is uniform".)

So, let's suppose we have a PRG $F: DF \rightarrow I$.

Define a new function $G: DG \rightarrow I$, st. $G(2n)=F(n)$ and $G(2n+1) = F(n)$.

We have:

$ g(k) = F([|k/2|])$, where $[|x|]$ is the greatest integer $<= x$.
$|DG| = 2|DF|$, where $|S|$ is the number of points in the set $S$.

For a set $E$ on the image space, the number of points that map into it via $G$ is just $2x$ the number of points that map into it by $F$.  On the other hand, the domain of $G$ is twice as big as the domain of $F$.  So the measure of the preimages via $F$ and $G$ are the same.  So, if $F$ approximates the uniform distribution on $I$, then so does $G$.  Therefore, if $F$ is a PRG, then so is $G$.

While I belive the above is correct for a PRG, a CSPRG is a more restricted notion that includes the "next bit test", along with the ability to withstand state compromise. See here.

The reason we would want the next bit test in our definition is clear.  The whole point is that the CSPRG should give us a (one time) semantically secure stream cypher.  If the first few bits could give us some information about the next bit that the PRG generates, then this would give us some information to distinguish the PRG output from uniformly random.  So, given messages $m_1, m_2$ and a ciphertext $c$, we could distinguish which of $m_1 \oplus c$ or $m_2 \oplus c$ is more likely to be the output of the PRG.  That would allow us to break semantic security.

I think the restriction on state compromise, may be just an extension of this.  If we generate a key by concatenating shorter keys: $F(n)||F(n+1)||F(n+2)|| \ldots$, we don't want exposure of one part of the key, $F(k)$, to give us information about previous or later parts of the key, eg $F(k-1)$ or $F(k+1)$.

At first glance it appears to me that if $F$ satisfies the next bit test, then so will $G$.  On the other hand, If some of $G$'s state is revealed (eg, $G(k) != G(k+1))$, then we can predict a part of it's past ($G(k-1) = G(k)$) and future ($G(k+1) = G(k+2)$).

I hope that helps.  I'll be watching eagerly if someone has something to add.


Proving that 2 numbers are different without revealing them

Yes, this is a standard secure two computation problem. There was a classic paper discussing this from many years ago called Comparing Information Without Leaking It. There are more efficient methods today (in fact, the oblivious transfer method today is very efficient using oblivious transfer extensions).


The threshold value for any node in the tree is the minimum amount of child nodes that is needed for derivation of the secret. For an OR node the threshold value is usually 1 while for an AND node the threshold value is equal to the number of child nodes. For instance from your diagram, the threshold value for the AND node numbered 1 is 2 and the threshold value for the other node is 2. The threshold value for the root node which in your diagram is r will also be 2 because it is an AND node and it has two sub nodes attached to it.
index (x) is simply a way to keep track of all the individual nodes that are part of the whole tree so you can evaluate them accordingly i.e according to their position in the overall tree which means being able to identify what child nodes are attached to any certain node and what parent node a particular node is attached to.

Hope this helps.


The CTR-IV either must be random or regularly incremented in a way that the IV never repeats again. If there is a repetition then the encryption will be insecure.

In rfc5647, it is the second way; regularly incremented.

invocation_counter is incremented per package. Section 7.1;

  The invocation field is treated as a 64-bit integer and is incremented after each invocation of AES-GCM to process a binary packet.

block_counter is incremented per AES encryption within the package. It must be initialized to 1 for per package, otherwise, an overflow will occur and therefore the IV's cannot be unique. Section 7.1;

  The block_counter is initially set to one (1) and incremented as each    block of key is produced.

The 4-octet block counter matches with the size of the package that is defined in section 5.2 as;

uint32    packet_length;  // 0 <= packet_length < 2^32

Thus, this counter can be incremented for all encrypted blocks within one package. For a new package the set to 1 (that is your latter case).

For the second part, this can happen if ECB mode is used and the data sizes are multiple of the block cipher. Even in this case, a padding scheme must be applied. that will prevent your equation.


With composite $n_1$ = $p_1q_1$, and a separate $n_2 = p_1q_2$, can the primes be calculated more efficiently than factorization?

Yes, this trivially compromises them. Simply compute the gcd of $n_1$ and $n_2$, which will return $p_1$ (assuming $q_1 \neq q_2$). The gcd can be computed efficiently using Euclid's algorithm.


Does encrypting a result of AES block cipher provide more security?

Long Story Short

If you only want to store the data as a backup service, do your double encryption yourself, have a backup somewhere. If you want to process the data, you may need FHE, but you need integrity, authentication, and freshness.

Let assume that the client wants to store some data on the cloud and the cloud service provider (SP) offers the client two ways as in your question.

Let's define the models for the service provider;

Honest: obeys the protocol
Semi-honest; obeys the protocol but tires to extract information. Can copy but cannot modify.
Malicious: Doesn't need to obey the protocol. Can diverge from the protocol whenever appropriate.

Assuming that SP doesn't add encryption.

In this case, if the data has no semantic security, The semi-honest SP can extract information by frequency analysis.
A malicious SP has much more power on your data than semi-honest SP. When the client requests data $d$, SP can return $d'$ where the $d'$ can be some other data or the previous version of $d$ and we call it the freshness (rollback) problem. There is no easy way for the client to believe that the data is authentic without storing some information about the data he uploads to the server as Merkle-Tree.

If the SP offers additional encryption as in your case 2, then;

The semi-honest SP can still extract information as in no encryption case since the encryption is performed by the OP.
The malicious SP same as no encryption with more power, he doesn't need to store with double encryption, he can store as you sent him.

What about the attackers. In short, we can talk about the attackers as malicious SP. Some may claim that the frame of the attacks is short, but not necessary.

The biggest problem here, the attacker may steal the data and the encryption key of SP. So, SP encrypted or not the data can be accessed by the attackers as the client uploaded. Some cay says that Hardware Secure Modules can store the encryption keys, but the attackers can use them as an encryption/decryption oracles as the SP does.

So, the second encryption may not give much benefit as one consider.


Why does a primitive root mod n gives a uniform distribution over n?

From the definition of a primitive root, as recovered by fgrieu:

  A number $g$ is a primitive root modulo $n$ if every number $a$ coprime to $n$ is congruent to a power of $g$ modulo $n$

and following-up from that:

This implies that $f(x)=g^x\bmod n$ is a bijection into $\mathbb Z_n^*$, the set of all integers smaller than and co-prime to $n$ greater than 0, i.e. $\{1,2,3,\ldots,n-1\}$ for a prime $n$. It's a bijection because every element can be reached (surjective) and no element is reached twice (injective) when iterating through all values $x$ just until (exclusive) you hit the first repetition in values. It's also a classic result that applying a bijection to a uniformly distributed variable results in a still uniformly distributed variable, i.e. bijections preserve uniform distribution.


Which party have to be online during garbled circuit-based MPC protocol?

Alice can construct a garbled circuit for $f$, send to Bob the keys corresponding to her input, and use oblivious transfers to let him learn the keys associated to his input. After that, she can go offline. Bob can then locally compute his output $a$ (meaning, he does not have to be online during this part of the computation). Then, he plays with Charlie the same way Alice played with him: he must be online to send to Charlie a GC, some keys, and execute oblivious transfers. Both can go offline after that, and Charlie can locally compute his output.


Parallel Pollard's Rho: Number of distinguished points

The expected number of points $\sqrt(\frac{n\cdot \pi}{2})$ is calculated via the birthday paradox and it applies to the number of calculated (not just distinguished/reported) points. As you said, each distinguished point represents $2^{32}$ points. Even if a collision is not reported (because it is not on a distinguished point), the two walks which collided will continue on the same path and eventually find the same distinguished point. That is where the ...$+\frac{1}{\theta}$ comes from in the complexity in the original Oorschot et Wiener paper. $\theta$ is the probability that a point is distinguished. So you have, the number of computations until a collision occurs, + the number of computations before that collision is reported i.e. before you reach the next distinguished point.

In practice, I haven't had a problem with Robin hoods, but Oorschot et Wiener seem to suggest that to avoid Robin hoods you need to take $\theta$  small enough that trails are long.


There is no security improvement for using an algorithm with ciphertext expansion. In fact, it's really only an unavoidable side-effect of certain public key operations. It's not something that's desired.
Anyway, time for the obligatory don't roll your own. No matter how secure you think it is, it isn't. If you want to learn about cipher design, read about existing ciphers, like this one.


Yes, but unless there is a significant break through in the crypto-analysis of SHA-1, the only way to retrieve the constant value is by brute forcing it. In other words, trying all the values, calculating the SHA-1 over the plaintext and the constant and comparing it with the given hash value.


With Damgård-Jurik, not only expansion factor is decreased: this scheme improves state of the art.

Reducing size of prime factors makes better chance of factoriation or maybe solving particular decision problem that Paillier scheme depends on.


How to compute two EC point multiplication?

There is no standard "multiply two group elements" operation in an additive group. So you first need to define what you mean by $P*Q$. From the comments I gather that you want $P*Q = q P = p Q = (p \cdot q) G$.

The computational Diffie-Hellman (CDH) problem is:

  Given $P=pG$ and $Q=qG$ compute $(p\cdot q)G$.

which is clearly equivalent to your problem.

If the discrete logarithm (DL) problem is easy for the group, you can first solve $P=pG$ for $p$ and then compute $P*Q=pQ$. But on the curves we use in cryptography both DL and CDH are believed to be hard. While such groups may exist, I'm not aware of any groups in which DL is hard but CDH is easy.

Another problem of interest is the decisional Diffie-Hellman problem:

  Given three group elements $P=pG$ and $Q=qG$ and $R$ decide if $R = (p \cdot q) G$.

There are some curves for which the decisional Diffie-Hellman problem is easy while the computation Diffie-Hellman problem and the discrete logarithm problem are hard. These groups are know as gap-groups and are useful in cryptography, for example they're used in the BLS signature scheme.


As the paper of MSS-SPR does not contain any One Time Signature scheme

Actually, that's not true; they assume Lamport signatures (specifically, a version they call LD-OTS).

When using the LD–OTS, the one-time signature of the message consists of
n bit strings of length n. The veriﬁcation key also consists of n bit
strings of length n, since half of the veriﬁcation key can be computed
from the signature.

Hence, the OTS signature is $2n^2$ bits long; in contrast, a WOTS+ signature (which XMSS uses) is $(n/4+3)n$ bits long, considerably shorter.

Now, the difference is actually larger than a factor of 4 - I believe that, if we take account of the fixed overhead of the authentication path (which is the same in both cases), and MSS-SPR's use of a somewhat smaller $n$, the two are closer.

  a fair comparison should use the same OTS in both schemes.

True; however as specified, the comparison isn't fair.

As for why MSS-SPR uses LD-OTS (rather than some Winternitz-based scheme), I'm not one of the designers, and so I can't be certain.  My best guess is that they couldn't come up with a shorter scheme that preserves the "not relying on collision resistance" property (which WOTS+ does).


It is not secure in general, but not insecure in general either.

For example, you can get a MAC algorithm for which it would be secure by concatenating constant data to a secure MAC. $Tag_k(m) = M_k(m)||0^n$ is a secure MAC if $M$ is. And clearly taking the first half of that is a secure MAC if $n = |M_k(m)|$.

On the other hand, reverse the order of the constant and non-constant part above and you get a MAC scheme for which taking the first half is very insecure.

If your secure MAC algorithm is based on a PRF, you can take the first half and have a MAC that is secure, but easier to guess randomly. (Because a secure PRF is a secure MAC and a truncated PRF is still a PRF.) Many MAC algorithms like HMAC and CMAC, for example, can be truncated for this reason.


How are private keys handed to users in Identity-based Encryption?

Crypto is nice and clean until you think about how to manage the keys. Common Identity-based Encryption (IBE) schemes have a tremendous disadvantage, that a trusted key authority generates private keys for some user and the user has to be given that key. The most common scenario for IBE is a corporate environment, so I will only ways to solve that in that environment. Note that all communication should be TLS encrypted.

If the user registers, they get an e-mail account and a private key that has that e-mail account as an identity. The security games in IBE schemes usually consider that an attacker can register many e-mail accounts and therefore request many the private keys with those. The schemes are proven secure when the attacker cannot derive the private key of an identity of another user.
This works fine, but the user would have to handle the key themselves and might even inadvertently misplace or leak it.
In a corporate environment, we usually have an IT department which either sets up the corporate workstation or adds a secure container on a BYOD-device. This administrator surely can write the private key for that user to a USB key and copy it to the configuration of the software that uses it. This makes it slightly harder for the user to do something dumb. Keep in mind that the private key can always be regenerated based on the e-mail account.
Other hardware is also possible. An administrator could generate the private key and push it to a smartcard which is then given to the user in person.
This has the added bonus that the user cannot really copy their privileges, because smartcards usually have a hardware-enforced copy-protection. They could still give their card to somebody else.

If the user abuses their privilege to access some data, be sure to have the necessary logs and a system in place to detect those events.


Small values with non-uniform distribution encoded as large values with uniform distribution

LFSR based
Since you want some simple not necessary secure than here one solution based on the LFSRs.
Let assume that each of your inputs has a length of 32-bit. Now, choose a maximal binary LFSR of length 128 ( yes not 32). Fill the LFSR's first 96-bit with 0s and the last 32 with your data. Now, run the LFSR $x$ times where $x>128$. Now take the next 128-bit as the mapping of 32-bit to 128-bit.
Maximal LFSR's with length $L$ generates all binary sequences of length $L$, except the all-zero case, in their periods. Your data will be the starting point on the sequence of length $2^{128}-1$ and the values will be not the same.
You can get your value back by running the LFSR in reverse. This is easy since you know the tap points. Otherwise, you will need 256-bits to construct the LFSR with the Berlakamp-Massey algorithm.
OTP based
A more simple solution based on OTP;
Generate a random 128-bit, and x-or you inputs by repeating 4 times. You did not want security, and this can map your input into 128-bit random. You can get your value back by x-oring the 128-bit key and taking the first 32-bit.
Block cipher based
Block ciphers are a family of permutations and with a fixed key, you select only one permutation from the family. Otherwise, selecting a random permutation and storing is infeasible, you need $2\cdot 2^{128}$ space to store. With the key, you can transfer back and forth. Also with the expected PRP of the block cipher, you can achieve good randomness, too.
AES is quite fast, especially with AES-NI can reach GB/s. Fix a key and use AES. This is quite easy since you can use OpenSSL tools to achieve this.


If I understand your cipher idea right, you would have a larger ciphertext alphabet than the plaintext alphabet, where each plaintext symbol maps to multiple ciphertext symbols (and the number is dependent on the frequency of the plaintext symbol), one of which is used randomly.

This is known as a Homophonic substitution, and with it the single-symbol frequency analysis usable for simple substitution ciphers is thwarted, since all symbols now have similar frequencies.

But as soon as we start to look at frequencies of letter-pairs (and triplets), we will observe enough structures to break this, too. For example, q is almost always followed by u, and thus the ciphertexts of q will almost always be followed by one of the ciphertexts of u. (I don't know enough about the statistic properties of the English language to give more examples, but you can be sure that an attacker would know.)

Some examples from German:

As in English, q is almost always followed by u.
A c is almost always followed by either k or h.
ei has about same frequency as ie (and i is the only letter who has this property related to e).

Some more details are given in David's answer.

Of course, if the ciphertext is so short (or the translation table so large) that each symbol is only used once or twice (or not at all), cryptanalysis is more difficult (or even impossible).


Why do we use hex output for hash functions?

Hexadecimal is traditional -- by this, I mean that there first were command-line tools that used hexadecimal for output, then other people using the hash functions found it fit to stick to hexadecimal, if only to be able to compare their values with the output of the aforementioned tools. That's how traditions get established: a more-or-less random choice at the start, then the need for interoperability and backward compatibility kicks in.

In the case of hexadecimal in cryptographic algorithms, one can probably trace it to the use of C language for reference implementations. Most algorithms are described with a specification (mathematical description, usually typeset in LaTeX), and a reference implementation that produces basic test vectors. For better or worse, the reference implementation is usually in C (or sometimes C++). In C, there is no standard facility for Base64 encoding (some programming platforms offer that, or external libraries, but it is not standard); but hexadecimal is easily obtained with a simple printf() with a "%08x" format string. As a very classic example, consider the MD5 specification (RFC 1321), which contains a reference implementation that does hexadecimal output.

The tradition is well entrenched; for the SHA-3 competition, NIST actually asked for reference implementations in C, and known-answer tests with a fully-specified text format that was hexadecimal throughout.

It must also be said that hexadecimal is convenient for debugging: the human developer can easily observe hexadecimal output and map these to individual bits, by doing the simple conversion in his head. Base64 is not as simple, because it entails 64 glyphs instead of 16, including some which are prone to induce visual confusion (1 vs I vs l, 0 vs O...). Also, many algorithm internally use 32-bit or 64-bit words, that map well to CPU registers; 32 and 64 are multiples of 4 but not of 6, so Base64 encoding again implies some non-trivial splitting.


This should be the flow of the description of RSA

RSA is a public key crypto system that everyone in the room who doesn't live in a cave uses pretty much every day. If you are using a computer to get on the internet, chances are you use RSA a lot.
Being a public key crypto system that means there is a public key that everyone knows and can use to encrypt messages and send them to you. Decrypting those messages is done using a private key that only you have. Pictures of Alice  and Bob  are always helpful here.
RSA works by using numbers of the form $N=p\cdot q$ where $p$ and $q$ are prime. If I have $p$ and $q$, then computing $N$ is really easy. But if I give you $N$, it turns out that breaking $N$ apart into the primes $p$ and $q$ is really hard.

Everyone can understand the math in that description. If someone has a hard time believing that breaking $N$ into $p$ and $q$ is really hard, then show them this

cb 12 fd 3b 32 8c 65 17 ff 39 2f 25 27 e3 80 ba bf d7 e4 5f 9a 65 a9 96 70 96 ef f9 49 36 79 97 e4 22 23 4c 9d af 5b 27 56 ef 6a 36 3f 4a 5d d1 44 fb 5d ca 21 7a f3 7c 39 cb ab 07 1c 6a ec 2c 21 64 37 1d 16 11 73 3f 7e 1f 68 a9 ea b5 bd 7a 05 6d 38 05 8d ef ee 23 1c e2 cf ec aa 22 d9 4e 84 47 38 c2 cd bc 1b 72 51 a3 64 46 f0 55 95 57 ee de 87 db 39 96 57 c0 42 58 1b 48 bc 5c 79 20 d9 96 4e e9 49 86 67 78 4f fe 4b 66 b0 f6 7d b9 e7 07 de c6 da d8 20 96 65 a0 de 4e a0 c4 76 f3 41 e7 e4 de c0 32 47 8d 5f a9 96 09 b8 46 5e e8 c0 3e d1 d0 69 e8 4c 26 3c 8e 69 1c 01 eb 61 ec ec 77 f0 e9 c2 fe 2a bf 8d 68 c2 1a 55 7d 61 ac 85 c8 f7 16 e2 a0 73 97 ff 26 5c 05 38 e6 e1 a7 89 13 d6 ac 13 aa 7e 44 87 83 07 ab f2 da a6 cf 38 a7 6b cb 17 07 62 08 a9 10 8e 58 8d 73 c6 e9

That is the $N$ that Bank of America uses and tell them that if they really think you are wrong, then the two of you should get together after the presentation so that you can go make a lot of money.

Personally I also like to show off pictures like this

Those are the inventors of RSA (Rivest, Shamir, and Adleman). By their picture they are obviously very smart, so the audience should just trust you that they know what they are doing.

In other words, if the audience doesn't need to understand all of the details of RSA, don't even try. Give them just enough that they can understand what they need to know. If they want more, deflect and take it offline as much as possible. Otherwise you will loose everyone else and probably the person asking the question.

Use lots of pictures and try to add some humor.


A "general computer" simply doesn't exist, test for yourself with this command:

openssl speed rsa

As an example here is the output on a Mac Pro 2007 withIntel Xeon 5130:

Doing 512 bit private rsa's for 10s: 67450 512 bit private RSA's in 9.95s
Doing 512 bit public rsa's for 10s: 961891 512 bit public RSA's in 9.94s
Doing 1024 bit private rsa's for 10s: 19914 1024 bit private RSA's in 9.93s
Doing 1024 bit public rsa's for 10s: 343029 1024 bit public RSA's in 9.98s
Doing 2048 bit private rsa's for 10s: 3101 2048 bit private RSA's in 10.00s
Doing 2048 bit public rsa's for 10s: 100363 2048 bit public RSA's in 10.00s
Doing 4096 bit private rsa's for 10s: 430 4096 bit private RSA's in 9.95s
Doing 4096 bit public rsa's for 10s: 27080 4096 bit public RSA's in 9.93s
OpenSSL 1.0.1 14 Mar 2012
built on: Tue Aug 21 05:18:48 UTC 2012
options:bn(64,64) rc4(16x,int) des(idx,cisc,16,int) aes(partial) blowfish(idx)
compiler: cc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -m64 -DL_ENDIAN -DTERMIO -g -O2 -fstack-protector --param=ssp-buffer-size=4 -Wformat -Wformat-security -Werror=format-security -D_FORTIFY_SOURCE=2 -Wl,-Bsymbolic-functions -Wl,-z,relro -Wa,--noexecstack -Wall -DOPENSSL_NO_TLS1_2_CLIENT -DOPENSSL_MAX_TLS1_2_CIPHER_LENGTH=50 -DMD32_REG_T=int -DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_MONT5 -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM -DAES_ASM -DVPAES_ASM -DBSAES_ASM -DWHIRLPOOL_ASM -DGHASH_ASM
                  sign    verify    sign/s verify/s
rsa  512 bits 0.000148s 0.000010s   6778.9  96769.7
rsa 1024 bits 0.000499s 0.000029s   2005.4  34371.6
rsa 2048 bits 0.003225s 0.000100s    310.1  10036.3
rsa 4096 bits 0.023140s 0.000367s     43.2   2727.1

And here is the same command on a slightly more up-to-date mobile (aka laptop) CPU (Intel i5 2540M)

Doing 512 bit private rsa's for 10s: 178265 512 bit private RSA's in 10.00s
Doing 512 bit public rsa's for 10s: 2244112 512 bit public RSA's in 10.01s
Doing 1024 bit private rsa's for 10s: 52008 1024 bit private RSA's in 10.00s
Doing 1024 bit public rsa's for 10s: 792898 1024 bit public RSA's in 10.01s
Doing 2048 bit private rsa's for 10s: 7216 2048 bit private RSA's in 10.00s
Doing 2048 bit public rsa's for 10s: 232383 2048 bit public RSA's in 10.01s
Doing 4096 bit private rsa's for 10s: 1012 4096 bit private RSA's in 10.01s
Doing 4096 bit public rsa's for 10s: 62854 4096 bit public RSA's in 10.01s
OpenSSL 1.0.1e 11 Feb 2013
built on: Mon Jul 15 12:44:45 UTC 2013
options:bn(64,64) rc4(16x,int) des(idx,cisc,16,int) aes(partial) blowfish(idx)
compiler: cc -fPIC -DOPENSSL_PIC -DZLIB -DOPENSSL_THREADS -D_REENTRANT -DDSO_DLFCN -DHAVE_DLFCN_H -m64 -DL_ENDIAN -DTERMIO -g -O2 -fstack-protector --param=ssp-buffer-size=4 -Wformat -Werror=format-security -D_FORTIFY_SOURCE=2 -Wl,-Bsymbolic-functions -Wl,-z,relro -Wa,--noexecstack -Wall -DOPENSSL_NO_TLS1_2_CLIENT -DOPENSSL_MAX_TLS1_2_CIPHER_LENGTH=50 -DMD32_REG_T=int -DOPENSSL_IA32_SSE2 -DOPENSSL_BN_ASM_MONT -DOPENSSL_BN_ASM_MONT5 -DOPENSSL_BN_ASM_GF2m -DSHA1_ASM -DSHA256_ASM -DSHA512_ASM -DMD5_ASM -DAES_ASM -DVPAES_ASM -DBSAES_ASM -DWHIRLPOOL_ASM -DGHASH_ASM
                  sign    verify    sign/s verify/s
rsa  512 bits 0.000056s 0.000004s  17826.5 224187.0
rsa 1024 bits 0.000192s 0.000013s   5200.8  79210.6
rsa 2048 bits 0.001386s 0.000043s    721.6  23215.1
rsa 4096 bits 0.009891s 0.000159s    101.1   6279.1


This is actually a fairly trivial case of secret sharing:

In the first case, we select a random value $R$, we give $X$ the value $R \oplus M$, and we give both Y and Z the value $R$.  Obviously, $X$ alone, nor $Y$ and $Z$ together cannot reconstruct $R$.

In the second case, we select random values $R_1$, $R_2$ and $R_3$, we give:

$R_1 \oplus M$ to $X$
$R_1$ to $Y$
$R_2 \oplus R_3 \oplus M$ to $C$
$R_2$ to $D$
$R_3$ to $E$

Shamir Secret Sharing is a neat trick; however sometimes problems can be solved by simpler methods.


The answer is that you can't; if you have a collision in $h^*$, you also have a collision in $h$.

The standard way to prove a collision-resistant hash based on a hash-resistant primitive is to show that if we are given a collision in the full hash, we can show that gives us a collision in the primitive.  Hence if we believe we can't find a collision in the primitive, we hence can't find a collision in the full hash.

That technique appears to work quite well here.

Suppose we are given two colliding messages $M$ and $M'$, that is $M \neq M'$ and $h^*(M) = h^*(M')$.  We will show how to examine how the two messages $M$ and $M'$ are processed by $h^*$ to show that there must have been some internal collision on one of the calls to $h$.

First, consider the case that $y_i \ne y'_i$.  If that is the case, then we immediately have a collision, because $h(y_i) = h^*(M) = h^*(M') = h(y'_i)$

The other possible case is that $y_i = y'_i$.  This implies that the length of the messages $M, M'$ are the same (because the lengths of $M, M'$ are included in the values $y_j, y'_j$.

We also know that $M, M'$ differ somewhere, that is, in at least one $n$-bit block.  Let us call $j$ one of the positions that $M$ and $M'$ differ; that is, $b_j \neq b'_j$.  This immediately implies that $y_j \neq y'_j$ (because $y_j, y'_j$ contain $b_j, b'_j$ as substrings).

Because $y_j \ne y'_j$ and $y_i = y'_i$ and $j<i$, that means there must be a $j \le k < i$ where $y_k \ne y'_k$ and $y_{k+1} = y'_{k+1}$.  That immediately gives us a hash collision in h, because $h(y_k) = h(y'_k)$


Is 3 rounds of Feistel enough for making a PRP?

Wel'll consider a symmetric Feistel cipher with $n$-bit block using ideal independent random functions at each round.

Making it computationally indistinguishable from a random permutation requires some number of rounds depending on the attack model; and on if we are content with asymptotic security for $O(2^{n/2})$ work, or want asymptotic security with more work, or want security for a prescribed small $n$.

Classical results for asymptotic security with $O(2^{n/2})$ work:

under random known plaintext, we need 2 rounds;
under chosen plaintext (that is, assuming an encryption oracle, the criteria for a so-called weak PRP), we need 3 rounds; see the famous work of Michael Luby and Charles Rackoff, How to Construct Pseudo-random Permutations from Pseudo-random Functions (in SIAM Journal on Computing Vol. 17, No. 2, 1988, initially  presented at Crypto 1985);
under chosen plaintext and ciphertext (that is, additionally assuming a decryption oracle, the criteria for a so-called strong PRP), we need 4 rounds; for a proof that 3 rounds are not enough, see this answer.

These classical results are nice, and relatively easy to establish, but not directly applied in common practice. First, $O(2^{n/2})$ suggests that for 128-bit security (the current baseline), we'd need a 256-bit block cipher (which is uncommon: 128-bit is mainstream, 64-bit used to be). Also, ideal independent random functions at each round is assumed, but actual round functions are quite far from that.

Things are more complex (and more rounds are needed) for asymptotic security with more work; see Jacques Patarin's Security of Random Feistel Schemes with 5 or More Rounds in proceedings of Crypto 2004, or his earlier Luby-Rackoff: 7 Rounds are Enough for $2^{n(1−\epsilon)}$ Security, in proceedings of Crypto 2003.

Even more rounds are needed for prescribed small $n$, and to my knowledge we only have heuristics.


For a random permutation $P$, what's the probability of the following event?

Assuming the $x_i$ are chosen independently of $P$, and the witdth $k$ of $x$ is not too narrow, it makes sense to use the approximation that $x\mapsto P(x)\oplus x$ behaves like a random function, at least as far as collisions are concerned.

Note: I wish I had a proof or convincing argument of that. The best I have right now is that without knowledge of $P$, we need nearly $2^{k/2}$ queries to $x\mapsto P(x)\oplus x$ in order to get a significant advantage distinguishing that from a random function. But that argument does not explain why the approximation still holds for e.g. $k=10$, $q=100$, when it does.

If further assuming that the $x_i$ are distinct, the problem becomes a straightforward application of the birthday problem for cryptographic hashing.


What are the fundamental roots of modern symmetric encryption?

There are a few here.

Block ciphers like DES and its modes are based of Feistel Cipher, AES is based on Rijndael.

Others like FOX64 based on Lai-Massey scheme.

Other are are stream ciphers like RC4.

So, These are some of the schemes which are used in todays symmetric key ciphers.


Tell me about non-MD5/SHA1 key fingerprints

Any secure hash algorithm can be used to generate a public key fingerprint - your choice depends entirely on which hash is expected by the other party.


Why does AES have exactly 10 rounds for a 128-bit key, 12 for 192 bits and 14 for a 256-bit key size?

Why these specific number of rounds only?
Because AES is a standard; AES is an acronym for "Advanced Encryption Standard".
The standard specifies these specific number of rounds to ensure that different implementations are interoperable.
Why not more or less?
The reason these specific numbers of rounds were chosen was a choice of the designers. They did a lot of math to determine that these were the sweet spot between sufficient security and optimal performance.
Less might be insecure, and more might be slower with no benefit.
To quote the above book (from Section 3.5 The Number of Rounds):

For Rijndael versions with a longer key, the number of rounds was raised by one for every additional 32 bits in the cipher key. This was done for the following reasons:

One of the main objectives is the absence of shortcut attacks, i.e. attacks that are more efficient than an exhaustive key search. Since the workload of an exhaustive key search grows with the key length, shortcut attacks can afford to be less efficient for longer keys.

(Partially) known-key and related-key attacks exploit the knowledge of cipher key bits or the ability to apply different cipher keys. If the cipher key grows, the range of possibilities available to the cryptanalyst increases.


Finding if two points on elliptic curve are related

No you can't.

I'll make the argument over the integers, it directly transfers to ECC points.

Suppose you have two integers $c,e\in\mathbb Z$. You can now prove for every $a\in\mathbb Z$ that $c$ and $e$ have $a$ "in common".

For this you simply pick $b=c-a$ and $d=e-a$ and now you have the "proof" that both have $a$ in common. Note how no restrictions whatsoever have been placed on $a,c,e$ so it works with all triples.


Why only one secret value with Shamir's secret sharing?

What you're looking for is called packed secret sharing. It was introduced by Franklin & Yung in:

Franklin, M. and Yung, M., Communication complexity of secure computation.. STOC 1992.

If you have a polynomial of degree $< d$, with at most $t$ corrupt parties, then you can use a single polynomial to hide $d - t$ secrets. It's not hard to see that you can't hide more secrets than this. To share $k$ secrets, you need $k$ degrees of freedom. The $d$ coefficients induce $d$ degrees of freedom, but each of the $t$ corrupt parties learns one linear constraint.

Note: in what you described in your post you have a polynomial of degree $< 4$ so if you take the standard Shamir setting of $t=3$ corrupt parties you can only hide the one secret value. While it is true that 3 shares together don't reveal any individual secret coefficient, they reveal linear relationships that constrain the secret coefficients to a 1-dimensional subspace.


Can CTR mode be used with public key cryptography?

I interpret your question to be asking "Can we directly use public key encryption algorithms with a CTR-like mode?", as opposed to "is it possible to perform a key exchange via RSA and use AES-CTR?" (which is obviously possible).

Let's define a "block cipher" as a deterministic algorithm that produces a permutation (the
"cipher" part) on a fixed-length block of bits (the "block" part). Non-randomized RSA meets this definition, though there are technically variants with different block sizes, determined by the modulus size.

The question then becomes "Can we apply textbook RSA to a public stream of incrementing numbers?", which is obviously a yes. However, doing so will not be secure. Non-randomized RSA is understood to be insecure. More importantly here, you will also be sending the nonce, and the adversary is assumed to possess your public key. Thus, nothing will prevent an adversary from applying $E(seed, public\ key)$ and generating the key stream himself.

"Randomizing" the above construction by using a random nonce will not work - if you are sending the nonce alongside the ciphertext, and the adversary has the key, the adversary can trivially recover the message.

So a secure CTR-mode using deterministic public key encryption such as RSA appears to be doomed.

Can we decrypt when counter mode is used if 1. we have the key and 2. we have the cipher text?

No, CTR mode generates a key stream by encrypting a counter, and adds the key stream to the message. Thus, if you do not have the seed for the key stream, you will not be able to regenerate the key stream and recover the message (assuming you do not resort to cryptanalysis to recover the message, anyways). While not sending the seed will disallow an adversary from recovering the message, it will also disallow the intended recipient from recovering the message, as both of them possess identical keys.


Would it be easier to bruteforce the original data if given two hashes (from different hash functions)?

IMO it depends on what you mean by the probability of successfully guessing the original data. Since hashing functions turn input of any size to a fixed-size output, there are (infinitely) many collisions. That may pose a problem with passwords, where any collision results in successful authentication. However, you only care about the correct preimage, as any other input, that produces the same output, (most likely) does not reveal Bob's valid public keys.

Suppose there is an attacker who knows your public keys format and is able to brute-force all possible keys. Then it is likely that more than one candidate will appear (depending on the length of your hash and public keys). The attacker then gets more information from the second hash as to distinguish which candidate is the correct one.

In that sense, you increase the probability of guessing the original data by providing a second hash.

But. I don't think that scenario is much to worry about - as you need the collisions of the first function to feed into the second function to gain advantage (or vice versa) and these are hard to get if the hashing function is well-chosen. Moreover, given that the number of such candidates might not be too high, the attacker might just as well try to DM using candidate keys rightaway.

If you worry about someone finding correct preimage of a given hash (or two), use properly-sized and random salt, different for each user. Ultimate booster: use different salts for each hash.


I can make a few comments regarding points 1 and 3:

If you are going to encrypt only one block, your first assumption is not that misled. However, you will almost always need to encrypt a file longer (maybe way longer) than the key length (let's say 128 bits). Without considering encryption modes, that means that for every block of 128 bits, you will encrypt with the same key. There are $2^{128}$ ways to encrypt the first block, but once you choose one, you have no freedom to choose the second.

(As a note, if you were to use different keys for each block, you would face the similar practical difficulties that make One Time Pad unpractical).

About rounds, the shortest answer is that the higher the amount of rounds, the "more scrambled" the text can get, but after a certain point, the improvement obtained by an additional round is not worth the overhead in performance.

There are two basic "operations" in cryptography. I have seen them by different names, but I first saw them as substitution and transposition. Substitution is like Caesar's cipher: you assign a different value for a character, but the value of every position is not affected by the others ( $E(M_1M_2M_3)=E(M_1)||E(M_2)||E(M_3)$). Transposition is like an anagram, or a Spartan scytale: the positions of the characters change, but the characters are untouched.

The aim is to mix this two techniques in such a way that the outcome yields no information about the original message. As you will see, each Feistel round will only have a small effect: a given bit will only affect a few bits on the ciphertext. Your target is that all bits of the plaintext affect all parts of the ciphertext.

Up to a certain amount (I believe 9), rounds are insufficient and they leak information. In cryptography, you do not want to live with the bare minimum, so several additional rounds were added.


Does NTRU provide Perfect Forward Secrecy?

Properly speaking, forward secrecy is a property of a protocol. The protocol is forward secret if compromise of the long term keys does not allow an attacker to decipher any past communications.

(Occasionally a distinction is made between that and perfect forward secrecy, with the latter secure when the attacker also knows e.g. all other session keys.)

You can build a key exchange protocol that provides forward secrecy from any authenticated public key encryption, including NTRU:

Assume the parties have exchanged long term keys.
A generates an ephemeral key-pair and sends the public key to B, using the long term keys for authentication.
B generates a session key, encrypts it for A's ephemeral keys and sends it to A.
A deletes the ephemeral key-pair after decrypting the session key.

However, if you mean the old draft protocol I linked in a previous answer, then, no. Unless I'm missing something, that protocol just encrypts a random secret using the long term keys. That does not provide forward secrecy.


Suppose $H(X) \rightarrow Y$ is collision resistant. Is $H$ also one-way?

No. Consider $H:X \to Y$ where $X = Y$ and the function $H(x) = x$. The function is collision resistant, but not one-way.


using elliptic curve point multiplication as a key stretching method

If I understand correctly is to hash your password $pw$ into a point using either $P=Pad(pw)\cdot P_0$ or $P=MD5(pw)\cdot P_0$ and then use $P$ for cryptographic purpose. The exact security of this proposal depends on what you want to do with $P$ exactly. But in some case, this is not secure. Typically, this mechanism is not a good way to hash a password (even if you add salt by varying $P_0$).

Indeed, in this application, you would know $P$ and $P_0$ and recovering the password $pw$ could be done using a discrete logarithm computation. Since $pw$ is generally quite short, $Pad(pw)$ belongs to a short interval of length $N$ (where $N$ is the number of possible padded passwords). In this case, using Pollard's lambda (i.e. The kangaroo method) allows to compute the discrete logarithm at a cost of $\sqrt{N}$. With $MD5$, $N$ is $2^{128}$ which would give a cost of $2^{64}$ to compute the logarithm, probably not enough.

On the other hand, if your application keeps $P$ secret, this is probably not going to apply. So could you tell more about the exact use of $P$ ?


hash function for elliptic curve co-ordinates

Let $k$ denote the bit-size of $p$.  Let also a hash function $H \colon \{0,1\}^{2k} \to \{0,1\}^\ell$.  We define the hash value of a point $P = (x,y)$ on an elliptic curve over $\mathbb{F}_p$ as
$$h \colon E_p(a,b) \to \mathbb{Z}, (x,y) \mapsto H(x + 2^k y)$$

One-wayness follows from hash function $H$ (for example SHA-3).

Note. There is a slight abuse of notation above, integer $x+2^ky$ should be seen as a binary string when applying hash function $H$; and the output (namely, $H(x + 2^k y)$) should be regarded as an integer.  This is done by the canonical representation: a $t$-bit integer $a \in \mathbb{Z}$ can uniquely be represented as $a = \sum_{i=0}^{t-1} a_i 2^i$ with $a_i \in \{0,1\}$, which in turn can be seen as the $t$-bit binary string $a_{t-1}a_{t-2}\ldots a_0$, and conversely.


How can I solve the discrete logarithm modulo 2q+1 if I can solve it in the subgroup of order q?

Ok, lets try again from scratch.  First, some group theory definitions:

A group is a set of elements and an operation $\times$ which satisfies a specific set of properties (closure, associativity, an identity element, inverses)
A subgroup is a subset of elements of a group which, along with the group operation from the main group, satisfies those same set of properties (closure, associativity, an identity element, inverses).  Note that the subgroup uses the exact same group operation $\times$, except that it restricts the operands to the subset.

For a finite group $G$, a subset of elements $H$ is a subgroup iff the subgroup is closed; that is, if you take any two elements $h_1, h_2$, then $h_1 \times h_2$ is also an element of $H$.

Now, $\mathbb Z^∗_p$ is a group with $p-1$ elements; the operation $a \times b$ is defined to be $ab \bmod p$; this satisfies all the group properties.

Now, consider only those elements $x$ of $\mathbb Z^∗_p$ that can be represented as $x = y^2 \mod p$ for some value of $y$ (or, in other words, that quadratic equation has at least one solution for $y$).  This turns out to be closed; that is, if we have two such elements $a = c^2$ and $b = d^2$, then $a \times b = ab = c^2d^2 = (cd)^2$ is also within this subset, and so these elements make up a subgroup.  It turns out that this subgroup has $(p-1)/2 = q$ elements (and is the only subgroup of that size), and hence is the "subgroup of order q" of the question.

With that background in place, the question under discussion is: suppose we had an oracle that could, given values $s$ and $t$ that were point a part of this subgroup (that is, there are some values $u$ and $v$ such that $s = u^2$, $t = v^2$) it could give us the value $x$ such that $t = s^x \bmod p$ (note: this is $\bmod p$, not $\bmod q$, because the subgroup shares the same operator with the main group).  Now, with such an oracle, how can we solve the DLP in the full group, that is, given $u$ and $v$, either of which may or may not be a member of the subgroup, how can we solve $v = u^x \bmod p$?

The first thing to note is if we define $s = u^2$ and $t = v^2$, both $s$ and $t$ are members of this subgroup.  Hence, we can use the oracle to find $y$ with $t = s^y \bmod p$.  Replacing the definitions for $s$ and $t$, we get $v^2 = u^{2y} \bmod p$.  Now, if there is a solution $v = u^x \bmod p$, we know that $v^2 = u^{2x \mod p-1}$ (Fermat's Little Theorem), we know that either $2y = 2x \bmod p-1$, and since $p-1$ is even, either $y = x$ or $y + (p-1)/2 = x$


Attacks from releasing decrypted CCM payload before verifying tag

Is this recommendation given because of user temptation to use unverified data without checking the MAC?

Yes. Note the word "released" instead of "stored".

  Or are there deeper ramifications?

That should not be possible; CCM uses CBC-MAC with known length and CTR mode encryption. There are - to my knowledge - no known plaintext attacks possible on these algorithms (given that the underlying block cipher is secure, of course).


Uniform vs discrete Gaussian sampling in Ring learning with errors

The TL;DR:

From a theoretic point of view, Gaussians are the better choice, both for the easiness of the security proof and its optimality in terms of tightness;
In practice, most of the time you can replace Gaussians by other distributions without too much trouble.

Theory

First, let me elaborate on a few reasons why Gaussians are better in theory:

When you use an error distribution in LBC, your distribution impacts the scheme in two conflicting ways:

Correctness: if the standard deviation of the error distribution is too large, then the correctness of the scheme is not ensured anymore. For example, in the key exchange in your Wikipedia link, if we set the error distribution to be uniform over R_q then the two parties effectively send each other random noise and thus it is impossible for them to agree on a common key with this protocol.
Entropy: the entropy of random distributions often play an important role in proving the security of a scheme. This is of course not restricted to lattice-based schemes, but since they are the topic at hand we can for example consider the leftover hash lemma (see this SE post: Relation between decisional SIS and leftover hash lemma in lattices). The SE post considers the error distribution to be over $ \{0,1\}^m$, you can use other distributions as well, but you need them to have sufficient entropy.

So you are faced with two somewhat conflicting conditions: you need a small standard deviation to ensure correctness, but you require sufficient entropy for the security proof to go through. As it turns out, for a fixed mean and standard deviation, the entropy is maximized for Gaussians. Which is why they look like the best compromise between these conditions.
While it is not exactly easy to work with Gaussians, they have a few "magical" properties which are handy when doing security proofs: for example, the sum of two Gaussians is a Gaussian. We can't say the same for uniform distributions (of restricted support).

Practice

Generating Gaussian distributions in a fast and secure (against side-channel attacks) way has proven to be difficult, and some methods for doing so have been subjected to devastating side-channel attacks. In addition it can be tedious, so many schemes (but not all) have tried to ditch full-fledged Gaussians without compromising security. For example:

Approximated Gaussians (using a table and 16 bits of randomness per coefficient sampled) have been considered. See FrodoKEM.
A popular choice is to rely on centered binomial distributions: they "look like Gaussians", but they can be sampled efficiently and securely (a binomial distribution is a sum of uniform samples in [0,1]). See NewHope and Kyber.
I have no knowledge of the uniform distribution being used in key exchange, but it is popular in Fiat-Shamir signature schemes which use variants of LWE (see qTESLA, Dilithium).

Funnily, you can even ditch the error distribution entirely and use truncation instead; of course now you no longer rely on the LWE hypothesis but on LWR (Learning with Rounding). This is what Saber does.


Best way, how to convert 32-byte Keccak hashes to positive numbers up to maximum?

Your "32-byte Keccak hash" doesn't look like a canonical, binary Keccak output, but rather appears to be encoded with some Base64 variant—to me it appears to be the MIME version.  Your comments on the matter confuse me whether that is the case or not; you should check your language or library's documentation.

If it's Base64 then it appears to be encoding a 18 bytes of raw binary output, which is 144 bits.  This is a unusual output size.  I would double check how your software is generating that output, and verify that all of that Base64 string really reflects a 144-bit Keccak output, and that there aren't some constant bytes being prefixed or suffixed to it.  Again, your description and comments are not helpful in this regard.

Taking the modulo is fine in practice if you do it over a large enough input set.
 Appendix B of NIST SP 800-185 contains a recommendation that uses modulo to convert the output of an extendable output or variable length hash function into a near-uniform natural number $0 ≤ n < R$ for arbitrary $R$.  The trick is that they make sure to do it over a hash output that is at least 128 bits longer than the number of bits needed to encode values in the output range:

Compute $k = \lceil\log_2(R)\rceil + 128$, where $\lceil\log_2(R)\rceil$ is the number of whole bits needed to encode $R$ distinct values.  For $R = 500$, this is $k = 9 + 128 = 137$.
Hash your input to an output $Z$ with length of at least $k$ bits.  Since your outputs are at least 144 bits, they meet this requirement.
Convert $Z$ to some "bigint" data type (arbitrary precision integers, check library support in your language; e.g., in Java it's BigInteger).  The bits_to_integer algorithm they detail in the document just parses $Z$ as a binary numeral with least significant bits first, although that later detail is not critical (e.g., Java BigInteger parses them in the opposite order, and that's just fine).
Take $N = \mathit{bits\_to\_integer}(Z) \mod R$ as your result.

The trick that allows them to use modulo is that they're willing to accept a biased distribution if they can guarantee the bias is astronomically small.  That's why they insist on taking a hash output 128 bits longer than the number of bits needed to encode $R$.  Suppose we used $R = 500$ but $k = 9$ (instead of the recommended $k = 137$).  The problem here is that since $2^k = 2^9 = 512$, when you take the modulo, 488 of the values have a probability of $1/512$ but 12 of them have a probability of $2/512$—they're twice as likely as the others.

Now suppose we take $k = 10$ instead, so $2^k = 1,024$.  Now when you take modulo 500, there are 476 values in the range have a probability of $2/1,024$ but 24 of them have probability of $3/1,024$—they're only 50% more likely than the rest.  For $k = 11$, $2^k = 2,048$ so you get 452 values with probability $4/2,048$ and 48 with $5/2,048$ (only 25% more likely), and so on.  By the time you get to $k = 137$ the bias is negligible; footnote 12 of the appendix gives:

$$
|\mathrm{Prob}(N=t) - 1/R| ≤ 2^{-w}
$$

...where $w ≥ \lceil\log_2(R)\rceil + 128$.


Is XTS basically the cheapest form of (secure) double-encryption?

So is there any way to break XTS or a double application thereof in less time and/or space than expected?
The expected time for standard XTS is time $2^{512}$ for 256-bit AES and $2^{513}$ time and $2^{512}$ space for double encryption.

Yes, there are better attacks than that.
With XTS a single sector is encrypted with a single $E_{K_2}(n)$ value, so the attacker can treat it as constant. It is only 128 bits, so a brute force attack can find both it and the AES key $K_1$ in about $2^{384}$ time. Once the attacker knows $K_1$, they can separately, given multiple sectors, attack the key $K_2$ in negligible time compared to the first step.
A meet-in-the-middle attack applies on double XTS as normal, in about $2^{385}$ time and $2^{384}$ space.
Note that with AES-128 the above would not be the case, since $K_1$ is the same size as the block, so a brute force takes $2^{256}$ time regardless of whether you are looking for the key or the encryption of the sector index.
There are of course other weaknesses that have to do with the fact that it is deterministic and lacks authentication. You can look at it as a sector sized cipher in ECB mode, if the attacker can see multiple ciphertexts for the same sectors. Any random string is a valid ciphertext, due to the absence of authentication or even padding.
XTS should not be used as general purpose encryption when IVs and authentication can be used.


Which ECB ciphertext stealing scheme is this?

This may sound crazy and absurd, but it seems that this scheme is simply broken:

on encryption, the last block is somehow padded (the exact method is not really relevant, but perhaps the trailing bytes of penultimate plaintext block are copied) and encrypted, then finally ciphertext is trimmed to match plaintext size;
on decryption, the same buffer is reused for each block, so the last ciphertext block is naturally padded with the trailing bytes of penultimate ciphertext block, then decrypted, and finally plaintext is trimmed to match ciphertext size.

Obviously, such an “encryption” irreversibly corrupts the last block, resulting in garbage being output on decryption. However, application software appears to ignore bad data silently, discarding the last record, absence of which is not evident to user, unless he specifically looks for it.

Well, I am not totally sure about this, as I only analyzed (OllyDbg to the rescue!) the decryption stage and header parsing, while object records are parsed on later stages of a quite-high-level processing, but it looks improbable to me that those high-level routines could perform a custom non-trivial restoration of the last block, — the more so that the last record appears to be missing, unless plaintext is guessed by hand (guessing is possible due to the highly predictable nature of plaintext, especially in the last block). However, if I am terribly mistaken, and such a scheme with properties specified in question is theoretically feasible, it would be interesting to know about it.


Definition of support in the context of an encryption scheme and usage of P = NP assumption in lemma 9.2 (Arora, Barak)

If you read the statements carefully, you see that $E_{U_n}(0^m)$ does not denote the encryption of $0^m$ with a specific key. It is function applied to a probability distribution - so $y$ is actually a probability distribution itself.

And this means, the word support fits to your understanding: It is the minimal set in the codomain (seeing $E$ as a function), where the probability is not 0 for any input from $U_n$ (side-note: the term closed doesn't really do anything for discrete or finite sets) - it is precisely the image of $E$ for this specific key length.

Another way to see this: The set $S$ is the image of the encryption function - for the specific parameters $m,n$.

Regarding this statement:

  Note that $y \in S$ if and only if $y = E_k(0^m)$; hence if
  $\boldsymbol{\mathbf{P}} = \boldsymbol{\mathbf{NP}}$
  then membership in $S$ can be efficiently verified.

This sentence might be missing something: It should state for claraification, that this is true for some key $k$ taken from $U_n$.

Regarding your 2nd question: For any $NP$ problem, verifying a witness if polynomial. But given some value in the codomain of $E$, you can't decide if it belongs to $S$ or not. However, if $P=NP$ you can find a witness in polynomial time. If for some potential witness exists, it is in $S$, and if no witness exists, it is not in $S$.


What authentication techniques can be used by QKD Systems?

The standard answer in the research literature is to use information-theoretically secure message authentication codes, typically universal hashing (aka Carter-Wegman authenticators).  Of course, you could use computationally-secure message authentication codes, like CMAC or HMAC, if you wanted, though that would partly defeat one of the reasons for using QKD.

That said, in practice QKD is a bit silly.  QKD solves a problem that most people don't have, so it is basically a fancy useless toy (albeit a very expensive one).  If you're considering using QKD in some practical deployment, my advice is: skip the QKD, and just use a TLS or IPSec VPN.  There, I saved you $50,000; don't spend it all in one place!


Why are the right halves kept unchanged in Feistel networks?

This structure allow us to make the process invertible. A Feistel structure creates a pseudo random permutation from a pseudo random function.
We want someone with the key to be able to calculate it in reverse and get the plain text from the cipher text.

Also recall that the after two rounds both sides get scrambled and after many rounds they are thoroughly scrambled to make deciphering without the secret key rather difficult. DES is no longer considered secure but the Feistel structure is still used in other block ciphers.


Difference in the Powers of Simulator and Environment in Universal Composability

In the real world we do have adversary and environment. The environment interacts with the protocol (real function) and the adversary. The parties are part of the environment. The real function leaks information to the environment/adversary
However, in the ideal world there is no such leakage. Therefore, in order to prevent the environment from distinguishing between these two worlds we need a simulator to create these leakage by getting some information from the ideal world. Here, the simulator is acting like the adversary for the real world. The environment thus is able to interact only with the ideal functionality and the simulator where the simulator is the adversary for the ideal world


The security proof for Key Policy Attribute Based Encryption

Because the simulator picked   $\gamma$ to generate $g^\gamma$.  He acts as an ABE authority for an attacker who breaks the Selective Set Model security game so he can use the attacker to solve the   Decisional Bilinear Diffie-Hellman problem .

As a result of being  the ABE authority, the simulator  knows  the master secrets and all other secrets created by the ABE authority. Remember, that for normal ABE, the authority knows everything, including user's private keys (attributes).

  Proof: Suppose there exists a polynomial-time adversary A, that can attack our scheme
  in the Selective-Set model with advantage $\epsilon$. We build a simulator B that can play the Decisional BDH game with advantage $\frac{\epsilon}{2}$. The simulation proceeds as follows:

  We first let the challenger set the groups G1 and G2 with an efcient bilinear map, e
  and generator g. The challenger flips a fair binary coin $\mu$, outside of B's view. If $\mu$ = 0,
  the challenger sets $(A; B; C; Z) = (g^a, g^b, g^c, e(g, g)^{abc} )$ otherwise it sets
  $(A; B, C,Z) =
(g^a, g^b,g^c, e(g, g)^z)$
   for random $a, b, c, z$. We assume the universe, $U$ is defined.

The simulator, then, gets to set up an ABE system so he can use the attacker

  The simulator B runs A. A chooses the set of attributes $\gamma$ it wishes to be challenged upon

$\gamma$ has nothing to do with the DBLDH assumption.


Passwords with same SALT. What does this mean?

A constant salt (or not using any salt) allows to do the same brute-force or dictionary attack on many passwords at once, instead of only at one at the same time. So you'll get an earlier "first match", and more matches at all for the same amount of work.

If the attacker wants a specific user's password, it is not faster at all (other than allowing precomputation of a hash→password table). Though if this attacked user has the same password with another user, this shows up, and a social (i.e. non-cryptographic) attack on this other user might be doable.


I don't really know so I'll tell you my best guess: One of the design goals was "free point validation". To do this, we want to make sure that no matter what $x$-value in $F_p$ we're sent, it is a valid point on the curve.
If $x\in F_p$, then to make an elliptic curve point we need $y$ such that $y^2=x^3+488862x^2+x$. But we have no reason to expect that $x^3+488862x^2+x$ will be a quadratic residue, so in general we will need to define $y$ over $F_{p^2}$. Thus, if I send you any value $x$ in $F_p$ and tell you it's a point on the curve, you know that there is some $y\in F_{p^2}$ such that $(x,y)\in E(F_{p^2})$, but you have no guarantee that $y\in F_p$.
The key exchange uses $x$-only arithmetic, so the key exchange will never need to use the extension field in any computations. Theorem 2.1 tells us that all multiples of a point with an $x$-value in $F_p$ will also have $x$-values in $F_p$, which proves correctness of the $x$-only arithmetic, more or less. So I think the case of $Q\in E(F_{p^2})$ but $Q\notin E(F_p)$ is used, but only via an implicitly-defined $y$-value.


Any theory about period length for AES applied to itself?

Since AES under any fixed key is a permutation, we necessarily have $j = 0$ and $i = l$—iterating a permutation enough times will always return you to the starting point.

From Harris 1960 (paywall-free), if we model AES as a uniform random permutation, every period length $l$ has equal probability $1/n$ (Eq. 5.2) for any particular starting point, where $n = 2^{128}$ is the size of the domain, so the expected cycle length is $\sum_{i=1}^n i/n = (n + 1)/2 \approx 2^{127}$.

(Any substantial deviation from this would imply an attack on AES.)


Collision probability of MD5 over different attacks

MD5 has a collision probability of $1 / 2^{64}$ under the Birthday Paradox.  Does this apply to any input given to MD5?

As explained in the other answer, $2^{64}$ is the birthday bound of messages until probable collision, not a collision probability. For two random messages you'd expect a $1/2^{128}$ probability of a collision with a 128-bit hash.

However, MD5 is broken with regard to collision resistance, so for two (or any number of) attacker controlled inputs you can't put a bound on it, they can find a colliding pair easily. (In fact, they can produce any number of messages that all collide, unless there are e.g. restrictions on message length.)

  Also, is the output of MD5 uniformly distributed to the randomized input? (If, please provide references.)

This translates to "is MD5 PRF?", which as far as we know is the case. For a reference to the fact that we don't know how to distinguish it from PRF you can use e.g. RFC 6151, which uses that to justify why getting rid of HMAC-MD5 "may not be urgent".


It's far from a full proof, but if you use the sketch from Boaz Barak's lecture notes, together with the full proof of the full scheme from the Cramer-Shoup paper, you should be able to work it out.


No, it is not equally secure.  Consider an instantiation where $E$ is instantiated with AES, and where the message is always 128 bits long.  Can you find an attack on this particular version of the scheme?

This smells like homework (I'm guessing?), so to avoid ruining the problem and give you a chance to learn from it, I'm just going to leave it at that.  I think you'll find the process of working out the rest of the details to be instructive: for instance, it might help you understand IND-CPA security a bit better and how a scheme can fail to meet this security definition.


Is it possible to 'fake' time for TOTP? (Time-based One-time Password)

The algorithm produces a password based on the value of the time that is input as an argument.  That value does not have to be the current time.  For the purposes for which TOTPs are generally used, there is no value in producing the password for a time other than the current time step - it won't be recognized by the validator.


Proof that any key exchange protocol is vulnerable to MitM attacks in the absence of shared information or trust

It has nothing to do with information theoretic. You just need to construct an adversary and argue that it works. In this case, the adversary is simple. Let $A$ and $B$ be parties with no secret information. An adversary $C$ playing man-in-the-middle interacts with $A$ pretending to be $B$, and interacts with $B$ pretending to be $A$. At the end, $C$ establishes a separate channel with $A$ and with $B$. Then, any message sent by is decrypted by $C$ (using the key generated with $A$) and then re-encrypted (using the key generated with $B$) and sent to $B$. Likewise, in the other direction.

Since there is no initial secret, $A$ and $B$ see exactly the same thing as they would see in a key exchange that is not under attack. However, $C$ learns everything communicated.

The difference between this and a full proof is minimal.


Can you break a multi language code using Frequency analysis?

Yes, we can almost certainly break this, given enough ciphertext.

One approach would be to use a dictionary and use word patterns.  For instance, if the ciphertext word is qddxfozogf, then the plaintext word was probably ammunition.  Notice how the 2nd and 3rd letters are the same; and the 5th and 10th letters, and the 6th and 8th letters?  The word ammunition is essentially the only word that has this special pattern.  One could expect that some fraction of words will be essentially unique, in their pattern of repetition.  With enough ciphertext, you'll be able to uniquely recover one or more of the words, and then the rest of the cipher will be easy to break.

Frequency analysis will also almost certainly be possible.  For instance, the letter q occurs with frequency 0.1% in English, 0.02% in German, and 0.9% in Spanish.  In contrast, the letter e occurs with frequency 14.7%, 17.4%, and 13.7% in English, German, and Spanish, respectively.  Therefore, if you choose uniformly at random between English, German, and Spanish, the letter q will occur in the plaintext with frequency about 0.3%, while the letter e will occur with frequency about 15.3%.  Notice how e is still much more common than q?  This indicates that frequency analysis remains possible.  (Wikipedia has data on the frequency statistics of different languages.)

Digraph analysis (the frequency of pairs of letters, like the pair th or qu) will also almost certainly be possible.

Finally, there are more sophisticated methods for cryptanalysis of simple substitution ciphers, such as hill-climbing.  These methods will almost certainly be effective at ciphertext-only cryptnanalysis.

And the cipher will completely fall apart in the presence of known plaintext (let alone chosen ciphertext).

TL;DR: Your proposal is highly insecure.  Don't use it.


If the input text and output text in DES are the same what is the value of the key?

I'm not aware of such DES key which $E_k(M)=M$

DES has 4 Weak Keys which allows $E_k(E_k(M))=M$

i.e. if you encrypt the encrypted message, you get as result the original message.

  page 159-160

Keys before parities drop (64 bits) | Actual key (56 bits)
0101 0101 0101 0101                   0000000 0000000
1F1F 1F1F 0E0E 0E0E                   0000000 FFFFFFF
E0E0 E0E0 F1F1 F1F1                   FFFFFFF 0000000
FEFE FEFE FEFE FEFE                   FFFFFFF FFFFFFF

  Example 6.8 Let us try the first weak key in Table 6.18 to encrypt a
  block two times. After two encryptions with the same key the original
  plaintext block is created. Note that we have used the encryption
  algorithm two times, not one encryption followed by another
  decryption.

Key: 0x0101010101010101
Plaintext: 0x1234567887654321 Ciphertext: 0x814FE938589154F7

Key: 0x0101010101010101
Plaintext: 0x814FE938589154F7 Ciphertext: 0x1234567887654321


Key rotation (or other measures) for PASETO v2 "local"

Key rotation is important.

Besides data breaches, unintentional key disclosure happens. For example by committing an unintended file to a public GitHub repository. Also, people having access to a key today can take a copy of that key when they leave the company.

In case of PASETO, brute-forcing the key is not a concern. The key space is ginormous (2^256), so this is infeasible, no matter how much data is collected.

If you control all the applications using that key, and you probably do, key rotation should also be fairly easy to implement.


Elliptic Curve ElGamal and DSA - smooth group order and element of large prime order

For the curves used in cryptography today, the order of the group of points is typically 256 bits, sometimes 512. Such numbers are within the range of current factoring algorithms (indeed, this is why you don't use 512-bit RSA keys), and so typically the order of the group can be factored and it is easy to see whether it has a large prime factor.

Moreover, standard curves such as the NIST curves or Curve25519 are chosen so that the order of the group of points is either prime (as in the NIST curves) or is a large prime multiplied by a small cofactor ($8$ in the case of Curve25519), so if you use a standard curve you know there is a subgroup of large prime order for you to work in. (It is important that you work in a group of prime order to prevent other types of attacks.)


Computing PGP ed25519 and curve25519 keygrips?

Keygrips are not part of PGP at all, they're just an implementation detail of GnuPG's key storage architecture specifically (which uses a common key store for PGP, S/MIME, and SSH).

As you saw, GnuPG uses libgcrypt for cryptographic operations, and the keygrip calculation can be found in cipher/pubkey.c where it's just a SHA-1 hash of the public key's parameters.


How to properly cypher 16 bytes message containing a CRC checksum?

Is this cryptographic standard relevant for this kind of task?

Yes to a degree, but with what's in the description (and assuming the CRC is checked after AES-CBC decryption)

There is no protection against replay of earlier captured messages. The usual options to protect from replay are a two-way protocol where the receiver generates a nounce made part of the message carrying sensor data, or/and a sequence counter maintained by the sender (but only the former solution insures freshness).
This is symmetric crypto, hence the sender is bound to contain a secret that allows decryption, and the receiver is bound to contain a secret that allows forgery of information. Both issues can be fixed by asymmetric crypto.
CRC-then-encrypt in general does not give integrity protection, and if encryption was with a stream cipher or the common AES-CTR, it would be trivial to alter the data in real time. The use of CBC encryption happens to save the day (because AES encryption of one block is not malleable), but that's a lucky choice more than by design. And if the message was larger than 12+4 bytes and thus did not fit a single AES block, I would not bet the house that there is no cryptanalytic attack on the integrity protection.
The integrity protection is only 32-bit. An adversary submitting 1000 random ciphertexts per second to each of 1000 receiving systems will sneak one thru the decryption and CRC check more often than once in 1h 15' ($2^{32}/10^6$ s) on average.

The academic solution to 3 and 4 is authenticated encryption, designed for both confidentiality and integrity. One of the most well-known is AES-GCM. It is improved in AES-GCM-SIV.

  How do I chose the key size?

There are three for AES: 128, 192 or 256-bit. They are safe/fastest, safer/faster, or safest/fast. In the context, AES-128 is technically sufficient, because the real threat is that the key somewhat leaks (gets extracted from either the receiver or sensor). AES-256 looks better on the spec sheet, likely is fast enough, and I do not see that it can make key extraction easier; so why not?

  How do I chose the Block size?

You did: AES can only be used with 16-byte block.

With AES-CBC (if kept against my recommendation of authenticated encryption) one choice you have is the padding mode, and the best is "no padding", since any padding will cause an extra 16 bytes of ciphertext.

Other, much harder things to determine for a real system are:

how the Initialisation Vector for encryption is generated;
how the keys are drawn;
how they are injected in the devices that need them;
how key leak is made unlikely;
how keys are rotated (changed, periodically or to recover from a suspected leak).

  Does CRC32 stored in a message reduce the strength of the cryptography as it introduces a relationship among bits in the message?

No, unless there was an exploitable weakness of AES iself, which can be discounted. Modern ciphers are designed to safely encrypt known plaintext, and thus are safe for redundant plaintext.


The important thing to note here is that $\mathsf{D}(k,0)=0$ does not necessarily imply that $\mathsf{E}(k,0)=0$. That is the reason why your attack does not work in general.

To illustrate, let $(\mathsf{E},\mathsf{D})$ be a CCA secure encryption scheme.
We then construct a new encryption scheme $(\mathsf{E'},\mathsf{D'})$ as follows:
$$\mathsf{E'}(k,m) = 1\Vert \mathsf{E}(k,m)$$ and
$$\mathsf{D'}(k,b\Vert c) = \left\{\begin{array}{ll} 0& \text{if } b = 0\\ \mathsf{D}(k,c)& \text{if } b = 1\end{array}\right.$$

It is trivial to show via reduction that $(\mathsf{E'},\mathsf{D'})$ inherits the CCA security from $(\mathsf{E},\mathsf{D})$, but still it has the property that $\mathsf{D'}(k,0)=0$.

As you can see, your attack does not work, because $0$ is never encrypted to $0$ by the challenger.


How to effectively apply combination of Block and Stream Cipher?

What you can do is convert the block cipher into a stream cipher. You can do this by using it as primitive for a stream cipher mode of encryption such as CTR. Then you can use the resulting key streams of cipher A and B and XOR them together with the plaintext.

In principle you can also encrypt it using a block cipher mode of encryption or stream cipher in any order. This should not leave loopholes.

Compression or no compression is a tricky question. I'd say that no compression is better. As long as your plaintext doesn't leak information through the size of the plaintext, you're OK. The amount of compression is dependent on the contents and size of the plaintext.

The problem with this is that the compression factor may differ for slightly different plaintext. This means that it will become next to impossible to not leak information.

It's good if the keys are not related to each other. For best security it would also be wise to make sure that the algorithms are not related either.

The use of two ciphers to achieve confidentiality is an operation with questionable returns. Often it is more useful to e.g. use public key cryptography (in a hybrid scheme, so that the private key is not required during encryption) and/or authenticated ciphers.


Workaround to implementing Forward Secrecy

This only works if you are absolutely certain that you're properly erasing the old private keys. This is harder than it seems; you have to be sure that you're leaving no traces anywhere, including on backup media or scattered around your hard drive. With proper forward secrecy methods, the keys never leave RAM, which makes erasing them securely much, much easier. Furthermore, this only happens after a week or a month or whatever; if you erase the private certificate monthly, then an attacker who acquires the certificate at the very end of the month (before you erase it) can decrypt the whole months' worth of messages.

There is very little reason to do this. ECDHE is not slow; while it's a bit slower and more computationally intensive than RSA, that difference shrinks rapidly as security increases (at 2048-bit RSA keys, there's a very small difference). Furthermore, ECDHE does not have anywhere near as many implementation pitfalls as securely erasing a private certificate weekly, and doesn't leave the week- or month-long interval for private key theft. Just use ECDHE.


Ciphertext manipulation for ciphers with intermediate tags

As the specification of Keyak v2 explains:

  To produce a tag that depends on the full message and not only on the message bits that have been injected in a single duplex instance, Motorist
  performs some dedicated processing at the end of each message called a knot. It extracts
  chaining values from each duplex instance, concatenates them, and injects them into all
  duplex instances. This makes the state of all duplex instances depend on the full sequence
  of messages. Then it extracts a tag from a single duplex object.

right within chapter 1 (emphasis mine). Note that Motorist is the underlying construction of Keyak 2.


First 16 characters replaced after decrypting AES encrypted string

Most likely you are using CBC mode, and most likely you did not supply the correct IV during the decryption process, resulting in improper decryption of the first block.

The IV should be supplied as part of the encryption process, and be different for every message, and be included with the ciphertext so that it is available for decryption. More than likely at least one of those did not occur.


Differential addition on Montgomery curve

Differential point addition means that to compute $x_{P+Q}$ you need not only $x_P$ and $x_Q$, but also $x_{P-Q}$.

There are a lot of possible formulas, you can find most of them here: https://www.hyperelliptic.org/EFD/g1p/auto-montgom-xz.html


Question about proof of pseudo-random random generators being one way functions

It's analyzed in this way because it is tricky to correctly conclude much more than what's written here.  The issue is that a uniformly random string $w$ in the image of $G$ is not necessarily distributed like $G(x)$ for a uniformly random $x$. We know that $\mathcal{A}(y)$ succeeds with $\varepsilon$ probability for a random input $y=G(x)$ of the latter form, but that doesn't tell us much about how it behaves in the former case.

More precisely, conditioned on $w$ being in the image of $G$, it is uniformly random in that image.  This does not necessarily imply that $\mathcal{A}(w)$ ouputs an element of the preimage set $G^{-1}(w) = \{x : G(x)=w\}$ with probability $\varepsilon$.  For example, $G$ could be highly "irregular," meaning that some preimage sets are much larger than others.  But $\mathcal{A}$ might only successfully invert on, say, those $y$ that have very large preimage sets.  This would give it good inverting probability on $y=G(x)$ for uniformly random $x$, but its probability of inverting on a uniform $w$ in the image of $G$ would be much less than $\varepsilon$.


Can we parallelize the Feistel Networks?

The standard way to make best advantage of parallelism is to use a parallelizable mode of operation.  For instance, counter mode (CTR mode) is highly parallelizable.  Parallelism at the level of the mode of operation is typically more effective and easier to implement than parallelism inside the block cipher.

The Feistel network approach to block ciphers is inherently sequential, so not a good candidate for parallelization.  If you wanted to do fine-grained parallelism inside the block cipher, you'd probably design your block cipher differently (e.g., a la Serpent and bitslice ciphers) -- but doing parallelism at the level of the mode of operation is typically even more effective.


What happened to Poly1305AES? Is it obsolete?

Poly1305 is a universal hash function. The output of that function cannot be used safely without being encrypted.

In order to encrypt it, any cipher can be used. AES was used as an example in the paper, but the very same paper mentioned:

  Users can switch from Poly1305-AES to Poly1305-AnotherFunction, with an identical security guarantee. All the efforts invested in the non-AES part of Poly1305-AES can be reused; the non-AES part of Poly1305-AES cannot be broken.

In fact, even Bernstein didn’t use this function with AES. The first real-world instantiation of Poly1305 was with Salsa20.

Poly1305 is widely used today, mainly with ChaCha20, a Salsa20 variant.

With AES, it never saw much real-world deployment, and Poly1305-AES has never been part of any standards.

GMAC is very similar to Poly1305, but can benefit from hardware acceleration on many platforms that also provide AES acceleration. This is probably the most commonly used construction today.

On constrained systems, constructions such as AES-CCM are better candidates as the AES core function can be used both for encryption and authentication instead of having to implement two completely different functions.

To recap, Poly1305-AES was just an example. That particular example was not used in practice, as standardized and widely deployed constructions with AES already existed. These were either more compact, or eventually got very efficient due to hardware support.

But Poly1305 is good, especially on hardware that lacks what is required to implement GMAC efficiently (carry less multiplication). So, it is used with ciphers that are also efficient without hardware support, not with AES.


Most encryption algorithm use a specific number of the same (or similar) group of operations. As example, AES consists of 4 different operations: SubBytes, ShiftRows, MixColumns and AddRoundKey. AES-128 (AES with a key of 128 bits) uses all this operations 10 times in 10 rounds. Well, not exactly. The last round doesn't have the MixColumns step. It would add nothing to the security which is why it's omitted.

If an attack has "broken 4 out of 8 rounds" it means that the same algorithm was broken if it would use only 4 instead of the normal 8 rounds. Using only 4 rounds instead of 10 in AES-128 is broken, even without special prequesits. Breaking a few rounds of a cipher is normal, because the secure properties of an algorithm have to slowly establish through the rounds. If 9 out of 10 rounds would be broken, that would be much more alarming. We can assume that the last round will be broken soon enough.

Now we have to mention one important thing: If an algorithm is broken it doesn't mean that someone can decrypt every message encrypted with this algorithm without the key. Nearly every attack on modern algorithms is not about this. There are different kinds of attacks: As example, a known-plaintext attack needs a special amount of plaintexts and corresponding ciphertexts to gain the key. Numbers of $2^{40} = 1\,099\,511\,627\,776$ are low, despite being something like 128 terabyte of encrypted data. A break with this small amount would be considered devastating for AES. For one special attack on AES-256 we still need ca. $2^{100}$ operations - too much in practice, despite being "broken" in the academic sense.


Security of encrypting many short values with AES in GCM mode

The only limitation that you really have to consider is that of nonce collisions. With 128-bit random nonces, you would expect collisions after about $2^{64}$ nonces due to the birthday bound.

Even if you stored all 30 fields of all 50 million rows thousands of times (you need a new nonce if a field is rewritten), you would still have a chance smaller than $2^{-32}$ of a collision. With your plan of using different keys for some fields you should be fine.

There are other limits on how much you can authenticate with GCM, but as long as you use the full-length authentication tag those limits are larger than the one above with short messages like you have. See section 7 of The Galois/Counter Mode of Operation (GCM) (pdf).

NIST SP 800-38D (pdf) says to only use a key for $2^{32}$ messages at most (Section 8.3) unless you are creating deterministic 96-bit nonces. It also gives even smaller limits if you wish to truncate the authentication tag (Appendix C).


Are attacks on AES more efficient now (due to the new paper published at CHES2016??)

Practically not, for two reasons:

the method described mostly speeds up AES computation with repeated use of the same key, rather than AES computation with repeated use of the same data, which is what a brute-force attacker does for key search, and what a side-channel attacker does to narrow a guess (there are other attacks, like detecting collisions in the CBC ciphertext, but a faster AES engine does not significantly help these).
even a speed up by a factor of 4 (more than claimed by the paper) would not qualitatively change the fact that AES key search, or other known AES attacks (excluding attacks on a particular implementation), are hopeless (when a single key is targeted, or when AES-192 or better is used); the technique in the paper reduces the security of AES-128 to 126 bits instead of 128, akin to reducing distance to notable nearby galaxies (excluding the Milky Way where we stand) to that of the Carina Dwarf instead of that to Andromeda.

Note: I have excluded side channel attacks against AES implementations using the technique described, but not use of the technique described to attack other implementations.


Single-block hash construction based on a block cipher with two fixed keys

This construction is well-known as XORP = "XOR of independent permutations". In your case the permutations are obtained by invoking a block cipher $E$ with different keys.
If $E$ is an ideal cipher, and $k_1, k_2$ are distinct (fixed, public) keys, then $E_{k_1}(\cdot)$ and $E_{k_2}(\cdot)$ are independent, ideal permutations. Ideal permutation means that everyone has oracle access to these permutations as well as their inverses.
The right question to ask here is:

If $\pi_1$ and $\pi_2$ are independent ideal permutations, is $\textsf{XORP}(x) = \pi_1(x) \oplus \pi_2(x)$ indifferentiable from a random oracle?

"Indifferentiable" means that $\textsf{XORP}$ looks like a random oracle, even to a distinguisher who has access to the underlying $\pi_1, \pi_2$ (and their inverses), which is the case here.
The answer to the question is yes, XORP is indifferentiable from a random oracle. See:

Srimanta Bhattacharya, Mridul Nandi: Full Indifferentiable Security of the Xor of Two or More Random Permutations Using the $\chi^2$ Method (Eurocrypt 2018)

Notably, XORP is secure beyond the birthday bound. If the permutations are on $n$-bit strings, then an adversary who makes $q$ oracle queries can distinguish XORP from a random oracle with probability at most $q/2^n$, instead of $q^2/2^n$.
In summary: $x \mapsto \textsf{AES}_{k_1}(x) \oplus \textsf{AES}_{k_2}(x)$ is a very strong one-way function, under the assumption that AES is an ideal cipher.
Aside: if $k_1$ and $k_2$ are independently random and private, then the question is whether $x \mapsto \textsf{PRP}_{k_1}(x) \oplus \textsf{PRP}_{k_2}(x)$ a pseudorandom function. This is much simpler since the distinguisher does not get direct access to the individual PRPs. Of course the answer here is also yes.


The compression of the eliptic curve point coordinates

In this case the 03 is not a sign of the compression format. It's a DER encoding of an ASN.1 BIT STRING, with a length of 39 hex (57 bytes). 00 means that all the bits in the remaining 56 bytes are used; this is rather common. 00 itself is not part of the encoded value.

Within this BIT STRING there is a value starting with 04 36. Here 04 is not an uncompressed point, but it is an ASN.1 OCTET STRING. Again, 36 is the length, in this case 54 bytes (the previous 57 bytes with an additional overhead of 00  04 36).

A BIT STRING is often used to be able to use any key or data format within it. The OCTET STRING is probably used to wrap the coordinate(s) within it. Because the BIT STRING doesn't indicate that there is an ASN.1 encoding within it (it contains a primitive value rather than a constructed value), decoding is a two step process. In this case the OCTET STRING is spurious, but it may be different for other structures that consist of a SEQUENCE of elements.

The 54 bytes of the value of the OCTET STRING are the minimum number of bytes to store a single 431-bit coordinate: $\big\lceil 431 / 8 \big\rceil = 54$. This could be the X coordinate that is the result of an ECDH calculation. If it was a point representing a public key you'd expect a compressed or uncompressed point, which would take one byte in addition to the 54 bytes given.


what are multi-primes and how are they different from semiprimes?

You got what a "semiprime" number is; it's a number which is the product of two primes.

When people talk about "multi-prime RSA", what they mean is something which is pretty much the standard RSA algorithm; however the modulus is the product of at least 3 prime numbers (as opposed to standard RSA, which has only 2 prime factors).

Why would anyone do this?  Well, for performance; using the CRT optimization, we can do the private operations (signature generation, public key decryption) somewhat faster than we can do with standard RSA.  And, it doesn't affect someone that has only the public key as well (they can't even tell if the key they've been given is standard RSA or multi-prime").

Why doesn't everyone do this?  Well, I'm not certain, but I can think of a few plausible reasons:

I believe this idea is patented.
If someone goes hog wild, and puts too many factors into the modulus, that will make the modulus easier to factor.  IIRC, having 3 or 4 factors is safe for common modulus sizes is safe; I know that having 10 is not.
Conservatism; we trust RSA as it was originally designed, we're not going to go to an unproven version for a modest performance gain.


Miller-Rabin has been known since at least 1980 (according to Wikipedia). Even though it's probabilistic, it's good enough. For example, openssl uses it$^\textrm{1}$. Chapter 4 of the handbook talks about various primality tests, which may gave you a better understanding of the authors' thoughts.

$^\textrm{1}$See the source code for bn_prime.c


RSA: If the least significant bits of the factors are leaked, what advantage is there in factoring N?

This question looked due to the Cold boot attack, by Halderman et. al. Normally researchers look at some random known bit known due to the decaying of the memory.

2009 Heninger et. al Reconstructing RSA Private Keys from Random Key Bits

if $\delta = .57$ fraction of the bits of $p$ and $q$ is randomly is given they can construct them.

The closest article is by Maira et. al.

2010 - Maitra Factoring RSA Modulus Using Prime Reconstruction from Random Known Bits, also a slide of one of the authors.

In Section 2 and 3, they look at LSB case. With theorem 1;

Theorem 1: Let $N = pq$, when $p, q$ are primes of same bit size. Let $S = \{0,\ldots, l_{N /4}\}$. Consider $U \subseteq S$ and $V = S \backslash U$. Assume that p[i]’s for $i \in U$ and $q[j]$’s for $j \in V$ are known. Then one can factor $N$ in $poly(\log N)$-time.

$l_N$ the bit size of $N$, i.e, $l_N = \lceil log_2 N\rceil$.


Understanding the Hidden Subgroup Problem specific to Integer Factorization

Let $\mathbb{Z}, +$ be the group integers, $\mathbb{Z}/n\mathbb{Z}, \times$ the multiplicative group of integers modulo $n$, and $\varphi(n)$ its order. Then $\varphi(n)\mathbb{Z}, +$, the additive group of multiples of $\varphi(n)$ is a subgroup of $\mathbb{Z}$. The function $f : \mathbb{Z} \rightarrow \mathbb{Z}/n\mathbb{Z} : x \mapsto a^x \mod n$ for fixed $a \in \mathbb{Z}/n\mathbb{Z}$ satisfies the description of the HSP oracle for the subgroup $H=\varphi(n)\mathbb{Z}$ of $\mathbb{Z}$ because

$\phantom{\Leftrightarrow} \forall \, x, y \in \mathbb{Z} \, . \, f(x) = f(y) \\
\Leftrightarrow x = y \mod \varphi(n) \\
\Leftrightarrow x = y + k\varphi(n) \quad \mathit{for \, some} \quad k \in \mathbb{Z} \\
\Leftrightarrow x = y + H$

Consequently, the formulation of the factorization problem is to find a generator of the group $\varphi(n)\mathbb{Z} \subset \mathbb{Z}$ given access to the function $f$ that computes exponentiation modulo $n$. Once you have this generator, $\varphi(n)$, computing the factorization of $n$ is easy using some straightforward (classical) number theory.


Proof that a modified public-key encryption scheme is not CCA secure

So let's go through the CCA(2) game and see where things fall apart, shall we?

Challenger: Generates keys.
Adversary: Calls the encryption or decryption oracles a polynomial amount of times. We don't need this here.
Adversary: Picks two messages, eg $m_0=0$ and $m_1=1$.
Challenger: Chooses a bit $b$ uniformly at random, ie $b\in\{0,1\}$
Challenger: Encrypts $m_b$ and sends the result to the adversary as $C$, the challenge ciphertext.
Adversay: Perform a polynomial amount of operations including encryption or decryption oracle calls, e.g. to decrypt $C$ with the last bit flipped.
Adversary: Output a guess $b'$ for the bit $b$, eg the result of the decryption query in the last step.
If $b=b'$ the adversary wins. If the probability  of this happening is not negligbly higher than $1/2$, the scheme is broken.

Do you see now how CCA security is broken using 1 query?


A pseudorandom generator is far more specific.

A pseudorandom number generator can just be statistical and/or produce an

endless stream of output and/or take extra entropy as input while it's running.

This RFC gives a way to implement a pseudorandom function.

In fact, if you hadn't specified that you wanted a PRG to implement a PRF, then

I would've just suggested $\;\;\; x \: \mapsto \: \operatorname{HMAC}\hspace{.02 in}(x\hspace{.02 in},\hspace{-0.03 in}0) \: || \hspace{.02 in} \operatorname{HMAC}\hspace{.02 in}(x\hspace{.02 in},\hspace{-0.04 in}1) \;\;\;$ as the PRG.


For each of the "MD" functions (MD4, MD5, SHA-1, SHA-256, SHA-512, and derivatives), one can view the compression function as a "tilted block cipher": the message block is used as key, and the function encrypts the current state.

More formally, if you look at MD5, then there is a block cipher $B$ that takes as inputs a 512-bit key and a 128-bit block. The Merkle-Damgård construction then uses a 128-bit running state $r$, initialised to a conventional initial value. The processing of message block $X$ consists in computed $B(X,r)+r$, which becomes the new value for $r$: the current state is encrypted, using the message block as key, and the encryption output is added (in the case of MD5, this is word-wise addition) to the previous state.

If you look at the block cipher details for MD4, MD5 and SHA-1, then you can see that it is a kind of generalised Feistel scheme. In a "normal" Feistel scheme, the input block is split into two halves, and one half is then combined (usually by XOR, but it also works with other reversible combinations like modular addition) with the other half; then the two halves are swapped. In MD5, the input block is split into four words; a function is computed from three words, result being combined with the fourth, and then the words are rotated. Successive SHA functions tend to add a few extra operations but don't change the general structure.

For all the classic MD functions, the inner block cipher was designed "from scratch", i.e. specifically for the hash function. However, in the case of SHA-1 of SHA-256, the block cipher was afterwards awarded a name of its own, SHACAL. I am not aware of any significant deployment of SHACAL as an encryption function.

Similarly, one might want to take an existing block cipher, and turn it into a hash function: this is what Whirlpool is about.

This block cipher / hash functions relationship is subtle, and, altogether, disappointing. Excellent performance of hash functions does not translate to fast encryption: while MD5 can crunch lots of data per second it does so by 512-bit blocks; the underlying block cipher, for the same amount of work, processes only 128 bits, so its bandwidth is going to be only 1/4th of that of MD5. Security is not that good either: most block ciphers are not very strong against related-key attacks because such attacks use an esoteric, impractical setup that does not apply to practical situations; however, when the block cipher is turned into a hash function with the Merkle-Damgård construction, the related-key attacks become collision attacks, and these are very practical. This is why Whirlpool uses a block cipher called W, derived from Rijndael (i.e. AES), but with a much strengthened key schedule: W is believed immune to related-key attacks, and this was done so to make Whirlpool immune to collision attacks.

You might want to investigate the design documents for Skein, a former SHA-3 candidate. Skein is built upon an internal block cipher (dubbed "Threefish"), but it uses it with another structure ("ARX") in which the block cipher is not "tilted", which avoids the trouble with related-key attacks, and allows a better performance mapping between hashing speed and encryption speed.