Why is it a bad idea to use a UTF-8 derived symmetric key?

The strength of a symmetric key is determined by the amount of entropy. In that sense your scheme would not increase or decrease the security by much. However, you would be specifying a higher key size than actually used. For instance your AES-256 bit key would have the same entropy as an AES-128 bit one. You'd use a slightly different key schedule and number of rounds as well of course.

Besides that you may run into problems when somebody decides to use a different encoding (hex encoding in UTF-8 is the same as just using ASCII though) or a byte order mark. It could also be possible to mix up uppercase and lowercase characters.

In the end you're only fooling yourself and possibly others if you'd use this kind of scheme. It is very bad practice. If you have to store the key as hexadecimals then pretty please with sugar on top, convert it back to the original form.

In general though you should never ever have to store a key in a string in the first place. Note that strings may be very hard to delete from memory. Instead store them in a key store such as PKCS#12 or preferably in a hardware device.


When all shares of a secret are given to adversary as a permuted matrix

Let us first consider the problem without involving Shamir secret-sharing
at all.  Suppose that $n = 140$ and that the secret $\sigma$ is a 140-byte Twitter message. The space is thus restricted considerably, from all possible $256$ byte values to the printable
characters permitted to be used in Twitter messages, and the distribution in this restricted space might also be nonuniform because of etaion shrdlu. The secret sharing
is trivial: each of the $140$ shareholders gets one byte, and the secret
is recovered only when all $140$ shares are assembled in the correct
order.

An adversary is given a large number composite number $N$ of bytes
(arranged into a matrix if the OP so desires, though I am not sure why
this imposes some structure on the data) including
the $140$ shares and the other $N-140$
entries filled in "at random". Can the
adversary recover the secret with large enough probability to be
a significant concern?  Well, the answer might depend on the
assumptions. If the $N-140$ "other" bytes are "filled in at random"
from the space of all $256$ bytes, then the adversary can simply
discard all bytes that are not part of the Twitter character set.
This reduces the workspace from $N$ bytes to
approximately $p(N-n) + n$ bytes where $p$ is the ratio of the size
of the Twitter character set
(80? 96?) to $256$. It might also be possible to make some educated
guesses and apply the known distribution of the message set to discount excessive numbers of letters x or q or z etc or punctuation marks, etc.  So, with no secret sharing, the extraneous bytes that
the adversary is handed should be chosen not at at random, but
roughly with the probabilities with which they occur in Twitter
messages.

Many of these concerns go away when Shamir secret sharing is used.
Now, the shares are of the same length as the secret, but
share $\sigma_i$ is the value of the polynomial
$$S(x) = \sigma + a_1 x + a_2x^2 + \cdots + a_{n-1}x^{n-1}$$
(where the $a_i$ are randomly chosen nonzero entries) at some
nonzero element $\alpha_i$ in the field.  Even if $\sigma$ is restricted,
these random polynomial coefficients ensure that the shares
$$S(\alpha_1), ~S(\alpha_2),~ S(\alpha_3),~ \ldots,~ S(\alpha_n)$$
essentially look like random choices. In fact, some of them might
even equal $0$.  Thus, if we fill the $N-n$ other entries with other
random choices (allowing $0$ as a choice too), the $N$ possible
shares handed to the adversary will conceal the true shares very well.
I don't have a formal proof for this, but I doubt that any statistical
test can distinguish the actual shares from the fakes with even a
minuscule chance of success.  Of course, one must ensure that $N$
is much larger than $n$ so that there are enough . I venture to suggest that $N = O(n^2)$ will be found to be more than adequate, and
perhaps even something like
$10n$ might work well enough.


How does tls 1.3 cope with man in the middle (in key exchange)

TLS 1.3 without PSK (i.e. the usual use-case of TLS) uses a certificate which verifies the authenticity of the service, just like all the other versions of TLS (and SSL). For most typical uses in web browsers, the server's certificate is signed by a certificate authority (CA). It doesn't matter what key exchange algorithm is used as long as it is strong (DH and ECDH are considered strong).

See also The New Illustrated TLS Connection: Every byte explained and reproduced for TLS 1.3.


Signature security proof in the Random Oracle model

This was discussed by Coron in 1.

You are actually asking why the random oracle can't just be some uncontrollable ideal random oracle.
In fact Bellare and Rogaway when introduced their Full Domain Hash scheme (FDH) in the seminal works 2,3 used this uncontrollable random oracle to analyze the security reduction for FDH.

The thing about using reductions to prove the security of, let's say a signature scheme, is that the reduction security depends greatly on the probability to break the underlying assumption, let's say the CDH assumption. So ideally, if the reduction enables to break CDH problem with probability 1 it means the signature scheme is pretty much secure as solving the CDH problem.

But what happens if this probability is much lower than 1?  Well, the signature scheme security becomes rather weak.

As Coron mentions in 1, allowing $\mathcal{A}$ to control the random oracle gives a tighter security bound on the FDH signature scheme than the one shown by Bellare and Rogaway.

The main thing about the tighter bound is that it does not depends on the number of queries requested by the forger, but rather only on the number of queries for signatures (which in practice is much lower than the number of hash queries such forger can do). A better bound enables one to use more efficient signature scheme.

To conclude, using a specific hash function does not say that this is an assumption of the model, it is merely a way to make the bound tighter.


Rationale of "r" AES key use in OTR version 3 AKE protocol?

The usage of the r key forces both parties to "fix" the public DH keys.

So Alice doesn't know Bob's public DH key before she's generating her own one.

And Bob can not make the choice of the public key dependant on Alice's choice and vice versa.

This forces both parties to be honest and to generate both public keys at random as there is no opportunity to force a specific derived key that may have some weak properties.


Why is H(k || m || k) secure against birthday attack?

if the attacker finds another message m' different from m such that h(m') = h(m) this doesn't guarantee that the prefix of m' is equal to the prefix of m, so with high probability H(k || m' || k) will be very different from H(k || m || k).

Correct: an adversary can't do a collision search offline because the adversary can't even evaluate the function $m \mapsto H(k \mathbin\| m \mathbin\| k)$.

  if the attacker wants to append extra bits to H(k || m || k) and compute another step of Merkle and Damgard algorithm he/she can't because he/she doesn't know the last block (that is the key), he/she only knows message blocks sent during the communication.

Correct: although if given $h = H(k \mathbin\| m \mathbin\| k)$ the adversary could compute $H(k \mathbin\| m \mathbin\| k \mathbin\| m')$ for some suffixes $m'$, that is of no consequence unless by luck $m'$ happens to end with $k$, which is completely improbable.

  if the attacker finds with birthday attack a message m' such that h(m') = h(k || m || k), he/she cannot verify if that authentication tag is correct because he/she doesn't know the key k. So the attacker to find a message m' such that h(m') = h(k || m || k) generates all possible hashes (considering the rule of birthday bound) in order to find the same value of H(k || m || k).

I don't really understand what you're getting at here, because $H(m')$ is not relevant to the authentication system.

All that said: The birthday paradox is nevertheless relevant even if the adversary can't perform an offline collision search!

Suppose you're using a 128-bit hash like MD5, and you learn the authentication tag $H(k \mathbin\| m_i \mathbin\| k)$ for a whopping $2^{64}$ messages $m_1, m_2, \dots, m_{2^{64}}$.  Suppose for simplicity that $k$ and the $m_i$ are all at least one full block long—at least 512 bits, for MD5.  With high probability, there will be a pair of messages $m_i \ne m_j$ with $H(k \mathbin\| m_i) = H(k \mathbin\| m_j)$, which means not only that $H(k \mathbin\| m_i \mathbin\| k) = H(k \mathbin\| m_j \mathbin\| k)$ but also $$H(k \mathbin\| m_i \mathbin\| m' \mathbin\| k) = H(k \mathbin\| m_j \mathbin\| m' \mathbin\| k)$$ for any common suffix $m'$, enabling forgery of many additional messages!  This is why for an iterated hash with an $n$-bit state, you should use it only for ${\lll}2^{n/2}$ messages.

To my knowledge, this was first described by Preneel and van Oorschot in their 1995 MDx-MAC paper.  It is a general attack on any hash of this sort with an $n$-bit state; the same idea applies to HMAC too even though HMAC had not yet been invented and Preneel and van Oorschot sensibly chose not to disrupt the natural flow of time by describing how it applies to HMAC.


Are there any symmetric Partial Homomorphic Encryption Schemes?

It depends on what you mean by "symmetric". As mentioned in the comments, you could use an asymmetric scheme and let $\mathsf{k} = (\mathsf{sk},\mathsf{pk})$. This seems unsatisfying though.

If you want symmetric to exclude this definition, a natural way to restate your question is "Are there any partially homomorphic encryption schemes in Minicrypt", in the sense that you can build them from solely the existence of a one-way function. I'm unsure of the answer in this situation, but there's some evidence against it being true.

For motivation, an easy way to construct a somewhat homomorphic encryption scheme is from $\mathsf{LWE}$.
This states that:
$$(A, As + e)\approx_c (A, u)$$
for $A$ and $e$ distributed correctly.
Standard LWE encryption schemes then use $As+e$ as a "blind", and then apply the one-time pad.
This design pattern of "Use a pseudo-random function to construct a "blind", then use the one-time pad" is fairly common. What gives LWE its homomorphic property is that the pseudo-random function $(A, As+e)$ is somewhat homomorphic.

So, a naturally way to try to answer your question would be starting with some one-way function / pseudo-random function that is partially homomorphic. A recent result showed that taking various minicrypt primitives and adding an additional partial homomorphic property is sufficient for many Cryptomania primitives (and therefore already takes you out of Minicrypt). This of course doesn't answer your question in the negative, but it does rule out a natural class of approaches to designing such a scheme while staying within Minicrypt.


I'd say that if you'd use HKDF as it is supposed to, then you should concatenate the two the concatenated result as Input Keying Material (IKM). HKDF has an extract first which will compress the IKM so you can input as much keying material as required.

You should of course make sure that it is impossible to have collisions for concatenated secret and password pairs. This is easily accomplished by making sure that the DH secret is constant sized (which is best practice anyway).

It is always possible to later add an actual salt; a password is not unique across invocations and therefore it is unsuitable to be a salt. You may want to add a salt later to reach a higher security level and leave it empty for now.

You may want to first perform a password hash over the password and include the result in the HKDF calculation. The reason for that is that currently the other party of the key agreement must know the password in advance. It is better to store a password hash in case the other other party gets compromised.

With that in mind you may also be interested in SRP and other augmented PAKE protocols.


Without using ROT13 explicitly, it can be done. You can draw up a frequency histogram of the text, and then shift it 13 characters left (or right). If it lines up to give the average English frequency distribution, it's likely this is ROT13 material. This will only work well if you have a large enough sample, obviously.

You should be able to do roughly the same thing with Base64, since it too preserves frequencies to some extent (though in a less obvious way, as the encoding works at the bit level, not on each character)

Though for Base64 a more intelligent approach is to just decode the whole thing and check that it looks like english (or whatever format you expect, really) either by frequency analysis or another method. It would be much faster and easier, but according to your question this is not a valid approach, so...

Nitpick: neither ROT13 nor Base64 use a cryptographic key, so they are not ciphers, but encodings (at least Base64 is - ROT13 tries to be a cipher, and could be called one, I suppose, but it's not technically correct).


Algorithm for factoring a 30 decimal digit number

Which algorithms give the best performance for 30 decimal digit numbers?

30 decimal digits is 100 binary digits.

Trial division will require around $2^{50}$ divisions.
Pollard-Rho-Factoring will require around $2^{25}$ checks - this may be a good pick for you if you want to implement it yourself quickly and don't mind having to wait a bit on an optimized execution result.
Most decent quadratic sieve implementations will do this number within seconds.
Most ECM implementations will do that too. If you need something more optimized than Pollard-Rho, using ECM is probably a good pick. Refer to this database for optimal curve representation choices and the Handbook of Applied Cryptography (Ch14, PDF) for fast scalar multiplication strategies.


Bouncy Castle elliptic curve from explicit parameters (E-521)

In order to do this, first convert the Edwards curve to Montgomery form, then to Weierstrass form, per this thread.

But, as the above thread explains, as well as CodesInChaos' comment, this will result in poor performance.

Thanks to CodesInChaos for pointing me in the right direction despite the stupid question.

Also see:

Elliptic Curves of different forms
http://samuelkerr.com/?p=431 which has a nice Python script for going from Montgomery to Weierstrass


No, Rfc2898DeriveBytes itself represents a deterministic algorithm. Any randomness it produces comes from a combination of randomness in the password (incorrectly named ENCRYPTION_KEY in the code) and the salt (the correctly named SALT). The other input options (such as the iteration count and string encoding) are configuration options and do not add significant randomness while still altering the final result.

Generally the output of Rfc2898DeriveBytes is made random by using a random salt which is then stored with the ciphertext (or resulting password hash, if it is used for that purpose). During decryption that same salt is used as input so that the same output key material can be produced to perform the decryption.

There are ways of constructing a class instance in such a way that the salt is generated internally, e.g. Rfc2898DeriveBytes(String, int) where the final int is the salt size. That's however not used in the code that you've shown.

Notes:

The inaptly named Rfc2898DeriveBytes class implements PBKDF2 and therefore should have been named PBKDF2DeriveBytes or just PBKDF2.
As indicated, PBKDF2 operates on a password, not a key. You can directly use a key with a unique or random IV to encrypt ciphertext if you already have a key.
A sentence such as "just looking for something very simple to encrypt data" will make any cryptographer cringe. You either do cryptography right or you can forget about security; there is not all that much middle ground.


Is DL difficult under the group of Unimodular matrices?

You will need to solve discrete log(s) over the field itself at some point to solve the matrix equation. Now, discrete logs over $F_{2^n}$, as opposed to $F_p$ ($p$ prime) are much easier as shown in the work by Joux, but no full proof yet.

However see, e.g.,here where the abstract states
"A new index calculus algorithm with complexity L(1/4+o(1)) in very small characteristic" is presented.

The L-notation is clarified in wikipedia, but the notation above essentially means that the complexity is essentially $\exp{[ c_n (\log n)^{1/4} (\log\log n)^{3/4}}]$ so closer to polynomial than exponential and the coefficient $c_n$ goes to zero as $n$ goes to infinity.


While using onetime encryption is it possible that one can deduce the key of a message if the contents of the message are already known?

Knowing the plaintext and ciphertext will allow you to recover (a portion of) the key.

The OneTime package referenced in the comments implements a simple one-time pad.  Because the plaintext and ciphertext are related by a simple XOR it is trivial to calculate the portion of the one-time pad that is used for that message.  If all of the rules for using a one-time pad are followed (e.g. no re-use, truly independent random values for each bit, etc), then that portion of the key can be calculated, but it wouldn't provide any value beyond what was already known.


Where does bootstrapping occur, client side or server side?

The aim of Fully Homomorphic Encryption (FHE) is out-sourcing the computation, especially onto the cloud or from small computing device into a more capable one securely. FHE was the holy grail of Cryptography that waited for around 30 years to be found, mentioned On data banks and privacy homomorphisms by Rivest.

In FHE schemes we are talking about circuit computation that is similar to electronics but this time mathematically. For semantical security, a noise is added and this is the main problem when performing FHE operations - i.e. dealing with the noise.

When circuit operations are performed with the used FHE scheme the noise increases. Especially the multiplication is problematic - doubling the noise. After a threshold is passed you can no longer decrypt the ciphertexts. For example in Fully Homomorphic Encryption over the Integers

$$c \leftarrow m + 2r + 2x$$ where $m \in \{0,1\}$, $r$ is the random (noise), and $x$ is the public key (note: here $x$ part it is simplified)

The bootstrapping is the novel idea given to us by Gentry. Before reaching the threshold, Gentry showed that we can run the circuit of the decryption algorithm of his scheme, and providing ciphertexts to this decryption circuit and encryption of the private key. In the end, we will get new ciphertext but the noise is gone.

Now, if we turn in to your question. For an FHE circuit, actually, you calculate the depth requirement and possible techniques available on your selected scheme, like bootstrapping, re-linearization, modulus switching. Once you designed and implemented your circuit, you send all the information to your outsource to compute (in FHE terms $\texttt{EVAL}$). If you need bootstrapping at some point to reduce the noise, you already provide the necessary information on your circuit and designed it with bootstrapping. Yes, actually, bootstrapping is a part of your circuit. There is no need for interaction. Fire and forget until the result is returned to you.

For the comment :

You prapere your circuit $\mathcal{C}$ and supply the required parameters for the evaluation;
 $$\texttt{EVAL} (k_{pub}, \mathcal{C}, c_1,\ldots,c_l, E_{k_{pub}}(prv))$$ where the $c_1,\ldots,c_l$ are the encryption of the plaintext, i.e. $c_i = E_{k_{prv}}(p_i)$, $k_{pub}$ is your public key, and encryption of your private key $E_{k_{pub}}(prv))$ if bootstrapping is required.

As always;

you keep the private key secret to yourself, and
the public key is public.


Are there flaws in (cryptographic) science/engineering/software/research due to pseudo random generators?

There are a few examples:

RANDU is probably the quintessential example of a bad pseudorandom generator. It consisted of the sequence $x_{i+1} = 65539\cdot x_i \bmod{2^{31}}$, which is always odd and whose sequential triples are highly correlated. It was implemented by IBM in its software, and so it was used all over the place. It has been suggested that research results relying on RANDU are not reliable, but I could not track down any concrete example of this.
Another interesting example is that of 1992 Ferrenberg et al., in which a pseudorandom number generator that passed the statistical tests common of the time, but nevertheless resulted in incorrect results in a real Monte Carlo Ising-Model simulation. The generator in question was R250, a very simple generalized feedback shift register.

There are most likely many other examples incorrect results that simply haven't been checked or reproduced.


Your question starts from an assumption that often isn't valid.  You write:

  Assuming the user didn't have to input the OTP value or counter number

but in fact, for cost reasons, often these devices don't haven't any way to send the counter number to the server; the user would have to input it.

If the counter value is actually based upon the time, so it doesn't need to be sent, then yes, the quote from Thomas Pornin doesn't apply.  For those kinds of tokens, yes, the server can use the time and we don't have the issue with it getting desynchronized if you press the button 100 times.  The server does still need to make sure that the token's time approximately matches the server's time, and that the number only increases (to avoid replay attacks).


Is it not secure if we use weak passwords to protect exported PKCS #12 files with private keys?

If one day this PKCS #12 file is stolen by a hacker, then, can he perform an offline dictioary attack to this file?

Yes, that's possible. The password is simply used to directly derive a symmetric key, which is used in turn to encrypt the private key.

  Is the (un-)exportability guaranteed by a cryptography algorithm (so that no one can change the property), or only by a software method (so that hackers can change the property)?

Generally it is just a bit set to 0 or 1 somewhere. Where and how it is stored depends on the Cryptographic Service Provider (CSP) and the implementation of the key container that contains the private key. If it and the private key are stored in a HSM or Smart Card, it may be tricky to change it.


When dealing with a block cipher of large block size, the text appearing as a quote in the question

Most modern block ciphers have a 128-bit block size, but they operate on 32-bit words. They build the encryption function from many 32-bit operations.This has proved to be a very successful method, but it has one side effect. It is rather hard to build an odd permutation from small operations; as a result,virtually all block ciphers only generate even permutations.

is about a merely theoretical attack. The book's chapter 3 acknowledges it:

This attack has no practical significance whatsoever.

That's because knowing the parity of the permutation implemented by an otherwise ideal block cipher with a $b$-bit block and some fixed key only helps adversaries after they have obtained $2^b-2$ plaintext/ciphertext pairs: the last two plaintext/ciphertext pairs are revealed by that parity. Before that threshold, nothing actionable comes from that one bit of information.
For example, with $b=3$, after an adversary obtained plaintext/ciphertext pairs 0/1, 1/6, 2/5, 3/0, 4/2, 5/7, which we can picture as
      0   1   2   3   4   5   6   7
      1   6   5   0   2   7   ?   ?
and if the permutation is known to be even, then the adversary can determine¹ that the remaining pairs are 6/3, 7/4 (rather than 6/4, 7/3).  But before the adversary obtained the pair 5/7, knowing that the permutation was even was of no help to predict if 5 maps to 3, 4, or 7.
Even if a 128-bit block cipher is known to implement an even permutation for any key, that's not an exploitable weakness. It does allow to build a theoretical distinguisher from an ideal cipher, but only after making so many queries ($2^{128}-1$) to the encryption or decryption oracle² that it does not count as attack against usual or reasonable security definitions.
The quoted text is somewhat exaggerating the difficulty of building an odd permutation from small operations; see these comments by poncho:

The standard trick for small block Feistel ciphers is to use modular addition, rather than xor, in each round; that way, the round, and hence the permutation, has a 0.5 probability of being odd. (…) If the two halves of the Feistel state are $a, b$, then the update $a\gets a+F(k,b)$ can be odd; in fact, it will be if an odd number of the $F(k,b)$ values are odd (fixed $k$, over all possible values of $b$).

¹ Proof: going from 01234567 to 16502734 can be done with an even number of permutations, e.g. 01234567 → 10234567 → 16234507 → 16534207 → 16504237 → 16502437 → 16502734.
² The challenger randomly choose an ideal random cipher or an even random cipher, the distinguisher tries to guess that choice. It needs $2^{128}-1$ queries to determine if the cipher is even or odd, if odd outputs 'ideal', otherwise outputs 'even'. It succeeds with probability $3/4$.


A Card Verifiable Certificate (CVC) is a certificate that has been created with validation and verification on smart cards in mind. These cards are extremely small System on Chips, with RAM, persistent memory (flash or EEPROM) and ROM.

So basically it's the same as a normal certificate, but it doesn't contain as many bells and whistles, as the bells and whistles it does have are generally minimized as well.

There are some standards for CVC's but generally they are not complied to so you will have to look up the specific protocol to know how the certificate is encoded.

Things you should expect:

a non-standard certificate format
a flattened DER encoded structure (sometimes just a single sequence with child elements)
specialized DER tags
the use of octet strings over integers or bit strings (smaller encoding)
short date formats for the date of issuance and date of expiry
few if any personal details
a simplified / shorter scheme for subject / issuer identification
for ECDSA: flattened signature format (i.e. statically sized R & S)
for RSA: signatures with message recovery (ISO / IEC 9796)
signatures over all of the other elements (so the signature can be updated / verified in a single operation)
simplified encoding of the public key (e.g. without algorithm specification)

Sometimes the certificate contains an OID that specifies the specific scheme and versioning information. In that case you could try and find the protocol required.

As for your question:

Base 64 is not a certificate format, it's an encoding format.
You cannot just convert an existing X.509 certificate to CVC because the signature would not be valid - even if you knew which ASN.1 elements to copy / convert.
There is no generic standard that is commonly used, so there are no generic tools - you'd need specialized tools and - of course - the private key of the issuer.


That doesn't hide Bob's identity from eavesdroppers.

(The OP mentioned in chat that the OP isn't trying to do that.)

I can no longer spot any other problems with the key exchange part.

The encryption/decryption of application level data is vulnerable to arbitrary replays

and reflection and dropping.  The public MAC input should indicate direction and

message_number and [number of messages received].  There should be a separate way

for it to securely indicate those three things without sending any application-level message, and a way for it to close_notify with a secure indication of those three things.


Application of uni-directional proxy re-encryption?

In bidirectional proxy re-encryption, there's an efficient algorithm to transform a re-encryption key from Alice to Bob in a re-encryption key from Bob to Alice. For example, the BBS98 proxy re-encryption scheme has re-encryption keys of the form $rk_{A \to B} = \frac{b}{a}$, where $a$ and $b$ are the private keys of Alice and Bob, respectively; it is easy to see that this scheme is bidirectional, since the algorithm to transform $rk_{A \to B}$ into $rk_{B \to A}$ is simply the modular inversion:
$$rk_{B \to A} = (rk_{A \to B})^{-1} = (\frac{b}{a})^{-1} = \frac{a}{b}$$

Now, let's recall what's the main functionality of PRE: secure delegation of decryption rights from one user (Alice) to another (Bob). We usually think of unidirectional PRE schemes since in most cases the delegation is inherently unidirectional. For instance, in the typical email example, I can delegate decryption rights to my secretary while I'm on holidays so he can decrypt my emails. This, however, doesn't mean that my secretary wants me to be able to read encrypted emails directed to him. Similarly, in a file sharing scenario, I may share some encrypted documents with you, but you don't necessarily want to do the same with me.

Hence, bidirectional PRE schemes are only useful when there's a complete symmetry in the trust relationship between Alice and Bob. This may happen in some scenarios, but it's not common.


The attack is described in the article Related-key Cryptanalysis of the Full AES-192 and AES-256 and applies in the following situation:

There is a key owner; the key is $K_A$ and the attacker tries to guess it.
The key owner can somehow be persuaded to compute three other keys $K_B$, $K_C$ and $K_D$, from $K_A$, using a specific derivation algorithm ($K_B$ is equal to $K_A$ XORed with a constant that the attacker chooses; $K_C$ and $K_D$ use a more complex but equally deterministic derivation algorithm).
Then, the attacker can make the key owner encrypt and decrypt arbitrary blocks -- that the attacker chooses -- with the keys $K_A$, $K_B$, $K_C$ and $K_D$. The key owner will accept to process up to $2^{99.5}$ blocks (that's 16-byte blocks, hence a grand total of about 14 thousands of billions of billions of gigabytes).
Finally, the attacker has access to some storage space of about one million of billions of gigabytes.

Under those conditions, the attacker can guess $K_A$. For details, see the article.
The name "related-key attack" comes from the involvement of several distinct keys, linked together by known relations. Resistance to such attacks were not part of the evaluation criteria during the AES competition (when Rijndael was chosen as AES). Related-key attacks are not very practical (even if the $2^{99.5}$ chosen plaintext/ciphertext value was not ludicrously large, the conditions on the four keys would still make the attack only theoretical).


why is FPGA suited for Cryptography applications?

The answer is simple. When you have a job to be done you choose toolkit which would accomplish it in a fastest possible way.CPUs are usually multi-tasked they would be running your OS beside running your cryptographic toolkit. Also, colloquially speaking, FPGA circuits can be designed for partcilar sort of computaion in hardware reaching a far higher efficiency in terms of energy utilization and performace.

So it is not that FPGAs have some special features that CPUs lack. Its just a matter of specialization in circuits construction for a specific task. ex. SHA.


Galois LFSR

In a Galois LFSR with polynomial $P$ of degree $n$, the state is a vector of $n$ bits assimilated to the binary coefficients of terms of degree $n-1$ to $0$ of a polynomial; we note both the state and its polynomial $S_j$ when at step $j\ge0$ .

The next state is computed as $S_{j+1}=S_j\,x\bmod P$. Equivalently, the state is shifted towards the high-order coefficient, which is output and dropped from the state; a 0 is introduced as the low-order coefficient; then if the output was 1, state bits at indexes corresponding to non-zero terms of $P$ (ignoring the high-order term $x^n$) are complemented.

It follows that in a Galois LFSR,
$$S_j=S_0\,x^j\bmod P$$
which allows efficient direct access. Polynomial modular exponentiation can uses the same methods as integer one except using carry-less arithmetic, with the simple algorithm having cost $O(\log(j)\,n^2)$.

Also, the output of the Galois LFSR in $j$ steps is the coefficients of the quotient $Q$ of the polynomial division of $S_0\,x^j$ by $P$, starting from the coefficient of degree $j-1$ for the first output bit, down to zero for the $j^\text{th}$; and it holds $P\,Q+S_j=S_0\,x^j$.

Fibonacci LFSR

The question uses a Fibonacci LFSR, as apparent by having the state at the beginning of the output. Afterwards, the next output bit is the parity of the bitwise-AND of the $n$ previous bits and the coefficients defining the polynomial. I'll use the convention that the previously produced bit is ANDed with the coefficient of degree $n-1$ of the polynomial. With that convention, the low-order (constant) coefficient of the polynomial is the leftmost bit of the question's Coeffients, and the polynomial $P$ is $1+x+x^2+x^3+x^4+x^{11}+x^{13}+x^{16}+\dots+x^{55}+x^{56}+x^{57}+x^{60}+x^{63}+x^{64}$
with the term $x^{64}$ not shown in the question (and never combined with anything by bitwise-AND when stepping the LFSR).

Caution: standard literature on Fibonacci LFSRs and Berlekamp-Massey often use the so-called reflected or reciprocal polynomial, where coefficients of order $i$ and $n-i$ are exchanged (which might change the order of the polynomial). The present answer does not use this form for the polynomial.

Without proof: with our convention, when the low-order coefficient of the polynomial is $1$ (as customary in Berlekamp-Massey), Galois and Fibonacci LFSRs using the same polynomial produce identical output sequences, only from different starting point and with different states (when the lowest-order non-zero coefficient of the polynomial has order $l>0$, the Fibonacci LFSRs reaches the same periodic sequence as the Galois LFSR after $l$ steps at most, when the Galois LFSR always enters that periodic sequence right from the start; we have the option of removing the first $l$ bits and reducing the polynomial's degree to $n-l$, so that the low-order coefficient of the polynomial becomes 1$).

We can always convert a Galois state to Finnonacci state yielding the same output by stepping the Galois LFSR $n$ times; its output (in chronological order) is the desired Fibonacci state (produced by increasing order of the corresponding bits in the polynomial, that is reflected compared to $Q$ obtained by polynomial division of $S_0\,x^n$ by $P$, by exchanging coefficients of order $i$ and $n-1-i$); that's because the Fibonacci LFSR first outputs its state (starting frow low-order, in our convention).

By the same reasoning, when the low-order coefficient of the polynomial is $1$, the Galois state $S_0$ corresponding to a certain Fibonacci state must be such that the corresponding output $Q_0$ of the Galois LFSR in the next $n$ bits is the Fibonacci state (produced by increasing order of the corresponding bits in the polynomial). It thus holds that $P\,Q_0+S_n=S_0\,x^n$. It follows that the coefficients of the Galois state $S_0$ from $n-1$ to $0$ are the coefficients of $P\,Q_0$ from $2n-1$ to $n$, where $Q_0$ is the Fibonacci state reflected by exchanging coefficients of order $i$ and $n-1-i$.

When the low-order coefficient of the polynomial is $1$, to compute the state of a Fibonacci LFSR after $j$ steps, we can thus convert its state to Galois form, fast-forward that, and convert back.

With $\widetilde{F_j}$ the Fibonacci state at step $j$ with reflection by exchanging terms $i$ and $n-1-i$, and $\lfloor U/V\rfloor$ the quotient of the polynomial division of $U$ by $V$
$$\widetilde{F_j}=\left\lfloor{\left(\left\lfloor{\widetilde{F_0}\;P}/{x^n}\right\rfloor\,x^j\bmod P\right)x^n}/P\right\rfloor$$

In more details:

Reflect the Fibonacci initial state, yielding $Q_0=\widetilde{F_0}$ (where the first outputs $0$ to $n-1$ are the terms of order $n-1$ to $0$);
Compute $P\,Q_0$ and keep bits of order $2n-1$ to $n$, yielding $S_0$ from order $n-1$ to $0$;
Compute $S_j=S_0\,x^j\bmod P$;
Compute the quotient $Q_j$ of the polynomial division of $S_j\,x^n$ by $P$;
Reflect $Q_j$ to compute the Fibonacci state $F_j$ after $j$ steps (which from order $0$ to $n-1$ is also outputs $j$ to $j+n-1$).

Note: Steps 4. and 5. are equivalent to stepping the Galois LFSR $n$ times starting from $S_j$, forming the Fibonacci state from order $0$ to $n-1$ (left to right in the question).

An alternative matrix method considers the transformation resulting from stepping the LFSR (Fibonacci or Galois) as multiplication of a (sparse) matrix. That matrix can be raised to the $j^\text{th}$ to obtain the matrix corresponding to stepping $j$ times, but the matrix is no longer sparse, and (using schoolbook matrix multiplication algorithms) the time grows $O(\log(j)\,n^3)$ rather than $O(\log(j)\,n^2)$, with space $O(n^2)$ rather than $O(n)$.

Here is hopefully C99-conforming code specialized for $n=64$ and Fibonacci form, heavily optimized for speed. Notably, the code:

Processes in parallel over 64-bit and uses no table, which I guesstimate saves like a factor of 100 in speed compared to bit-by-bit on a 64-bit CPU, on top of having a cost growing with $j$ as $O(\log(j))$.
Is branch-predictor friendly (the only test in inner loops is their end condition); this is obtained by masking rather than testing, often extending a low-order bit to 64-bit using negation: -(uint64_t)1 is 0xFFFFFFFFFFFFFFFF while -(uint64_t)0 is 0x0000000000000000, and that's standard-conformant.
Off-topic rant: If you are a compiler writer in certain large company, please make it unnecessary to use a workaround; no I won't bow to a\&(0-b) when a\&-b is more recognizable.
Stores the low-order coefficient of the polynomial $P$ in the high-order bit of variable $p$: that's a common implementation technique for Galois LFSRs, and eases conversion from bits in the order of the question to integer.

The code first performs the computation of $x^j$ in step 3, by binary exponentiation scanning $j$ from right to left (the low-order 6 bits are optimized out because $x^j$ requires a single shift for $j<2^6$); then steps 1 and 2 (the initial reflection reduces to scanning bits of $s$ in the appropriate order); then the rest of 3; then steps 4 and 5 are handled by stepping the Galois LFSR (the final reflection reduces to accumulating the result in the appropriate order).

I wanted to fit the function's code including comments in the ≈25 lines requiring no scrolling, so I (ab)used the C syntax, like using multiple operators , and separators ; on the same line.

// fffibo64:  Fast-Forward a 64-bit Fibonacci LFSR
//  Inputs:
//   p  The polynomial, of degree 64; high-order bit of p is the poly's
//      constant term, and must be 1; coefficient x^^64 is implicit
//   s  Initial Fibonacci state (that is outputs 0 to 63 starting at high-order)
//   j  Number of steps
// Output: Fibonacci state after j steps (that is outputs j to j+63 starting high-order)
#include <stdint.h>
#ifdef _MSC_VER                     // this vendor has its own views on C, workaround that
#pragma warning (push)
#pragma warning (disable : 4146)    // avoids "unary minus operator applied to unsigned type"
#endif
uint64_t fffibo64(uint64_t p, uint64_t s, uint64_t j) {
    uint64_t u,v,w,x;               // workhorse temporaries
    // compute x^^j mod p into x, with optimization for low-order 6 bits
    x=((uint64_t)1<<63)>>(j&63);    // takes care of the low-order 6 bits of j
    if((j>>=6)!=0)
        for(v=p;;) {                // for remaining bits of j, if any
            if ((j&1)!=0)           // perform x = x*v mod p
                for(u=x, x&=-((w=v)>>63); w+=w; x^=(u=(p&-(u&1))^(u>>1))&-(w>>63));
            if ((j>>=1)==0) break;  // we have handled all bits of j
            // perform v = v*v mod p
            for(v&=-((u=w=v)>>63); w+=w; v^=(u=(p&-(u&1))^(u>>1))&-(w>>63));
            }
    // perform p*reflected(s) and keep coefficients 127 to 64 of that into v
    for(w=(p+p)|1, v=0; v^=w&-(s>>63), w+=w; s+=s);
    // perform u = v*x  mod p
    for(u=v&-(x>>63); x+=x; u^=(v=(p&-(v&1))^(v>>1))&-(x>>63));
    // here u is the Galois state after j steps; step it into x, reflecting
    for(w=64, x=0; x+=x+(v=u&1), u=(p&-v)^(u>>1), --w;);
    return x;
    }
#ifdef _MSC_VER
#pragma warning (pop)
#endif

// demo of the above, producing the output stream bit by bit both sequentialy, and with
// direct access, with (hopefully) identical result.
#include <stdio.h>
int main(void) {
    uint64_t j,
        p=0xf814a8fd7ccb3bc9,   // 1111100000010100101010001111110101111100110010110011101111001001
        s=0x0f5b61d9ca0c991e,   // 0000111101011011011000011101100111001010000011001001100100011110
        t=s,x;
    for(j=0; j<800; ++j) {
        printf("%d", (int)(t>>63));
        // evolve the state t step by step
        x=p&t; x^=x>>32; x^=x>>16; x^=x>>8; x^=x>>4; x^=x>>2; x^=x>>1; t=(t+t)|(x&1);
    }
    printf("\n");
    // same sequence with direct access
    for(j=0; j<800; ++j) printf("%d", (int)(fffibo64(p,s,j)>>63));
    printf("\n");
    return 0;
}

Try it online!


Interlock Protocol for Preventing Man-in-the-Middle (MitM) Attack

Let begin with some definitions;

Passive attack: When the attacker only observes and not interacts with any of the parties it is called the Passive Attack. Detection of a passive attack is difficult to detect.

Active Attack: In Active attack, the attacker modifies the system on behalf of him. He can change, replay, or even delete the values or try to impersonate one of the users. There is no bound for the active attacker. Remember the quote;

"Attacks always get better; they never get worse."

  why do most documents say about altering the message content by the attacker?

That really depends on the aim of the attacker. When the attacker is able to change the message and the target is accepting the messages it is perfect. The target is a puppet of the attacker. More sophisticated attacks may require more than a message change as in The 9 lives of Bleichenbacher's CAT, it puts another scratch again. Also, remember that even in Cryptoanalysis the first aim is accessing the message not the key. The key is sufficient but not necessary.

  Can't the hacker just keep a copy of encrypted block and send the encrypted original data to Bob?

If it suits he can, but he is no longer a passive attacker, now he is an active attacker, he modified the protocol. For full answer see in 5.

  Why does a MITM presence interrupt the network? For example, Wireshark captures the packets but still, the actual recipient receives the packet.

The MitM attack requires an active attacker. You use the WhireShark as a passive attacker. This is similar to wiretapping. Tapping is even possible in Fiber Channels.

  could an interlock system be susceptible to passive attack?

There is no known passive attack for the Interlock protocol. Of course, there is always a passive attack, that is; breaking the Diffie-Hellman problem or the Discrete Logarithm Problem.

  Can Eve send the original data without altering the message content, and keep a copy of it to integrate it with the remaining message blocks

Let remember The Interlock Protocol which is designed to expose the MitM attack. Once the key exchange is finished the two sides execute;

Alice encrypts a message $m$  with her key and sends only half of the message.
Similarly, Bob encrypts a message $m$  with his key and sends only half of the message.
Then, Alice sends the other half of her message and finally,
Bob also sends the other half of his message.

Alice and Bob can combine and see the message.

Replaying is not possible as noted in the The Interlock Protocol article. The MitM attacker must decrypt the incoming data and then encrypt with the key between his and Bob. Since he cannot decrypt, he must send something else. But, he cannot send the same half text since when Bob decrypts it with the "wrong" key and Bob will get a garbage message.

Since he is exposed, the parties must establish a new key exchange in a secure way.


Does keeping a public key private or using multiple encryption help?

Keeping the public key private:

Does not help in protecting data.
Does not work: depending on the algorithm, the public key could be recomputed from the exchanged messages.
Does not work: something which has been communicated to more than two people cannot be considered secret anymore. Especially since public keys are commonly written everywhere without any particular protection.
Does not work: people who would bother trying to crack your friend's private key would be people interested in your friend's secret, so chances are that they already have the public key (the attacker is one of your friend's friends, or already has hijacked the computer of one of your friend's friends).

As for cascading ciphers, it just makes processing slower, and more complex, both activities being ultimately detrimental to security (way more than the off-chance that one of the algorithms is actually weak, which does not happen often as long as none of them is a homemade cryptosystems -- these, of course, are almost always laughably vulnerable).

And "military security" is not stronger than normal security; it is just usually much more expensive.


Getting unlimited amount of signatures - Risk?

In my opinion this may open door to a lot of attacks the attacker can use.

Actually, public key signatures are designed to be used securely like this.  When we design a signature method, we assume that the attacker can ask for a large number of messages of his choosing to be signed, and still try to ensure that the attacker cannot generate a valid signature for a message that he did not ask to be signed (or recover the private key) - if someone can show a method, we consider that signature method as broken, and discard it.

However, there is one possible avenue for the attacker; if he submits the identity $Eve$, and gets the signature for $(Eve, DHPublicKey)$, he now has a valid message/signature pair, which would verify just fine.  If he can use that signature somehow in an attack, well, that's one thing that the signature method doesn't protect you against.  Of course, it's possible that there is no such attack (for example, if the attacker doesn't know the $DHPrivateKey$ that corresponds the to $DHPublicKey$ in your message), however that is something you need to consider.


Strong LRSW assumption for type 3 pairing groups

In a type-3 group, after an oracle query you get to see $(g_1^a, g_1^{at}, g_1^{as+axst}, g_1^{ax}, g_1^{axt})$ but not $g_1^s$ or $g_1^t$ (those are in $G_2$). Suppose you had a homomorphism $G_2 \to G_1, g_2 \mapsto g_1$ so you could recover $g_1^s$ and $g_1^t$.

Call your tuple from the oracle $(A, B, C, D, E)$ and compute $(Ag_1^r, B(g_1^t)^r, C(g_1^s)^r, D, E)$ for an $r$ of your choice. There is a unique value of $u \in \mathbb Z_p$ (where $p$ is the group order) such that $a+r = ua$ and if my math is correct, the modified tuple is now a correct tuple for $a' = ua$ and $x' = u^{-1}x$, which the oracle never signed.

Indeed, for the $D, E$ components the change of variables $a \mapsto ua, x \mapsto u^{-1}x$ does not affect the product $a'x' = ax$ so we can leave them alone. For $C$, the exponent was $as + axst$, the second summand is ok but the first one has $as = a'u^{-1}s$ so we want to change that $a$ to $a'$. We can't do that directly, but since $au = a + r$ we can make up the difference by adding $g_1^{rs}$. This change from a multiplicative relationship (that leaves the product $ax$ alone) to an additive one (that we can use to adjust the remaining terms) is what makes this attack work. For $A, B$ we then do the appropriate adjustment as well.

Note that you never actually get to know the value of $u$, or $x'$. That's why this doesn't work against plain LRSW, where you need to output $x'$ as well.


Affine Cipher: what to do if the number isnt invertible over mod n?

If you divide the whole equation throughly 2 you get
$$31a\equiv 19\pmod {34}$$
which you can solve to get $a\equiv 5\pmod{34}$. This then gives two possibilities for $a\pmod {68}$: either 5 or 39. For these two possibilities you can then find the corresponding $b$ (it turns out to be 5 in both cases) and check which solution works.


Making counter (CTR) mode robust against application state loss

Relying solely on randomization for the block counter is actually more likely to cause a nonce collision in case of a system time reset. This only gets worse as the message length increases. This is further exacerbated if the PRNG takes the system time as input, or does not have enough seed entropy. There is also no reason for the static 0 byte in the nonce.

How about a 48-bit time(in ms) counter, a 48-bit random value, and a 32-bit counter than increments from 0 for each block of the data?

This gives 9000 years of unique nonces each millisecond, a 280 trillion to 1 chance of a random collision in case of a system time reset, and a 64GB max data limit per nonce. This also makes the code for nonce incrementation more simple since it starts at 0 and is only a 32-bit unsigned integer.

Values above are approximations, but close and provide a reasonable example of the periods with those given bit sizes.


Well, you probably cannot check this without a somewhat explicit specification of $\varphi.$ In general, if the key scheduling function has a simple structure, and if $|V|=|K|$ this becomes easier; In that case, if  $\varphi(h_0,\cdot)$ is a permutation you are done.


How is the re-encryption done in Path ORAM?

Client holds a secret key, which is used to encrypt/decrypt all blocks.  Nonce is not used as a key but randomness to make sure that all the blocks, no matter updated or not, will look fresh.


You tried interpreting this as a ternary code written in columns, but why not in rows?

It was really quite simple to solve.

Here's the code I used:

for n in ['110','012','111','120','112','001','011','012']:
    x = int(n,3) + 64
    if x==64:
        x=32
    print chr(x),

and here's the answer:

   LEMONADE


Text partially decrypted regardless of IV

You are actually not talking about "ciphers" but about "modes of operations".

ECB mode does not use the IV so its value is ignored when using that mode. It's a great example of reason why do we even use modes of operation. (ECB is the fastest mode of operation, but it's the least secure one) This is an .bmp image encrypted using ECB. (and then converted to .jpeg)

As you can see you can easily deduce what was on the original. Using a different mode of operation (CBC) it's usually much harder.

Now the image is indistinguishable from noise, but there is still some info that can leak. If someone encrypts the same image twice the ciphertext will be identical in both cases.

And this i the reason for random IV. Even if the image is identical, the different IV will cause the ciphertext to be completely different. This is useful for example when encrypting passwords. Two identical passwords should not be stored as two identical ciphertexts.

In conclusion the IV is not made for preventing decryption of the ciphertext. That's the job of the key. Random IV is used to prevent leaking of "metadata" when adversary can see only raw ciphertexts.

In most of the modes of operation (like CBC) the "current" block is obscured by connecting it somehow (usually by XOR) with previous blocks ciphertext.

This leaves the first block which has no predecessor with no obfuscation. This is where the IV comes into play. We add a fake "previous block" into the ciphertext. (IV is usually prepended to ciphertext and is immediately visible to adversary) When deciphering we actually use the IV only for that first block. To decipher any other block all you need is the key and previous ciphertext (which is also visible to the adversary)

When no IV is provided then the first block is getting decrypted into $Plaintext \oplus IV$, and since this block is usually predictable (like first characters of file header) this usually allows pretty easily to guess the IV.


IND-CPA secure RSA padding with a partial homomorphic property

Here is a padding scheme for RSA that I crafted for the question. It allows encryption of strictly positive integers up to some moderate bound $b$, and such that the (ordinary) product of the plaintexts can be found from the product of the ciphertexts modulo the public modulus $N$ (with knowledge of the private key, by the method's normal decryption and unpadding method).

Plaintext $x$ with $1\le x\le b<N^{1/8}$ is randomly padded as $y=x\,r$, where random padding multiplier $r$ is a randomly seeded prime with $N^{1/8}<r<N^{3/8}$. Raw RSA encryption is then applied to $y$.

After raw RSA decryption, unpadding pulls the factors of $y$ at most $b$, and outputs their product $x$. It is possible to recognize a ciphertext obtained by using the homomorphic property from one that is not, by testing if $y/x$ is composite or not.

This has no discernible practical interest, but seems plausibly IND-CPA secure, and actually workable: padding can be made more efficient than RSA key generation; Pollard's Rho is enough for decryption for small $b$, and ECM will make $b=2^{128}$ feasible.

Variants are possible allowing decryption of the product of up to $h>2$ terms, by adjusting $b$ and the bounds for $r$. We want that $r_\text{max}<N^{1/h}/b$ and $r_\text{min}>b$. If we go that route, we also need to check that the public exponent $e$ is high enough that it remains overwhelmingly likely that $e\log_2r\gg\log_2N$, in order to prevent an $e^\text{th}$ root attack; and that there remains ample entropy in the choice of $r$ (well over twice as many bits as the security level) in order to avoid some meet-in-the-middle attacks.

We also have the option to widen the choice of the padding multiplier $r$, allowing any $r$ such that all its prime factors are above the plaintext bound $b$. That allows selection of $r$ in ways speeding-up (at least on average) the factorization job for un-padding. This is especially desirable for ciphertext obtained by the homorphic property, where it becomes compute-intensive to ensure that all unknown factors of $y$ are above $b$. We can choose $r=\prod s_i$ as the product of random primes $s_i>b$ :

with $s_i$ bounded by some moderate $s_\text{max}$, which will make Pollard's Rho efficient;
or with $s_i=1+\prod t_j$ for random primes $t_j$ bounded by some even more moderate $t_\text{max}$, which will make Pollard's $p-1$ efficient.


Why can't AES-GCM be used in IKEv1 phase 1?

With IKEv2 all payloads are generally sent in a single Encrypted Payload (SK) whose data is both encrypted and integrity protected/authentication (that protection covers the complete message, including the header and optional unencrypted payloads). That works quite nicely with modern AEAD algorithms like AES-GCM, the additional authenticated data (AAD) are the headers (IKE and SK) and any unencrypted payloads, the resulting authentication tag is what's sent as Integrity Checksum Data in the Encrypted payload.

On the other hand, IKEv1/ISAKMP handles encryption and integrity protection of IKE messages quite differently. For integrity protection of Phase 2 messages (Quick Mode/Informational), the message ID and the payloads are hashed (a PRF is used actually) and the result is added to the message in an additional Hash payload (during Main and Aggressive Mode it's similar but slightly differs based on the authentication method). The complete message, including that Hash payload, is then encrypted. So that does not really match with how AES-GCM works, unless the protocol would have been changed significantly (like getting rid of the redundant Hash payloads and handling integrity protection only via combined-mode cipher). But I guess there really was no point in doing that for an already obsolete protocol.

After writing this answer, I noticed that this is actually described in the introduction to RFC 5282.


Security implications of using hash as a MAC

In general, the construction $H(K||M||N)$ where $H, Y, N$ are known to an attacker is arguably no more secure than $H(K||M)$, which we already know to be broken. For that latter construction, we can easily forge a MAC of the form $K||M||PADDING||Z$ for some message $Z$.

This same attack would apply to the construction proposed in the question, except the forgery would be of the form $K||M||N||PADDING||Z||N$. This attack is feasible on many currently used hash functions, however, is not feasible on the new SHA-3.


First block as initialization vector in the CBC-MAC

My question is, if the first block is used as IV, then is it secure (unforgeable), and why?

Suppose with this scheme, you have the MAC for the message $[m_1, m_2, m_3]$.  Could someone without the key compute the MAC for the message $[m_2, m_1, m_3]$?


Why is SHA-3 robust against Length-Extension Attacks?

Everything was changed between SHA-2 and SHA-3.

In the specific case of the "length extension attack": the issue is that SHA-2 process data by splitting it into elementary blocks (64 or 128 bytes, depending on the SHA-2 variant), and produces for each block an output which has exactly the same size as the function output. Moreover, the output for a complete message is merely the current output after processing all blocks of the (padded) message. This means that anybody can take a hash output and "continue" processing of a longer message with additional blocks.

In SHA-3, a sponge construction is used. The crucial point is that, in a sponge, the internal state is much larger than the hash function output. Thus, you cannot simply "continue" processing of a message by using a hash output, because that output contains only a fraction of the internal state.

You can get the same kind of protection with a SHA-2 function by truncating the output. For instance, there is a (relatively new) member of the SHA-2 family called "SHA-512/256", which is SHA-512 (with a different conventional IV) with output truncated to 256 bits. This truncation makes it immune to the length extension attack.


Random Coin Flip using ElGamal and a Trusted Party

ElGamal encryption works like this:

We work in a cyclic group $G$ of order $q$ (a prime integer), with $g$ being a generator. Here, we note the operation multiplicatively. For instance, we work with integers modulo $p$ (a big prime such that $q$ divides $p-1$) and $g$ is one of the $q$-th roots of $1$ modulo $p$.
Private key is $x$, an integer modulo $q$.
Public key is $y = g^x$ (i.e. $g^x \mod p$ if we use integers).

A chooses random bit $a$, and a random integer $k$ modulo $q$, and announces $c_A = (g^k, g^a·y^k)$ (encryption of $g^a$ with ElGamal). The second half of that encrypted message is equal to $g^{x·k+a}$. B sees these values.

To bias towards 0, B can simply send the exact same value ($c_B = c_A$). B does not know the value of the bit from A, but he knows that by sending the same value, he forces the final XOR to be a 0. To make the manipulation less obvious, B can choose a random integer $f$ modulo $q$ and send:
$$c_B = (g^k·g^f, (g^a·y^k)·y^f)$$ (i.e. values computed from those sent by A). If you expand these equations, you will see that $c_B = (g^{k'}, g^a·y^{k'})$ where $k' = k+f$. B knows neither $a$ or $k$, but he sends a valid ciphertext for the same value $a$, and with a uniformly chosen random $f$ this cannot even be detected. This is how B biases the coin to 0 with 100% success rate.

To bias towards 1, the construction is a bit more complex. B computes this:

$$ c_B = ((g^k)^{q-1}·g^f, (g^a·y^k)^{q-1}·y^f·g) $$

for a random $f$ modulo $q$. If you expand this equation, you will see that $c_B$ is a valid ElGamal encryption of $g^{a·(q-1)+1}$. Since $g$ has order $q$, $c_B$ is thus the encryption of $g^1$ if $a = 0$, and $g^0$ if $a = 1$. Thus, B always sends the bit opposite of the bit from A, guaranteeing a coin toss of 1. Furthermore, the random $f$ makes sure that the manipulation is not detectable.

Generally speaking, this exploits the homomorphic property of ElGamal: given the encryptions of $m$ and $m'$, one can compute a valid encryption for $m·m'$, without knowing $m$ or $m'$.


How does an oblivious test of plaintext equality work?

You've messed up your question. Since the two ciphertexts both use the same r, anyone can easily check if $m_1=m_2$. This is not the interesting case.

But if the two ciphertexts are $(a_1, b_1) = (g^{r_1}, m_1 y^{r_1})$ and $(a_2, b_2) = (g^{r_2}, m_2 y^{r_2})$, then the tuple $(g, y, a_1/a_2, b_1/b_2)$ is of the form the mentioned paper deals with.


What use cases would benefit from a faster RNG?

This paper isn't about a faster RNG, and it's mostly only of interest in a computer science context rather than in an applied cryptographic context. These results reduce the theoretical requirements needed from two weak sources of randomness in order to combine them into a source of true randomness. However, in the applied world, we already have "enough" — a few bytes can seed a CSPRNG that will generate effectively infinite computationally-random bytes.

When systems today fall over due to randomness issues, it's usually due to systems-engineering failures: a good RNG wasn't used (despite them being widely and easily available), or not enough initial randomness was seeded (e.g., /dev/urandom on an embedded device), or a virtual machine was copied and restarted with the same initial random seed. These classes of problems aren't solved by improving our sources of randomness.

To your question directly, a faster RNG isn't of much practical use. A stream cipher seeded with enough randomness is effectively a DRBG, and can produce random bits extremely quickly — far more quickly than is needed for the overwhelming majority of use-cases. The operations that use that randomness typically execute far more instructions than do the operations to generate it.

Thomas Ptacek's response to this story on Hacker News is how I expect most crypto people feel about this.


Relations between RSA and Generalized Diffie-Hellman (GDH), factoring and GDH

Breaking the Generalized Diffie-Hellman (GDH) assumption is known to imply Factoring for Blum-integers. This is a result by Biham et al.
Since the (non)-equivalence of the RSA and Factoring assumptions is one of the biggest open questions in the RSA literature, it would be really surprising if there was a reduction from GDH to the RSA assumption, because then we would have the equivalence of the RSA and Factoring assumptions for Blum-integers given the result of Biham et al.


Can one implement AES on 4-bit microcontroller?

Yes, AES could be implemented on a 4-bit micro-controller such as this EM6626, and that would not be rocket science or stupidly slow. This application note illustrates that all kind of 8-bit operations are simple, and table lookups are possible.

In fact, tables are not even indispensable if performance is non-critical; see this minimalist AES source code in C which has a compilation option to avoid any table.

The most serious issue is the amount of RAM required: current 128-bit subkey and 128-bit data will eat half of the total 512-bit RAM of the above device.

Also worrying is the security: I know no 4-bit micro-controller with any kind of security evaluation. Thus I would trust such an implementation only if it is operated in a secure environment, and with a key that vanishes from the device after use. That's an appropriate security model for an enciphering machine, but not a copy-protection dongle.


Robust authentication and integrity for short OTP message

If you want to be consistent with OTP usage, then you should use a One Time MAC. Currently it seems the easiest path for that is to simply use Poly1305, but remember that you must never reuse keys for Poly1305, just like you can't reuse keys in OTP. (In particular, don't use the key generation routine used by ChaCha20-Poly1305 to derive the Poly1305 key from a nonce/key pair).

Using HMAC doesn't make much sense: if you're using OTP, that's probably because you don't trust any particular block cipher, so you shouldn't trust any particular hash or MAC algorithm.


Does this pairing-based signature scheme work?

Your proposed signature scheme falls to universal forgeries under a known message attack (UF-KMA).

The adversary $\mathcal{A}$ receives the public key $(A,P)$, a single message signature pair $(M,C)$ and the challenge message $M^*$.
It outputs $$C' := \frac{H(M)}{H(M^*)} \cdot C.$$

The adversary described above is succesful with probability $1$.
To see this, consider that $C$ is by definition
$$C = \frac{p}{a\cdot H(M)} \cdot G_2.$$
We now have
\begin{align}
C' &= \frac{H(M)}{H(M^*)} \cdot C\\
&= \frac{H(M)}{H(M^*)}\cdot\frac{p}{a\cdot H(M)} \cdot G_2\\
&=\frac{p\cdot H(M)}{a\cdot H(M) H(M^*)} \cdot G_2\\
&=\frac{p}{a\cdot H(M^*)} \cdot G_2,
\end{align}
which is exactly the signature of $M^*$ and will therefore be accepted by the verification equation.


Given any LFSR equation $$Z_{i+L}=C_0 Z_i+C_1 Z_{i+1}+\cdots+C_{L-1} Z_{i+L-1},$$ over any field, you can rewrite it as a linear system
$$
\left(
\begin{array}{cccc}
Z_{i} & Z_{i+1} & \cdots & Z_{i+L-1} \\
Z_{i+1} & Z_{i+2} & \cdots & Z_{i+L} \\
 \vdots & & & \vdots \\
Z_{i+L-1} & Z_{i+L} & \cdots & Z_{i+2L-2}\\
\end{array}
\right)
~
\left(\begin{array}{c}
C_0 \\
C_1 \\
\vdots\\
C_{L-1}
\end{array}\right)
=
\left(
\begin{array}{c}
Z_{i+L} \\
Z_{i+L+1}\\
\vdots\\
Z_{i+2L-1}
\end{array}
\right)
$$

and solve it by using linear algebra, since the right hand vector and the matrix entries are obtained from the observed keystream sequence $(Z_t)$. You will need $2L$ keystream symbols to obtain the coefficients uniquely.

In this case there are faster ways of solving such a system, such as the Berlekamp Massey algorithm, which recursively finds the solution with the smallest $L$, given the keystream $Z_t.$ See the answer to the question berlekamp massey to construct minimal lfsr? for more details.


I have this list of LibSodium primitives, which should I pick so that the implementations tend to be interoperable?

For symmetric encryption (encrypt data with a key, decrypt with the same key) use crypto_secretbox functions or possibly the crypto_secretstream functions. This seems to be what you want for problem 1.

Crypto_generichash() is not an encryption function. It's a hashing function. It takes in a message and spits out a short value known as a hash. The hash is unique per message, and different messages tend to have wildly different hashes. There is no known way to find out what message created a given hash faster than just trying all messages. Likewise there's no known way to find 2 messages that result in the same hash faster than trying all messages.

Problem statement 2: The function names should be the same in the libsodium bindings for all languages. XOR is a logic operation, not a stream encryption function.

It is worth thoroughly reading the documentation, and probably some tutorials about encryption in general. Some of what you're confused about (hashes vs encryption) is very basic, a bit like someone not knowing the difference between equality comparison (==) and assignment (=) and wanting to implement binary search. It makes it a bit difficult for me to formulate a useful answer. There is NOTHING WRONG with not having learned this stuff yet, it's not obvious or generally taught in school. If you want to learn a lot of this I suggest Dan Boneh's coursera course. It's a free graduate level course.

TL;DR: You probably want crypto_secretbox_easy(), though I'm not totally sure based on your short description.


What are the advantages of a static ECDH key?

Well, the advantages of static-ephemeral ECDH (and, they apply to DH as well):

You get one-way authentication for free.  That is, if Bob has Alice's public ECDH key, and uses it to talk to someone, Bob knows that that someone is Alice, without doing any further checks.  Now, Alice has no idea who she's talking to; on the other hand, for some scenarios, Alice really doesn't care.
You don't need a reply from Alice to get her ECDH public value; you already know it.  This may allow you to use one fewer protocol round (depending on what else needs to be done on the protocol).  In fact, if all Bob wants to do is share a symmetric key so he can send Alice a message, he doesn't need any replies from Alice at all; he can generate his public value, and the message encrypted and authenticated with a key derived from the shared secret.  Doing this is actually known as the Integrated Encryption Scheme; if this is what you're doing, you might want to look at the standards (as people have thought through the details)

Of course, there are some downsides:

It means that Bob has to get Alice's public key in a way that is authenticated.  If that means that Bob has Alice's key in a database, well, there are some practical questions with that (such as when Alice creates a fresh key, how does Bob hear about it).
If Alice does care who she is talking to, that means Bob needs to authenticate himself.  If you need to do this, you lose some (but not all) of the advantages you get from preconfigured keys in the first place.
You lose the Perfect Forward Secrecy properties that are normally associated with DH; you may or may not care depending on your security assumptions.  That is, if someone gets their hands on Alice's private key, then they can not only impersonate Alice, they can go back and decrypt previous sessions.


The "hard part" about GCM implementation is resistance to side-channel attacks, especially cached-based. GCM is the combination of AES-CTR, and a custom MAC that relies on multiplications in a binary field (GF(2128)). Efficient implementation of that operation classically uses tables, which can lead to cache-timing attacks because the accessed table slots will depend on the secret data (though cache-timing attacks have never, to my knowledge, been spotted "in the wild", they work very well in lab conditions so the common wisdom is that they are a plausible threat).

If you have a recent enough x86 CPU then you have the AES-NI opcodes, which help for AES but also for multiplications in binary fields, making GCM both resistant to side-channel leaks and very efficient. But smaller devices do not necessarily have the luxury of such a hardware-assisted implementation. In fact, it may be argued that performance is much more likely to be an issue on small embedded CPU (say, the low-end 32-bit ARM CPU) than on big PC, where encryption only uses a small fraction of the available computing power.

For small CPU, Poly1305/Chacha20 will be faster, with a smaller footprint, and more resistance to side-channel attacks. Techniques for making a constant-time implementation of AES are still applicable (like the Kasper-Schwabe implementation) but will offer lower performance because a 32-bit small CPU has only 32-bit registers (the Kasper-Schwabe code uses bitslicing techniques to run 8 parallel AES instances over 128-bit registers, but with 32-bit registers this goes down to 2 parallel AES instances). For the binary field part, one can use plain integer multiplications, but with most bits cleared to avoid problems with carries, so there will be a lot more multiplications than with a prime-field based MAC like Poly1305.

GCM is there to stay because it got NIST blessing and thus made its way to many standards; it even convinced CPU vendors to include specialized opcodes, and this in turn will reinforce its position.

Meanwhile, research on AEAD modes is still active, and there is an ongoing competition with interesting candidates (e.g. NORX). Thus, while there is a bit of dissatisfaction over GCM because of implementation issues, the succession is still open. Poly1305+ChaCha20 got a little headstart by being there first, but that does not make it an automatic fallback.

A common problem to both GCM and Poly1305+ChaCha20 is the need for a non-repeating IV. Such an IV is easily managed in the context of a streamed protocol (such as SSL/TLS) but it can be a source of trouble for encryption of independent messages -- IV reuse is a mortal sin and is not easily tested for in a given implementation. An IV-less encryption system would need to be a two-pass method (which is not necessarily a problem for encrypting messages); a possible candidate would be a counter-intuitive MAC-then-encrypt construction, with (say) HMAC computed over the plaintext, and the HMAC value being used as IV for AES-CTR encryption.


Where can i find relative software for differential cryptanalysis?

Not to my knowledge. Here is a possible explanation: non-trivial differential attacks are rather difficult to find in a fully automated way, and most of the time, one requires some (human) insight from a cryptanalyst before beginning to write some software.

Another explanation could be the following: cutting-edge differential attacks (like against SHA-3 candidates, for instance) are performed by world-class crypto researchers, and the competition (being the first to publish) is rather rough. So, people do not take the time, or are not always willing to share their software with everybody.


Is ECB mode safe to use with RSA encryption?

It is highly misleading to call how RSA Encryption is used as 'ECB mode'.

With ECB mode, we break the plaintext into N bit segments, and send each one through the block cipher separately.  The block cipher is deterministic, and so if two plaintext blocks happen to be the same, so will the corresponding ciphertext blocks.

Now, with RSA encryption, we take the short message, and some randomness, stir them together (using a padding method), and send that through the RSA primitive, resulting in the ciphertext.  If we encrypt the same message again, well, we'll stir in different randomness, resulting in a different looking ciphertext.  Hence, we avoid the problems inherent with ECB mode (and thus it is rather inappropriate to call what we do with RSA 'ECB mode').

Now, some closing comments:

The above assumes that you are using a known-good RSA padding method, such as OAEP.  If you aren't, and are instead using 'textbook RSA' (which is just to take the message, interpret it as a large integer, and send that to the RSA primitive), then there are a number of security problems you can run into, in addition to determinism.  If that is the case, you definitely need to fix it.
Someone could devise a CBC-type mode for doing RSA encryption (by breaking up the message into separate blocks, and doing an "add mod N" of the ciphertext of one block to the plaintext of the next).  We never do so, because of efficiency - if we ever need to RSA encrypt a long message, a far more efficient approach would be to pick a random (say) AES key, RSA encrypt the AES key, and then AES encrypt the actual message with the AES key.  Because AES is far more efficient than RSA, this is faster (and we retain the only-someone-with-the-private-key-can-decrypt property of pure RSA).


Is RSA-OAEP secure against Shor's factoring algorithm

If so, then make the seed >128-bit and be safe from Shor. Then, why there are so much fear of Shor's algorithm for RSA?

Well, remember that the assumption in the original question was that we kept the RSA public key secret.  That is a nonstandard assumption; we generally assume that the attacker knows the RSA public key (and in practice with most uses of RSA, he can easily learn it).
And, with knowledge of the RSA public key, Shor's algorithm can efficiently break it (assuming a reasonable sized Quantum Computer, of course); that is, he can learn the private key (and then do anything that the legitimate owner of the RSA private key can do) - the RSA padding mechanism does not offer any additional protection.


Shamir Secret Sharing - How to reconstruction secret? Example

But for another three share holders is can't reconstruction secrete.

Sure they can.

In the field $GF(17)$, we have:

$$\frac{43}{3} = \frac{9}{3} = 3$$

because $43 = 9 \pmod {17}$, and $3$ is the value that, when multiplied by 3, gives us 9 modulo 17.

And, we have:

$$\frac{23}{2} = \frac{6}{2} = 3$$

beause $23 = 6 \pmod {17}$, and $3$ is the value that, when multipled by 2, gives us 9 modulo 17.

Remember that, when we work in a finite field, division isn't exactly the same as it is when we're working with in $\mathbb{R}$; for example $\frac{1}{2}$ is not 0.5 (which is meaningless in $GF(17)$, but instead it is 9.


Clearly, your code is not SPA safe.
The if condition over a sensitive bit will certainly leak in timing. The time taken by a square is slower that a multiplication due to this if condition.
Exemple: bit 000 will induce a Square Square Square in term of cpu instruction will have less than a bit 100 where you will perform Square Multiply Square ...
Try to compare couple of operations instead of individual.

Regarding, the difference between a square and a multiply it depends on the chip you are working on, does modular operation are provided by a crypto processor? In this case, some countermeasures might have been implemented to avoid differences between a multiplication and a square.

You can share your traces if you like.

edit

Here is two SPA safe algorithm

Atomic The most elegant SPA safe algorithm, imo http://bcm.crypto.free.fr/pdf/CCJ04.pdf Fig2

The Montgomery Powering Ladder  Less efficient as it is a square and multiply always (trash multiply for square) https://www.iacr.org/workshops/ches/ches2002/presentations/Joye.pdf


On an EKE (Encrypted Key Exchange) what would happen if asymmetric key would be symmetric?

On EKE where the user sends a password encrypted public key and receives a password encrypted and public key encrypted secret key.

That's not the original meaning of EKE (which was a password encrypted Diffie Hellman exchange), but the above modification makes sense (if perhaps a bit dangerous), and so lets consider what would happen if we replace the public key encryption with a symmetric one.

In your revised scheme, the Client (Alice) would select a random symmetric key $K$, encrypt it with the password to form $E_{password}(K)$ and send that.  Then, the Server (Bob) would decrypt the ciphertext (using his password) to recover $K$.  Bob then picks a secret key $S$, and encrypts it with both the Alice's symmetric key $K$, and the password, forming $E_{password}(E_K(S))$.  Alice then unwraps $S$, and uses it somehow, perhaps to encrypt a message to Bob.

Now, consider someone listening it; they here $E_{password}(K), E_{password}(E_K(S))$, and $E_S(\text{known text})$.

The don't know $password$, however if they have a guess of the password $password'$, they can attempt to decrypt $E_{password}(K)$ with $password'$, coming up with a value $K'$ (and $K = K'$ if his guess was correct, that is, if $password = password'$).  Then, they can attempt to decrypt $E_{password}(E_K(S))$ with $password'$ and $K'$, resulting in $S'$ (and, again, $S = S'$ if his original guess was correct).  He can then attempt to decrypt $E_S(\text{known text})$; if he original guess is correct, then he will decrypt it properly, and so it will be obvious that his guess was correct.

This is entirely passive, and hence if he has a large dictionary of potential passwords, he can run this logic on each password.  If the correct password appeared somewhere in the dictionary, he'll find it (and then be able to listen into the entire conversation).

This doesn't happen with EKE (either version); if Alice encrypts a random public key, even if the correct password would recover it, he can't use it do decrypt Bob's reply.


How do you calculate the linear approximation of an S-BOX?

You might want to check out this stackoverflow question: What is Bit Masking?

Basically, the mask selects certain bits from the words, where a word is a vector (a row) of bits. The input mask selects certain bits from the input word, and the output mask selects certain bits from the output word.

The goal is to find a set of output bits that can be expressed as a linear combination of input bits with the highest probability. "A linear combination" in this case basically means no bitwise AND/OR gate are present in the expression, only XOR gates. This is relevant because when you have something like $\text{out} = a \oplus b \oplus k$, where $\oplus$ is XOR, then you can trivially solve for $k$ by computing $k = \text{out} \oplus a \oplus b$.


Present an attack for the combination of OTP and textbook RSA

This scheme follows the KEM/DEM approach of contructing secure asymmetric encryption schemes. However for a KEM/DEM PKCS (public key cryptosystem) to be secure it is required that both the key encapsulation mechanism (KEM) and the data encapsulation mechanism (DEM) are CPA or CCA secure for CPA or CCA of the whole scheme.

Indeed the DEM looks CPA secure as it is an OTP. The KEM scheme may be CPA secure, but I can't prove it now. Somebody else may be able to do this though. However the whole scheme isn't CPA secure as pointed out by Yehuda Lindell in the other answer.

But neither of the part is CCA secure. I'll present two attacks breaking this scheme by attacking the KEM and the DEM in isolation.

Attack 1: Breaking the DEM

The DEM is basically a simple OTP. Now let's assume you're given the ciphertext $c=(u,v)$ to be broken. First choose a random $s$ and construct $c'=(u\oplus s,v)$. Note that $c'\neq c$ so asking the decryption oracle for decryption of $c'$ is valid. Obtain the decryption $m'$ of $c'$ using you decryption oracle. Note that $m'=(m \oplus r \oplus s) \oplus r=m \oplus s$, now finally obtain the message $m=m'\oplus s$. You have successfully broken the DEM in a chosen ciphertext attack.

Attack 2: Breaking the KEM

The KEM is simple textbook RSA. However interaction is a bit more tricky here but still quite simple. Let's again assume you're given a ciphertext $c=(u,v)$ to decrypt. Now choose a random $s$ again and construct the ciphertext $c'=(t,v\cdot s^e\bmod N)$ with $t$ being a random message, note again that $c\neq c'$ so asking for the decryption of $c'$ is totally valid. Ask your decryption oracle for the decryption of $c'$ and learn the corresponding message $t'$. Note that $t\oplus t'=r'=r\cdot s$. Finally reconstruct the original $r=(t\oplus t')\cdot s^{-1} \bmod N$ and reconstruct the message as $m=u\oplus r$. You have now successfully broken the KEM.

So you see that this scheme is totally flawed in a chosen ciphertext setting and message recovery is quite easy.


Is 512-bit RSA still safe for signature generation?

I don't have any experience with this myself, but Tom Ritter talked about this on twitter:

Matthew Green: Out of curiosity: do you happen to know offhand how much it costs to factor a 512-bit RSA key on EC2?
Tom Ritter: My personal costs are \$120-\$150 with my setup. You can probably do it cheaper, heard reports of \$75.

He also published a description of how to factor RSA moduli.

Another project in a similar vein: Factoring as a Service:

The Factoring as a Service project is designed to allow anyone to factor 512-bit integers in as little as four hours using the Amazon EC2 platform for less than $100, with minimal setup.

You should be able to just run the scripts from their github.


GOST symmetric cipher uses 256-bit keys to encrypt 64-bit blocks. That means there are many keys which give the same result

This is actually incorrect. A block cipher, when given a key, maps $n$-bit plaintext blocks to $n$-bit ciphertext blocks (and vice versa for decryption). Here's a toy example for $n=2$:

  $E_k(00) = 01 \\
E_k(01) = 10 \\
E_k(10) = 00 \\
E_k(11) = 11$

Although there are $2^n$ possible plaintext blocks and $2^n$ possible ciphertext blocks, there are actually $2^n!$ different possible ways to map plaintext blocks to ciphertext blocks. In this toy example, there are actually $2^2! = 4! = 1\times2\times3\times4 = 24$ different ways of mapping each two-bit input to a unique two-bit output.

Back to your question, GOST uses 256-bit keys, meaning that there are $2^{256}$ possible keys. However, with a 64-bit block size, there are $2^{64}!$ different possible permutations, and $2^{64}!$ is much larger than $2^{256}$.


Does piping MT19937 random stream into SHA512 make the state of MT unrecoverable in practice?

The main issue would be the MT seed size. MT has a large enough state, but the seed is generally just a 32 bit word $w$. See here for more information.
SHA on the output won't guard you from a brute force attack on the seed; an attacker can just try and generate the stream and perform the SHA calculations and compare.
So you need to somehow extend the seed size and initialize the state. The state is pretty large and MT has a large period, so the plumbing is already there. If you can then just call it MT is the obvious next question.

Is there any real practical way to obtain the MT state in this setup and hence be able to predict next blocks?

Yes, as the initial state is derived from a generally small seed.

Or maybe prediction is somehow possible without state recovery?

I don't see that happening, but if you can retrieve the initial state, then you don't need to go there.

I have read that there are CSPRNG designs that use an MT generator internally. Do they work like this, just take an MT stream and obfuscate it in some way or are they completely different?

I haven't heard of them, but if they don't allow for a large seed as input, then they're in trouble.

The final question is indeed if you have gained anything when you're finished. Plenty of DRBG's based on hash functions exist, and adding a fast PRNG at the backend may not make much sense. The large state would not sit well with many cryptographers and secure software / hardware developers either.


You run the algorithm with two different plaintexts (whose difference is usually small – just a few bits, everything else being equal).

Wherever these plaintexts lead to different inputs to an S-box (in any layer/round of the algorithm), we call this S-Box “active” (since the other S-boxes produce the same result for both plaintexts, they are called “passive” and are not considered further).


Apply your formula, perhaps simplified as $\ln(2^x)={x} \ln(2)$, so for 1536-bit numbers about one in $1536 \ln(2)$ are prime. In the case of $1{,}000{,}000=2^{20}$ (approx.) the number of primes is about one in $20 \ln(2)$.


How secure is SHA1? What are the chances of a real exploit?

Actually SHA-1 has been "officially insecure" for a longer time, since an attack method was published in 2011. The 2017 collisions was just the first known case of actually running the attack. But everybody was already quite convinced that the attack worked, and, indeed, the 2017 collision was produced with the expected computational cost.

The important point is that we are talking here about collisions. A collision is when you find two distinct messages that are hashed to the same value.

In many protocols, collisions don't matter; what is important is the resistance to second preimages. A second preimage is like a collision, except that the attacker does not get to choose one of the messages; the attacker is challenged to find a colliding pair of messages, the first one being fixed. Finding second preimages is a lot harder than finding collisions. For a "perfect" hash function with a 160-bit output (like SHA-1), a collision can be found with effort 280, while finding a second preimage requires effort 2160 (i.e. a million billion billion times more). Moreover, while a structural weakness is known in SHA-1, that allows lowering the cost of the collision attack from 280 to 263, making it merely "very expensive", no such weakness is known that would help for second preimages.

So right now, SHA-1 seems still very very robust for second preimages, and any protocol that uses SHA-1 and relies on second preimage resistance can keep on doing so safely for the time being.

The tricky issue is to determine if a given protocol relies on second preimages, or if collisions can impact it. SAML is a complicated beast. It seems that it uses SHA-1 in conjunction with digital signatures, and this relies on second preimages, except in situations where attackers can get to choose part of the data that is being signed, in which case they might want to exercise a collision between "innocent-looking data" and malicious data. In the case of the published SHA-1 collision, this is done with PDF files because the PDF format is flexible enough to turn an difference in only a few bits into an arbitrary visual effect.

The cautious course of action would be to migrate to SHA-256. There is no absolute urgency to do so; but if ten years from now you still use SHA-1, then this means that your software management is terrible (and this is much more likely to be an issue than SHA-1 weaknesses).


Elliptic Curve Isogenies, Frobenius endomorphism relation to characteristic equation

I have struggled with this proof, but here is how I tried to reason through it:

The Frobenius endomorphism can be represented by a $2 \times 2$ matrix over the torsion group $\mathbb{E}[\ell]$.  You may as well raise $\phi$ to some $r$ power, $\phi_q^r$, and get an eigenvalue equation for this matrix.

You get a subgroup $C$ of $\mathbb{E}[\ell]$ such that $\phi_q^r (P) = \kappa P$ if the characteristic equation has a root $\kappa$. From Vélu's formulas, we can build an isogeny from $\mathbb{E}$ to another elliptic curve $\mathbb{E}'$ such that the kernel of the isogeny is $C$. The Frobenius endomorphism only permutes the points in $C$, leaving the $j$-invariant of $\mathbb{E}'$, well...invariant.

So the $\phi_q^r$ define a subgroup / eigenspace that can, via Vélu, generate an isogeny where it's the kernel.

More discussion:

Are you familiar with Vélu's formulas? They may be the missing link for you. Basically: assume you have an elliptic curve $\mathbb{E}$ over some field $\bar{K}$, and let $C$ be a finite subgroup of  $\mathbb{E}(\bar{K})$. Then, Vélu tells you that there is another group $\mathbb{E}'$ and an isogeny $\chi:  \mathbb{E} \rightarrow \mathbb{E}'$ such that $C = \text{Ker}(\chi)$. They even explicitly give you a formula for the isogeny!
A homomorphism from  $\mathbb{E}[\ell] \rightarrow  \mathbb{E}[\ell]$ is represented as a $2 \times 2$ matrix (the points of $\mathbb{E}[\ell]$ are "$\ell$-torsion points") (page 233)
If the number points on a curve satisifies $ \#\mathbb{E}(\mathbb{F}_p) = p + 1 - a$, then the Frobenius endomorphism $\phi_q$ satisfies $\phi_q^2 - a \phi_q + q = 0$ (page 234).

So, the Frobenius endomorphism acting on the $\ell$-torsion, $\phi_{q;\ell}$ can be represented as a matrix:

$$ \phi_{q;\ell} = \begin{pmatrix}
\lambda & b \\
0 & \mu \\
\end{pmatrix}$$

Its characteristic polynomial is

$$ \begin{vmatrix}
\lambda - T & b \\
0 & \mu - T \\
\end{vmatrix} = (T-\mu)(T-\lambda) \equiv 0 \bmod \ell$$

So a root $\lambda$ here satisfies a subgroup of $\mathbb{E}[\ell]$, $C$, such that for all the points in $C$, $\phi(P) = \lambda P$. Raising $\phi_q$ to some $r$ power will just give you another eigenvalue equation, say $\phi_q^r(P) = \kappa P$. From Velu's formulas, we can define an isogeny such that $C$ is the kernel of the isogeny, and $\phi_q^r$ just permutes all the coordinates of points in $C$, leaving the parameters of the equation for $\mathbb{E}'$ alone. That means the $j$-invariant of $\mathbb{E}'$ is left alone too.


Encrypt a single file, chunk-by-chunk, each chunk using different key (AES)

Step 1: good job, this is the right way. You can also use bcrypt or scrypt for extra resistance. Make sure you have chosen sufficiently strong parameters, that is, 64-bit salt and 10000 rounds absolute minimum.

Step 2: no! once you have a strong derived master key, you don't need to apply PBKDF2 on any keys derived from this master key. You are just wasting time and effort and it doesn't scale at all. Use HMAC with a random nonce and keyed with the master key.

Step 3: Why not just encrypt the whole file with a single (derived) key? Why would you want to split the file into chunks? If you do have a good reason, ignore this.

Step 4: I.. suppose.

Step 5: Yeah.

Is my design flawed? Well I won't lie to you, it is a bit weird. You don't need to split the file into chunks if you just want to encrypt it. You are making it needlessly complex. Unless you have good reason. Now the real problem is you have no mechanism in place for integrity checking and authentication. That is BAD.

Or is my design totally pointless and extra? Frankly, yes, it is.

Any else comments are welcomed. Do not design your own real world cryptosystem. Either you do it the simple way and have someone competent (or better yet, multiple) look over it  before deploying it, or don't do it at all. Mindlessly throwing cryptography at a problem isn't the right approach.

The problem I have with this question is that you have no clear goal in mind. What are you protecting against? What is your threat model?  Where is the database stored? Who or what  will access it? etc..

Without knowing this, "extra security" doesn't mean anything. More secure than what, against what?

TL;DR: design is flawed and over-engineered, designer should not be designing cryptosystems for real world use (though it's fine to experiment, of course). Best use an existing file encryption scheme (there ought to be millions for Android, but OpenSSL will do fine) and store metadata in a secure database.


Is a MAC a valid way to ensure tamper-resistance?

First, you have to check if the HMAC integrity check complies to the governmental standard. In the USA, for instance, you have to check the FIPS specifications.
If that has been clarified then here are my answers:

  is this a valid use case for a MAC?

Yes.

  Are there any major or minor flaws with this technique?

The one you already stated.

  Is it OK to reuse the same HMAC key forever?

That is seldom a good idea, due to the "break once run everywhere" scenario.
I would instead use a Key derived from a Masterkey. The Key is on the database and the Masterkey on an seperate isolated device. From time to time you should change the Key by a new derivation form the Masterkey and some well known data.

  Would an asymmetric or AEAD solution be preferable?

An asymmetric solution makes less sense here, because you have to store the private key on your database system anyhow.


Is it possible to have 11 rounds with an AES of 128 bits?

I don't understand why I have 11 rounds? What is the role of the 11th round?

I suspect that they are doing standard AES-128, and thus have 10 rounds.

By '11 rounds', I suspect they mean '11 subkeys'; AES uses one more subkey than it has rounds.

  Let's suppose that I want t attack the 10th round, must I compute the 10th ciphertext?

I rather suspect what's actually needed to perform the attack will depend on the details of the attack.  On the other hand, without the final subkey, you can't compute the intermediate cipherstate (and if you knew the final subkey, that'd give you the entire key anyways).

I suspect that it's easiest, for a DPA-style attack, to attack either the first or the last subkey; those subkey bits satisfy the equation $S = K \oplus I$, where $S$ is one of the subkey bits, and $K$ is a bit you know (it's either a plaintext bit or a ciphertext bit), and $I$ is a bit of the AES internal state; if you can find a correlation with $I$, you can recover $S$; recover enough $S$ bits, and that's the game...


Trying to better understand the failure of the Index Calculus for ECDLP

You're essentially correct. Index calculus is impractical on elliptic curves because there is not a straightforward notion of smoothness in these groups.

In prime fields, there is the easy mapping from the multiplicative group to the integers, where smoothness is well-defined. Similarly, in extension fields there is the mapping to polynomials over the ground field, where smoothness is given in terms of irreducibility.

In elliptic curves there is no such simple mapping. One can't use decomposition into prime divisors, as in hyperelliptic curves, since every point is a prime divisor. One possible solution, as you have pointed out, is to try to lift the elliptic curve into $E(\mathbb{Q})$ or $E(\mathbb{Q}_p)$; this approach is full of obstructions, however, and has proven not to be very productive yet. The survey by Joe Silverman explains some reasons why.

Another approach is to try and decompose points into sums of a special pointset within the elliptic curve group itself. This is the summation polynomial approach of Semaev, but it only seems to work well for curves over extension fields, where the Point Decomposition Problem is tractable. Note also that recent advances have shown that in binary curves index calculus is actually asymptotically feasible.

Apart from direct attacks, there are some other ways to solve elliptic curve discrete logs using index calculus for special curves. The MOV attack uses the Weil pairing to map the logarithm to an extension field, where you can use the regular index calculus algorithms. The GHS attack maps the logarithm to a logarithm on a hyperelliptic curve of hopefully low genus, where index calculus attacks are also efficient.