Difference between oracle behavior and real execution

The point why a simulation must not deviate too much from the real game is due to the following reasoning. You assume you have an adversary that wins the original game, but you do not know how the adversary acts if you deviate from the behaviour of the real game and the adversary can notice this. Exactly because you make no assumption whatsoever about the adversaries behaviour when encountering a behaviour in the simulation that is not covered by the real game. If the adversary can now always force your simulation to deviate from the real game, then you cannot use the adversary anymore as you cannot predicts its behaviour anymore (e.g., you simply have to abort the simulation every time since you cannot answer queries of the adversary and you do not know what the adversary does if you can not answer a query).

If your simulation fails with a probability that is non-negligible, then this is not a problem per se. What you need is to estimate the probability that an adversary causes a simulation to fail. Typically, proofs try to somehow partition the set of potential queries into those that are answerable and those that force the simulation to abort. For instance, assume that this partition is randomly defined according to some distribution and the simulation does not leak any information on which queries would be bad, then the adversary has no better strategy than "accidentially hitting" a query in the wrong partition and you can easily estimate its probability (as it is independent of the adversaries behaviour).

For instance assume you as a simulation have to guess that the adversary does not query 1 in $n$ possible things, because you cannot answer this one query. Think for instance  (i.e,. you have partitioned such that you have $n-1$ queries that are good and 1 bad query). Now, if you randomly choose $i\in [n]$, then the adversary has no better strategy than accidentially hitting $i$ (i.e., the simulation is exactly as in the real game except the unwanted event happens and let us assume that this event is independent from the other things the adversary sees in the simulation). Then for every query the probability of an abort is $1/n$ and if the adversary makes a polynomial number of queries you just loose tightness in the reduction (you condition on the event that the adversary does not hit bad in all queries). Now, the simulation will always abort with the same probability irrespective of the adversaries strategy and you are fine. A nice brief discussion on how to formally model this can be found in Alex Dent's A Note On Game-Hopping Proofs. But actually the reasoning and the calculations are very simple. Note that also here there is a difference in the behaviour of the oracle in the real and simulated game and this does not mean that the proof does not make a sense.

However, if any adversary can always force the simulation to abort, then you have a problem. The problem as with Waters proof is that the probability of the adversary causing an abort of the simulation is not independent of the adversaries behaviour (as above). So he cannot relate the winning probability of the adversary and the reduction meaningfulle. Thus, he has to introduce this complicated artificial abort technique. As you already mention, can be avoided when using the strategy of Bellare and Ristenpart.

If you have a problem with a specific proof it may be easier to ask a specific question. I am not sure if my edit helps you.


Can you help me with this Random Number Generator function?

The classical way to generate a random permutation is the Fisher-Yates shuffle; it takes an underlying random number generator, and produces a random permutation.  With just a bit of care, it can generate each permutation with equal probability (assuming the underlying random number generator outputs are independent and uniformly distributed).

The only downside is that the algorithm requires N to be small enough so that you hold the entire permutation in memory; that doesn't sound like that's a problem from you.


Is 128-bit security still considered strong in 2020, within the context of both ECC Asym & Sym ciphers

I strongly disagree with saying that AES-128 is broken, in any way, shape or form, and likewise ECC with 256-bit keys. Note that even in this answer by @kelaka regarding AES-128, you would need over 34 million years of the entire bitcoin mining power to carry out a computation of $2^{128}$. This is far from broken. If quantum computers ever happen at scale, it is very very unclear how long it would have to actually run to achieve $2^{64}$ quantum computations for AES-128 (but ECC-256 would be in bigger trouble). Bottom line, these are far from broken. (I don't know what Schneier quote you are referring to, but anyway I completely disagree.)


Encrypting text file line by line with stable encryption

Yes, it's possible. Encrypting each line independently, like you suggest is the way to go.

Most likely you will want to use a symmetric encryption algorithm independently for each line – i.e. have a new unique IV/nonce per line. That's the simplest to implement. However, it means every line is up to 128 bits longer. If you can't live with that, you practically have to either sacrifice some security (e.g. use ECB mode without semantic security) or have changes to one line affect nearby lines as well.

One question to consider is whether to use authenticated encryption to guard against an attacker being able to modify the file. This is usually the way to go, but if you have something that ensures integrity at a higher level in your setup (signed tags/commits, say), you could afford to skip it.

For authenticated encryption you need to further decide whether you want a single MAC for the whole file (slower, since it needs to be recalculated after every modification) or one per line (which takes even more space).

In practice, I would go with AES for encryption. (Either 128-bit or 256-bit keys – doesn't matter much in practice.)

If you can live with the extra space it requires, the absolute simplest from an implementation standpoint (when you have a library that supports it), is to use AES in GCM mode. You get both encryption and authentication in one, and the only requirement for IVs is uniqueness. Each line will be up to 256 bits longer (when using 128 bits for both IV and auth. tag).
If you have authentication already, I would go with AES CTR. If you know the file will never have more that $2^k$ lines through its lifetime (counting each version of each line) you could store a $k$-bit value per line instead of a full 128-bit IV. You will need to make sure you never reuse a counter value in any case, including different "forks" of the file.
If you need a MAC for the file, you can do the above and append an HMAC.


Derive a public EC key from two public EC keys

As long as there is a probability that the adversary has the access to a valid signature on the message $m$ using one of the private keys, none of the schemes would be secure, and also any other scheme which is using a linear combination of the keys as the resulting private key.

Because, if an adversary has two valid ECDSA signatures on message $m$ which one is made by private key $a_1$ and the other is made by private key $a_2$, she can produce any signature on message $m$ using the private key $c=b_1a_1+b_2a_2+b_3$ where $b_1$,$b_2$ and $b_3$ are known to the adversary. This is due to the homomorphic properties of Elgemal signature.

So other than the algorithm #2 the algorithm #1 (Addition) seems to be unsecure. Whereas, If an adversary has a valid ECDSA signature on message $m$ using private key $a_1$ and she knows $a_2$ then it can produce a valid signature on message $m$ using private key $c=a_1+a_2$ quit efficiently. In other words for breaking the scheme it suffices to have just one of the private keys, say $a_2$, and a valid signature produced using the other private key, say $a_1$.

For making the answer more concise, I'm using the notations in Wikipedia article ~ "Elliptic Curve DSA".

assume the signature on message $m$ made using private key $a_1$ is $(r,s)$ and the forged signature made for private key $c=a_1+a_2$ is $(r',s)$.

$(r,y_1)=kG=zs^{-1}G+rs^{-1}a_1G$

$(r',y_1')=(r,y_1)+rs^{-1}a_2G$


How to find the base point given public and private key and EC parameters except the base point

Most standardized curves has a base point $G$ of prime order $q$ so computing the inverse of $k$ (the private key) modulo $q$ can be easily done as
$$
k_{\text{inv}} = k^{p-2} \bmod q,
$$
thanks to Fermat's Little Theorem since
$$
k_{\text{inv}}\times k \equiv k^{p-1} \equiv 1 \pmod{q}
$$
In the case the order is a composite integer $n$, then Euclid Extended algorithm is a good way to find it.
In your problem you have a public point $P_{\text{pub}}$ such that
$$
P_{\text{pub}} = [k]G,
$$
and you only know $k$ and $P_{\text{pub}}$. To find $G$, use of the above algorithm (if the order of $G$ is known) to find $k_{\text{inv}}$ and we have
$$
G = [k_{\text{inv}}] P_{\text{pub}}.
$$


How can a good pseudo-random number generator be made?

There are two answers, really depending on your specifications and how your generator will be evaluated.

If all you need is to have a PRNG with statistically excellent random, but really don't care about predictability or cryptographic considerations, go for something simple like a Mersenne Twister.

If you actually need some effective stream-cipher, look up on existing ciphers. Yet again, I'd go for something simple, like using an AES in CTR.

Note: If you intend to use your solution for any real usage crypto, then by all means please read papers & think about using an existing solution, yours will most likely not be error-proof in the implementation


Is this problem based on discrete polynomials modulo $(x^3-1)$ strong?

Here's the isomorphism:

$ax^2 + bx + c$ (with $z$) maps to $ax^2 + (b + z - z')x + c$ (with $z'$)

The only nonobvious thing about this transform is that it preserves $f$, that is, that $f(A, B)$ (with $z$) is the element that maps to $f'(A', B')$ (with $z'$, and $f', A', B'$ are the mapped versions of $f, A, B$)

However, this is not hard to show; we notice that the constraints $ax^2 + bx + c = -z \pmod {x-1}$ is equivalent to $a + b + c = -z$.

With this in mind, if $A = ax^2 - (a+b+z)x + b$ (setting the linear term to the value it must be for it to be consistent with the constraint), and if $B = cx^2 - (c+d+z)x + d$, then $f(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z)x + (2ad+2bc+ac+bd)$

If we consider the mapped version of those two elements $A' = ax^2 - (a+b+z')x + b$ and $B' = cx^2 - (c+d+z')x + d$, then the mapped version of $f'$ would have $f'(A, B) = (bd -2ac – ad – bc)x^2 - (-ac+ad+bc+ad+z')x + (2ad+2bc+ac+bd)$

We can see that the element $f(A, B)$ maps to the element $f'(A', B')$, hence the isomorphism is preserved.


You seem to be confused a bit. You're talking about three or four distinct things here. At one side, you have RSA. On the other side, there's DSA and ECDSA, which are more or less based on the same cryptographical ideas. Then you talk about group signatures.

Your first question is about RSA

  How do I guarantee that two systems/users have not picked the same private key? Would it matter if they did?

Two different users generate two different keys, by picking random primes $p$ and $q$, both having a bit length around $\log(n)/2$, such that the product of them ($n=pq$) will have length $\log(pq)=\log(p)+\log(q)=\log(n)$. Let's see how many primes there are for an RSA system of 4096 bits. According to Wikipedia, the prime counting function $\pi(x)$, which computes the amount of primes smaller than $x$ can be approximated by $$\pi(x)\approx\frac{x}{\ln{x}}$$. We need primes of length 2048, so we need to substract around $\pi(2^{2047})$

\begin{align}
\pi(2^{2048})-\pi(2^{2047})&\approx\frac{2^{2048}}{\ln{2^{2048}}}-\frac{2^{2047}}{\ln{2^{2047}}}\\
&=\frac{2^{2048}}{2048\ln{2}}-\frac{2^{2047}}{2047\ln{2}}\\
&=2^{2037.5}-2^{2036.5}=2^{2036.5}
\end{align}

That's a lot of primes to choose from. This basically guarantees that no two RSA secret keys will ever be the same.

  Are group signatures possible with DSA or ECDSA?

Let's recall what a group signature is, on an abstract level:
There's a group manager $\mathcal{Z}$, who chooses the group members (setup). The group members can sign a message, and a verifier only learns that the signature was created by someone in the group, without being able to pinpoint who it was. $\mathcal{Z}$ can optionally choose to reveal the original signer.

Now, DSA and ECDSA are two specific instances of a regular digital signature. These obviously aren't group signatures schemes, but regular digital signatures.

What you probably are asking about is whether it is possible to use the mathematical constructs behind DSA and ECDSA to create a group signature scheme, just like Chaum et al. constructed their scheme on RSA. (EC)DSA are based on the (elliptic curve) discrete logarithm problem(s). Indeed, there are a lot of proposed group signature schemes based on elliptic curve, as there are based on regular DH groups.

Also worth noting are ring signature schemes (RST, for example), which provide a similar but spontaneous construction, without a group manager (and thus without possible revealing of the original signer).


Applying machine learning algorithms to homomorphic encrypted data

Homomorphic Encryption on Reals
In theory, homomorphic encryption can be done on real numbers. This answer describes two options you have when dealing with real numbers or operations that will result in real numbers. Kristin Lauter is doing some of the cutting edge research in this area. In a recent paper, CryptoNets: Applying Neural Networks to Encrypted Data with High Throughput and Accuracy, the authors (which includes Kristin), state:

  One thing to note is that the encryption scheme does not support floating-point numbers. Instead, we use fixed
  precision real numbers by converting them to integers by proper scaling, although there are also other ways to do this
  (Dowlin et al., 2015).

They go on to say:

  The neural network takes as its input a vector of real numbers and, through a series of additions, multiplications, and other real functions, it computes its outputs, which are also real numbers. However, the homomorphic encryption scheme works over the ring $R_n^t := \mathbb{Z}_t [x] /(x^n + 1)$. This means that some conversion process between real numbers and elements of $R_n^t$ is needed.

So they are not operating on real numbers directly. Instead, they encode (using scaling as mentioned in the other answer I linked to). And then decode after decryption. III.B of the Dowlin paper discusses encoding methods for real numbers. Real numbers are encountered everywhere in data analytics, and so I expect there to be continued research into how best to operate on reals using homomorphic encryption. In other words, it is an active area of research and not something that you can just quickly pull a tool out of your hat and off you go. Some thought and care must be taken in making sure you aren't invalidating the analysis techniques by using some of the encoding methods that are out there.

Order-Preserving Symmetric Encryption
The claim in the blog post is

  Simpler schemes like order-preserving symmetric encryption also allow strong security in certain settings, and are easy to use with out of the box machine learning tools.

The author doesn't appear to go into much more detail than that, which leaves me wondering what they really mean. Order-preserving symmetric encryption is all about encrypting data in such a way that a natural ordering of the plaintexts is preserved. This allows you to, given only ciphertexts, do comparisons. This leads to useful operations. Specifically, the paper the post links to mentions range queries on encrypted numbers. The 2004 SIGMOD paper by Agrawal describes how their OPE scheme can be directly applied to IEEE 754 single precision floating point numbers.

Not being a machine learning expert, I can't tell you how useful only being able to do comparisons, operations like min and max, and range queries would be for machine learning. I guess if your machine learning tools require only range queries and comparisons, OPE could be used with "out of the box machine learning tools", but something tells me that would leave much to be desired in terms of data analysis.


Practical examples of Threshold Secret Sharing?

I worked on a secure document management project 20 years ago which used secret sharing. It is widely used in financial networks. Actual use cases with public details that are easily accessible include:

Threshold key sharing is used in Hardware Security Modules, for example to unlock the administrator account. In the Amazon CloudHSM documentation, this is explained in detail:
Amazon CloudHSM: About M of N
Hashicorp's Vault uses Shamir's Secret Sharing during the "unsealing" process as explained here: (https://www.vaultproject.io/docs/concepts/seal.html) This enables reading and decrypting secrets from the storage backend.


Why does the Fiat-Shamir heuristic not work without a random oracle?

Background: The Fiat–Shamir heuristic converts a certain class of interactive zero-knowledge proof systems—$\Sigma$-protocols, where prover proposes random commitment, verifier responds with random challenge, and prover answers with proof—into signature schemes using a random oracle to determine the challenge from the commitment.

Using a random oracle means that everyone has access to the same independent random challenge as a function of the prover's commitment.
The signer can pretend to have been given an independent random challenge in a simulated interactive zero-knowledge proof.
Everyone else can reproduce the interaction given the message and commitment with the same challenge, in order to verify the resulting transcript as a signature.

The ROM theorems of Pointcheval & Stern exploit $\Sigma$-protocols in which the proofs for two different challenges for the same commitment leak the secret key with high probability, and use that to show that a ROM forger can be used to leak the secret key.  The basic idea is the forking lemma:

If you have a forger as a Turing machine, you can pause it just before it queries the random oracle, duplicate the state of the machine (‘fork’ it, in the parlance of our times), and then run it forward twice with two different random oracles.
If the forger makes $q$ queries to the oracle, and you pick one of the $q$ queries uniformly at random to fork the machine, there's about a $1/q$ chance that you picked the query to the random oracle to choose the challenge—and hence about a $1/q$ chance that you got two different signatures with the same commitments but different challenges, leaking the key.

(The forger could also return a forgery without using the random oracle to determine the challenge, of course—but there is a negligible probability they will guess the challenge the random oracle would have returned, and if their guess is wrong, whatever they return won't agree with the challenge that all the verifiers will be using.)

The random oracle model is essentially a model for how forgers are designed.  That is, a ROM theorem is a statement of the form: If a forger is designed generically in terms of a hash function, then there is a way to break some underlying problem, using that forger as a subroutine.  The proof shows how to use that forger as a subroutine, by passing it specially crafted random oracles that have the correct distribution on outputs but also do nefarious things behind the scenes to exfiltrate the goods from the forger.

What Goldwasser & Kalai showed about Fiat–Shamir—much like Canetti, Goldreich, & Halevi showed about signatures in general—is that there exists a $\Sigma$-protocol such that there is a forger for the signature scheme obtained by using Fiat–Shamir heuristic with any particular hash function even if it is secure in the random oracle model, using a series of complexity-theoretic tricks to make $\Sigma$-protocols that throw tantrums when the challenges have certain forms, which a forger can exploit to forge signatures in a Fiat–Shamir scheme that uses any particular hash function.  Of course, the forger, in this case, is not written generically in terms of a hash function; although there exists a forger for any hash function, each forger itself depends intimately on the details of the hash function.

The tricks are elaborate and I won't go into details here, but the point is not that (e.g.) the Schnorr signature scheme is insecure—rather, it's that the Fiat–Shamir heuristic does not always produce a secure signature scheme given a secure $\Sigma$-protocol even if the signature scheme would be secure in the random oracle model.  So you can't formally draw the implication that a ROM theorem of Schnorr signature security guarantees a Schnorr signature forger can be used to compute discrete logs—but it would be rather surprising if Schnorr's identification scheme interacted with (e.g.) SHAKE128 to break the security of the signature scheme derived by Fiat–Shamir.


Tweaking textbook RSA to make the encryption a Pseudorandom function

This is not a secure pseudorandom function.  No tweak is going to make this a pseudorandom function.  After all, it is a public-key operation, so anyone who knows your algorithm can compute $f(m)$ given $m$.  Consequently, it cannot possibly be pseudorandom: there will always be a trivial distinguisher.

What are you actually trying to accomplish?  Why do you think you want a tweak to RSA that makes it a pseudorandom function -- what problem are you trying to solve?  I think you may need to step back from the specific mechanism you have in mind and think through what are the broader requirements of your particular application.  Once you've done that, we may be in a better position to help you solve your problem.


EEE and EDE are effectively the same in terms of security.  EDE is used because it is "backwards compatible:" by setting all three keys to be the same, it becomes equivalent to just single encryption (E) with that key.


Can a ciphertext be decrypted to 2 meaningful messages?

This is actually possible in practice because to us, human beings, a "meaningful message" can be a file.

Now, depending how we encrypt our files, we have more or less slack variables at hand to play around with the resulting ciphertexts.

Ange Albertini played a lot with file formats and he actually has a PoC where he encrypts given images into other files, even valid images... Or where he encrypts a JPG into a PNG if using AES and into a PDF if using 3DES... Or even worse!

(image by Ange Albertini, CC3.0BY)

How comes? Well, this is mostly done by abusing the way the modes of operation work, as well as the way the file formats work.

When you encrypt a file using AES CBC, for instance, you can choose your IV, which means that you can control the first 128 bits of your ciphertext. Furthermore you can also append any plaintext data at the end of your ciphertext, and it will get encrypted when you decrypt your ciphertext, but it also means that you can obtain its corresponding ciphertext so that it gets decrypted when you encrypt your plaintext appended with that ciphertext...

With this two details you already have plenty of room to play around with the file formats in a way that would produce valid files when encrypted/decrypted!

Now, a question that was not addressed by Ange is whether this is secure...
Well, as long as you are appending encrypted data or that you are not reusing your IVs, this does actually protects the content of your files (especially Ange's limited deniability example), as long as your secret key remain secret... (But it might be a problem in the case of CBC, depending on your use of the cipher, as it mandates most of the time the IVs to be unpredictable, unlike CTR where it suffices to have unique nonces.)

So, is it possible to do the same in the other direction, decrypting into two different files given different keys? Well, if you can have different IVs, then yes, it is possible using the same kind of tricks that Ange used.

In the end, is this related to the way the actual ciphers work? No, not at all. This is not a cryptographic property, but a consequence of the file formats' malleability.


If I want to securely delete this message is it enough to delete (overwrite with random) the IV, the first block, or both?

No, it's not enough.  Not even if you erase both.

(Not unless your message is at most two blocks long, that is.)

Erasing the IV makes the first block of the message undecryptable.  Erasing the IV and the first $n$ blocks of ciphertext makes the first $n+1$ blocks undecryptable.  In either case, the rest of the message can still be decrypted normally.

For modes other than CBC, the details may vary, but for all commonly used modes the conclusion remains the same: to ensure that no part of the message can be decrypted even if the key is compromised, you will need to erase the entire ciphertext (or the IV and almost all of the ciphertext, at least).


Why do we need Rekey (Use case of rekey cryptography)

I would say that rekeying is used in cryptography in order to limit the number of messages (talking about encryption and decryption here) that are sent from the same key. This is just a preventive measure to thwart the attacker from getting much information about the same family of messages (encrypted with the same key) by looking at the encryption of messages with the same key.
If you have heard about the standard security definitions of encryption schemes and the standard attacks, like ciphertext only attacks, chosen ciphertext attacks, etc. then you might know that if the adversary gets hold of many many messages encrypted with the same key then in some encryption schemes and in some use case scenarios, the adversary might get some information about the messages which he ideally shouldn't have.
Let me give you a very primitive example.
You might know what a caeser cipher is (if not, then look it up). In case of caeser cipher (or any substitution cipher), if the adversary sees a lot of messages, encrypted with the same key, then they can easily run a frequency analysis attack on the cipher to learn the key and then get the message in plain. Rekeying, very frequent in such cases, in such a case might at least prevent the attacker from getting enough information to run an attack like this or at least make it an attack more difficult to run.
Don't assume that this is how weak the modern ciphers are, they are pretty great at prevent many attacks, even more sophisticated ones like linear and differential cryptanalysis on DES and AES.
But still, if an adversary gets hold of $2^{43}$ known plaintexts then it can successfully cryptanalyse DES encryption (although because of this, DES is not used these days and it is replaced by AES and 3DES) meaning that if the adversary somehow knows the encryptions of $2^{43}$ messages, all encrypted with the same key, then it can find the key and decrypt all of the upcoming messages (if encrypted with the same key) by using Linear Cryptanalysis.
Now in the above case, if one puts a limit on the time for which a key is used, say for only $2^{30}$ messages, then the attacker will never get $2^{43}$ encrypted messages with a single key because the key will be refreshed or rekeyed after just $2^{30}$ messages and this prevents the Linear Cryptanalysis attack on the cipher. Note that this above discussion assumes that adversary somehow gets to know the messages and their encryptions whenever they are sent. This may be true if adversary knows what the other 2 parties are talking about for some time but doesn't know what they will talk about, say a month later, and he wants to get the key somehow so that he can listen to their talk after a month. If he has already seen $2^{43}$ messages in the part where he knew what they were talking about, then he will recover the key and then use that key to listen to their chats after the month. If the 2 communicating parties change their keys, then he won't be able to use that old key to listen to their chats after the month.
In practice, say in the browser, a hybrid type of encryption is usually used where a public key handshake is used to establish a symmteric key and then that key is used to encrypt messages by symmetric encryption (AES) because symmetric encryption is way faster than public key encryption. Then you might ask that why don't we use symmetric key encryption to establish the keys also? This is so because symmetric key encryption doesn't provide a way for 2 parties to negotiate a key over an untrusted channel like internet but public key cryptography does (like Diffie Hellman Key Exchange Protocol).
Once a connection has been established, then across multiple sessions public key cryptography is used to rekey the symmetric encryption through which messages will finally be encrypted.


Security aspects of using a global values as nonce and additional data for AES?

It is not clear what you are attempting to do.
AES in itself does not need a nonce, it only needs a key.
If you are using an algorithm which uses AES, such as AES-GCM then the nonce must never be reused (In general when using cryptographic protocols, never reuse a nonce!).

If by global value, you mean one which is constant, this ruins the security of any nonce using protocol. If you simply mean using a global variable as an engineering question, this is usually not advisable, as you are not encapsulating the nonce, but should not ruin the cryptographic security of any algorithm, provided the nonce is used only once.


Truncated 60 bit SHA1 collision detection?

It seems I am now running out of memory before computing the end answer which is bizarre

Typical brute-force issue.

Here’s a hint: do NOT store results in arrays as that’s most probably what’s currently causing you to run out of memory. Look at the numbers: if we would assume no collisions, you’ld need your array (read: memory allocation) to hold up to $2^{60}$ elements to store all 60-bit results; and we’re not yet counting memory you need to run the OS, to run your code, and to store things like the random 15 bits hex codes you’re hashing.

Of course – due to the fact SHA1 collisions are known to exist – your array won’t grow that big, so you won’t need to worry that you might be needing a rough 144115 Terabytes of memory to store all “SHA1 truncated to 60-bit” results. Thinking about the resources available when using an average desktop computer, a project going for 60-bits of truncated SHA1 without running out of memory should be feasable. An SHA1 hash truncated to its first 60 bits, should take around and about 60 or 120 million iterations/hash-calculations before hitting a collision – depending on how lucky you are. Unless your computer is 10 years old or older,and unless you mess up your implementation, that number of elements should easily fit into memory.

One potential solution to your memory problem is to use random hex codes as you currently do, and to store things in a tree indexed by the first 60-bits of the hash. (In case of doubt, look for “Binary Indexed Trees”, also known as “Fenwick Tree”.) Yet, if that’s indeed the best way to do it somewhat depends on implementation details, available resources, and – last but not least – used programming language. As we handle coding-related questions as “off topic” here at Crypto.SE, I’ll refrain from diving into that.

Background Info: Exponential Growth Problem

I’m assuming you did some research before practically programming things up. If you did, remind yourself of the fact that the resources required for a brute-force attack grow exponentially with the data size (here: number of bits) you are brute-forcing. Among other sources, you can find this information in the Wikipedia article about Brute-Force attacks. Note that when we talk about the exponential growth of needed resources, we’re not only talking about raw computer memory – “time” is also one of the exponentially growing factors.

Here’s a graphic (from an SHA1 brute-force project) that puts things into perspective for you:

The fact that brute-force attacks cause you to quickly run out of several kinds of resources is the main reason why password-brute-forcing tools and utilities tend to prefer “dictionary attack” methods for longer passwords, and it’s one of the main reasons why cryptanalysts dive into cryptographic algorithms to find weaknesses and/or attack vectors that allow them to avoid having to bluntly brute-force things.

Long story short: Unless you’re a governmental agency with ample resources, or you’re merely attacking something small enough to fit your desktop computer, brute-force attacks can quickly become a rather futile effort.

Optimizing Collision Attacks

Lucky for you, SHA1 is considered “broken” and some attacks have been found which are more speedy than plain “brute-forcing collisions for (truncated and non-truncated) SHA1”. For details, you might want to check the papers mentioned in an answer to “SHA-1 collisions - what about practical attacks?”

For your convenience, here’s the relevant snippet:

  I'll assume … enough resources to perform one single attack finding two distinct 128-byte colliding messages on SHA-1 with a small change: the value of the (arbitrary) 160-bit initialization value. The later is possible

  by brute force with expected effort less than $2^{81}$ hashes (about the effort devoted to bitcoin mining in a year according to that source) using Paul C. van Oorschot and Michael J. Wiener's Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1; free slightly earlier version available from the first author's website);
  or with less effort using complex specialized methods exploiting weaknesses in SHA-1's compression function, with an estimated effort comparable to

  $2^{69}$ hashes, per Xiaoyun Wang, Yiqun Lisa Yin, Hongbo Yu: Finding Collisions in the Full SHA-1, in proccedings of Crypto 2005),
  $2^{63}$ hashes, per Xiaoyun Wang, Andrew C Yao, Frances Yao: Cryptanalysis on SHA-1, rump session of Crypto 2005; see also Martin Cochran: Notes on the Wang et al. $2^{63}$ SHA-1 Differential Path, in IACR eprint archives, 2007),
  $2^{61}$ hashes, per Marc Stevens: New collision attacks on SHA-1 based on optimal joint local-collision analysis (in proceedings of Eurocrypt 2013, also freely available from the author's website).

Based on the information available in the papers mentioned above, you should be able to derive something more optimal compared to your current, non-optimized brute-force approach to find “truncated SHA1” collisions. After all, “time” is a pretty valuable resource.


There are various factors that go into choosing a MAC algorithm, for example: Use cases for CMAC vs. HMAC? documents CMAC vs. HMAC; I think HMAC is a reasonable default choice though (supported by Colin Percival: http://www.daemonology.net/blog/2009-06-11-cryptographic-right-answers.html).
Yes, the MAC can be transmitted alongside the ciphertext, one thing to remember to do when verifying the MAC is to use a constant time comparison: http://codahale.com/a-lesson-in-timing-attacks/


Does the Server Key Exchange sign a hash or text

Signature generation includes hashing. So there is no need to perform hashing separately. This is why the signature schemes that are used will always indicate the hash to be used - either directly or indirectly using parameters.

Without the hash the signature would be vulnerable to key-only existential forgery attacks. I don't see how that would influence the security of TLS, but TLS in general tries to use standardized primitives within the protocol

Note that TLS up to 1.2 contains rather a lot of legacy constructions that would be considered non-standard by now, TLS 1.3 tries to resolve this by using RSA-PSS and SHA-2 (in the 256, 384 and 512 bit versions) which is provably secure if RSA and SHA-2 are secure.

So yes, hashing is used, but only as part of signature generation.


How can an adversary request decryption of an unused sector?

I understand that an adversary is capable of modifying an unused sector, but can anyone explain how they would be able to request its decryption?

The first thing to understand here is that this is an adversary model. In cryptography we model our adversaries so we know exactly what capabilities they have and which they don't.
In this particular case it seems whoever came up with this model decided that it would be a good idea to give the adversary the ability to change the ciphertext of and decrypt unused sectors.

Now we could model our adversary so that they don't have this capability. But in general we want to come up with models that are as powerful as possible so that if we prove a scheme secure in that model, it provides the maximum protection possible.
The only limit to the powers of adversaries that we usually use is we don't give them powers that always break any scheme we could possible come up with. E.g. when we encrypt a challenge bit for the adversary we do not allow the adversary to ask for the decryption of that specific ciphertext.

So the default in cryptography is to always add powers right until we barely don't get trivial breaks of security. Now for this specific capability. It seems to be useful because it utterly breaks the ability of the disk encryption to use an unauthenticated deterministic stream cipher (e.g. initialized / keyed by the sector index). This is because an adversary can just look at the ciphertext, request a decryption and then compute any such static keystream as an XOR. The keystream could then later be used if the sector becomes used at some point to extract data and break security. Additionally if the scheme allows you to get some value out of knowing plaintext-ciphertext pairs (e.g. block-indexing parameters), getting them from an unused sector may prove useful, especially if the decryption capabilities of used sectors are somehow limited.


Why does the hashfamily of all functions with $\{h \in H_0 | h:U \rightarrow V\}$ satisfy universal hashing?

First note that the set of all functions $U\to V$ contains for every value $u\in U$ and every value $v\in V$ a function $f$ such that $f(u)=v$. Also note that if you fix a point $u\in U$ and take a random function from $U\to V$, $f(u)$ is uniformly distributed in $V$.
Now if you apply that, fix any two points $x\neq y,\quad x,y\in U$. Now choose $h$ randomly out of $U\to V$. Note that $h(x)$ is uniformly distributed and $h(y)$ is uniformly distributed. The probability for $h(x)$ and $h(y)$ to be equal now should be $1/|V|$ which implies the desired universality.

Given that the above might not be entirely clear, let's do an example:
$$U=\{1,2,3\}\quad V=\{1,2,3\}$$
Clearly there are 27 functions mapping from $U$ to $V$ and clearly there are 6 pairs of unequal values $(x,y)\in U\times U$ for which we need to check whether the probability holds.

$(x,y)=(1,2):$ There are three possible ways to map $1$: to either 1,2, or 3, let's denote the actual value $h(x)$ for the moment. There are also three possible values to map $2$ to: 1,2, or 3, let's denote the actual value as $h(y)$. Given that these two choices are independent, there are 9 cases here.

If $h(x)=1$ then the tested equation only holds if $h(y)=1$ as well which is a 1/3 chance
If $h(x)=2$ then the same argument as for $h(x)=1$ applies with $h(y)=2$
$h(x)=3$ goes analogously

Now counting the cases where the equation holds for $(x,y)=(1,2)$ we get $3/9\leq 1/3$ as demanded.
If we go through the other pairs as well, a very similar argument will ensue and we'll be getting $3/9$ for all of them. Therefore a random function from $U$ to $V$ satisfies universality.


Observing cipher suites and certificate algorithms without man-in-the-middle

There are no TLS ciphersuites using CAST, so you can determine that one without looking at any actual data of any kind from any connection(s).

Yes, you can always tell passively (merely by looking) at a TLS handshake the selected ciphersuite. Note ciphersuites containing 'SHA' (meaning SHA1) use it only for the key derivation (called PRF through 1.2), and HMAC through 1.1 (always) or in 1.2 for any CBC-mode cipher or RC4 -- but RC4 is so weakened it should never be used at all according to rfc7465 in 2015. Using SHA1 or even MD5 in key derivation or HMAC is not a weakness; their breakage for collision only endangers certificates. (And actually not all certificates, but enough that the consensus is to ban them entirely.) You should definitely worry about any use of single-DES, as well as the 'export' suites with DES-40 or RC4-40 (as above, even full-strength RC4-128 is now officially prohibited). Some people worry about Triple-DES (written 3DES_EDE_CBC in the RFC names, and 3DES-CBC3 in OpenSSL's scheme) because of the generic birthday bound for 64-bit block -- see https://www.sweet32.org -- but for many applications, e.g. accessing StackExchange, this is not a problem. IDEA in principle also has the 64-bit block issue, but it is very rarely used, mostly because its patent status caused many people to avoid it in the past, and now there's no reason, benefit or incentive to go back to it instead of newer, better options.

Through 1.2 you can also see the server certificate chain (which will almost always be two and occasionally more, not 'a' certificate as you asked) and check the signing algorithms, and key sizes which is more important. MD5 and SHA1 broken for collision does endanger certs, as above, and as a result no cert issued by a public CA after about 2008 uses MD5 and none after 2015 or at most 2016 uses SHA1 for signature -- and the certs issued before that are all expired and invalid (except roots where the signature algorithm doesn't matter at all). In 1.3 the certifcates are now encrypted, but if you are on-path you can actively make a test connection to the same server with the same parameters and you're pretty much guaranteed to get the same certificates, which you can look at. For that matter many certs from public CAs are now in the public transparency logs and you can look there -- although if a server/domain has multiple current public certs in the logs you don't know which one(s) is(are) actually used.

Those said, regarding your other Q I have no idea whether squid in particular can do any or all of this, or could resonably be modified to do so.

Lastly, to be clear, although this will detect some cases where a connection is insecure, the lack of an identified weak primitive in a connection does NOT mean it is secure. Except for the intentionally-broken export suites and long obsolete single-DES, and a few cases of certs signed using MD5, I've heard no credible allegations of real-world breaks of SSL/TLS connections because of weak primitives (not even RC4). Instead the breaks are due to bad parameters or keys (sometimes visibly so, i.e. too small, sometimes not) or protocol or implementation flaws, or not the connection at all but rather an endpoint. Plus not all connections even between the same pair of endpoints are the same, and the existence of some apparently-good connection(s) does not prevent the past, present, or future occurrence of bad one(s).


How to break homophonic substitutions and nomenclators with too many symbols?

Regarding the first part of the question, I will just link to another answer I wrote in the past:
Why don't homophones hide multiple-letter patterns?

Summary: If you adjust the frequencies so that every single symbol is equally likely, then bigrams can be used for frequency analysis because they won't be uniform distributed. The structure of language is much more complex than frequencies of single symbols.

The second one is probably much easier to break: Let's assume you know that this kind of cipher is used. The list of the most common words in English should be fairly easy to generate. And then just pick arbitrary plaintexts and calculate the frequencies. When you consider the most common words as one symbol that will change the frequencies of the other letters to some degree, but the symbols for most likely words are between the most likely symbols of the alphabet.

To further improve this process:

Look at bigram frequencies. If you consider the symbols for (of, the), that is surely one of the most likely bigrams in such a cipher.
Adding more and more words as single symbols has no meaningful effect: Language is very, very non-uniform over words. See These lists on Wikipedia to get an idea:

In the "TV list", first is you with $1,222,421$ counts, 1000th is worst with a mere $2276$. That's a factor of $537$ times higher. Total count was $29,213,800$ for that list.
In the "Project Gutenberg list", first is the with $56,271,872$ per billion words, 1000th is names with $79,366.6$ per billion words. That's a factor of $709$ in those frequencies.
In the first list, the 1000th word has frequency $\approx 0.0000779$, and in the second list it's $\approx 0.0000794$. So if you consider every word a single symbol, this is the frequency. If you use multiple symbols of the normal alphabet for other words, the frequency of this special word would be even less.

On the nomenclators, there is also the problem: Since you assign one symbol per word, if you change the key you need to update the entire lists for both parties.

Frequency analysis can be applied to more than just single letters, and not all patterns of natural language can be hidden at the same time. This makes substitution ciphers really weak, especially if you use the same key (in the nomenclator this is the entire list) for more than a single, very short message.


What is the weakpoint of PRNG based encryption?

As a stream cipher I don't think there is any direct way to break the cipher.

First of all, it is extremely inefficient, as Richie already mentions. SHA-256 has an input block size of 512 bits, and you're only propagating 128 out of 256 output bits. So you're wasting a lot of input space. In other words, it won't be twice as slow as just SHA-256 due to the limited output being used, it will be about 8 times as slow (!).

One of the problems with your algorithm is that it only propagates 128 bits out of the internal state of the 256 bit internal state of SHA-256. That means that you are more likely to hit a cycle within the hash function. Probably your cipher mode has limited input size because of that. It is probably similar in security to CBC for a normal 128 bit block cipher in that way.

A bit of a unfair problem with it is that it has not received any formal review and that it doesn't have a formal proof. As for practical problems, a hash function input is generally not designed to take any keys, so you need to be aware of that. SHA-256 is fortunately relatively resistant against side channel attacks by itself. One good thing is that the key is not repeated anywhere in the followup hash calls.

As a cipher mode your algorithm is deterministic as it doesn't take an IV. It would however be easy to add a 128 bit IV or (rather) nonce at the start, simply as additional input next to the key. As it stands, it cannot be used as a cipher for repeated messages. You might mitigate the cycle issues by adding a counter to each invocation of SHA-256 as well, there is space enough for another 128 bit value.


Is the firewall decrypted my session?

In order to inspect the encrypted traffic, your firewall has to decrypt it firts, one way, or the other. Since it can't do it any other way, it "impersonates you/your computer" as the client to the server (and creates an encrypted connection to the server) and also "impersonates the server" to your computer as the client (and creates an encrypted connection with you).

  There is an error "Certificate Not Trusted" (Server Certificate changed to Firewall Cyberoam Certificate).

That's because the firewall has to "impersonate" the server to your client and as it can not use the real servers certificate for authentication/en/decryption/data integrity of the traffic between you (as the client) and it (as the server), it has to use its own. The certificate the firewall uses is issued by its own CA that's obviously not set as trusted in your browser.

  Which public Key I got? Is Main server Public Key or Cyberoam Public Key?

The firewalls (Cyberoam).

  Is SSL traffic inspection is same for Authenticated Encryption "GCM" ?

AFAIK, yes.

The only problem I see here is if you don't know your encrypted traffic is being inspected / don't want it inspected. If you do, you should set the firewalls CA as trusted in your browser and that'd be that. Here are the instructions from Cyberoam Knowledge Base

Hope I helped.


There is some discussion here and a paper from 1996 here. I had looked at this cursorily years ago, it is not so easy. And a google search brings up some other papers. The discussion may be the way to start.


Encrypted Data length in a CBC Block Cipher

What is the extra byte and what should it be?

That is due to the way padding is specified. The last byte is the padding length, from 0 to 255. That is the length of the padding without the length byte itself. So with "zero padding" there's still the padding length byte.

  The first section says the length is the sum of the block length, the contenct length, the MAC length and the padding length. So why in the example is the 8 byte block length ignored in the calculation?

The quote continues "this does not include the IV". That is because unlike the rest of the data, the IV is not encrypted.


So first, for each employee there is a public-private-key pair, which is $2n$.

For each session one symmetric key is created. Your solution assumes the communication partners initially agree on a symmetric key they both use in the communication with each other.

Considering a session as a communication in just one direction, instead of $n*(n-1)/2$ symmetric keys, there would be $n*(n-1)$ symmetric keys, making a total of $2n + n*(n-1) = 30$ keys

Edit for clarification:

The initial question states "each employee communicated with all other employees once"

This could mean two things:

$A$ sends a message encrypted with $symkey_1$ to $B$
$B$ responds with a message also encrypted with $symkey_1$
So $A$ communicated once with $B$ and $B$ communicated once with $A$

Another interpretation:

$A$ sends a message encrypted with $symkey_1$ to $B$
Two days later, $B$ sends a message to $A$ encrypted with $symkey_2$
So $A$ communicated once with $B$ and $B$ communicated once with $A$

The second interpretation will create $n*(n-1)$ symmetric keys, while the first one created only $n*(n-1)/2$ symmetric keys


One possibility for what you might be missing: normally the same key (the same matrix) is re-used to encrypt many messages.  So now try counting the total entropy in $M$ length-$N$ messages, and the entropy in a $N\times N$ matrix, and compare what happens when $M$ gets large....

Another possibility you might be missing is the consequences of the fact that you are working modulo $26$.  I think you need to calculate out $p(y|x)$ carefully.  You might start by considering what happens when $N=1$.  Can you calculate the value of $p(y|x)$ and $p(x|y)$, for all possible values of $x,y$?  Maybe write a program to do it, or do the case analysis so you don't have to consider $26\times 26$ cases exhaustively.  I think you'll find that is enough to let you figure out what's going on.

I don't want to say more, because this is an exercise, and should solve your own exercise.


Full encryption of IDs, partial decryption with customer specific key

So lets assume a few things:

just symmetric primitives suffice;
a symmetric key derivation function and single block encrypt with a 64 bit block cipher is sufficiently fast;
the ID's are unique and not related to customers;
we're not afraid of customers sharing ID's;
there is protection against customers simply guessing ID's;

Scheme:

establish a master key $k_m$
derive customer keys and distribute to customers: $k_{c,name} = KDF(k_m, name)$
derive a data key for each ID with index $i$: $k_{id, i} = KDF(k_m, i)$
create and distribute the encrypted array where each entry $C_i = E(k_{id, i}, ID_i)$

Now comes the tricky part:

when a customer wants to get the ID's he sends you the set of indices to the ID's;
you calculate the customer key and a customer specific data key for each entry: $k_{c,name} = KDF(k_m, name)$ and $k_{c,name,i} = KDF(k_{c,name}, i)$
you calculate the difference between the data key and customer specific data key for each entry: $k_{x,i} = XOR(k_{c,name,i}, k_{id, i})$
you send a map consisting of elements $(i, k_{x, i})$ back to the customer
the customer can now perform $k_{id,i} = XOR(k_{c,name,i}, k_{x, i})$ for each entry
and of course calculate $ID_i = D(k_{id, i}, C_i)$


Why is Symmetric encryption classed as Private Key?

Here's an easy way (in my opinion) of keeping it straight: Think of encryption as creating a "secure channel."

Symmetric:

Secret Key K <-----------------------> Secret Key K

Each side has the same shared key. Since they have a shared secret key, messages flow freely between them - they can both encrypt messages to send to one another. The picture is symmetric... the two sides match.

Asymmetric:

Public Key   -----------------------> Private Key

One side has the private key, the other the public key. The public key holder can encrypt messages such that only the private key holder can read them, but the private key holder cannot use his private key to send secure messages to the public key holder (unless they negotiate/exchange some other key(s)). The picture is not symmetric anymore.


What is the probability of a collision in SHA-512 when the input is 512 bits of data

Suppose the input of SHA-512 is 512 bits of data (so exactly the same size as the output). If I would test every possible combination (so $2^{512}$ calculations), then will the output also be exactly $2^{512}$ different hashes, or will collisions occur?

It would be astonishing if SHA-512 turned out to be a permutation on 512-bit inputs, so no, absent a publication-worthy breakthrough in SHA-512 analysis, the output would not be exactly $2^{512}$ distinct hashes.

  If collisions occur, would the amount of collisions and the 'size' of the collisions (approximately) be the same as statistics would predict after randomly generating $2^{512}$ 512-bit strings? (With 'size' I mean the amount of times a specific hash occurs)

As far as we know, yes.  The usual model is a uniform random function.  Under each distinct input, the output is an independent uniform random bit string.  This model is like writing down a giant book of outputs with $2^{512}$ pages, one page per input having the corresponding 512-bit output, where every output is chosen independently and uniformly at random—which is exactly what you just described.

If we examine the structure of SHA-512 under the hood—a block cipher, which we might call ‘SHACAL-512’ (related to SHACAL-2, which is the block cipher underlying SHA-256), in Davies–Meyer composition—for 512-bit message $m$, we have $H(m) = E_{\operatorname{pad}(m)}(h_0)$ where $h_0$ is the standard initialization vector.  In the ideal cipher model, every distinct 1024-bit string $\operatorname{pad}(m)$ gives rise to an independent uniform random permutation $E_{\operatorname{pad}}(m)$, whose output on a fixed input string $h_0$ is then an independent uniform random 512-bit string.  Absent cryptanalysis of ‘SHACAL-512’, there isn't a much better model for this either.


If you mean this paper by Rogaway, "Evaluation of Some Blockcipher Modes of Operation" (PDF, relevant page is 120) then it very clearly documents everything.

$q_{\text{dec}}$ is the total amount of decryption queries the adversary asks. If you only accept one decryption query before using different keys, this can be approximated by $1$.
$\sigma$ is the total number of block cipher calls the mode would make on the adversary's sequence of queries. So if all adversarial queries (encryption and decryption ones) together require 4 block cipher calls to process, then $\sigma=4$. For 500 MByte of Data (in the single query) this would imply $\sigma\approx 2^{26}$

Also note that the bound stated in the paper (note the additional square on the $\sigma$) is $$\leq \frac{q_{\text{dec}}}{2^\tau}+\frac{\sigma^2}{2^b}$$

Plugging in the above values yields an advantage of $\leq 1/2^\tau+2^{52}/2^b$ which bounds the success probability of any adversary. Now random noise usually isn't exactly a smart adversary so the probability of a (successful) forgery from random noise is even much lower.

So let's clarify on what a "block cipher call" actually is. Modes of operation like CCM are built on block-ciphers which get modelled as functions $C=E_K(P)$ for some plaintext $P$, some key $K$ and the corresponding ciphertext $C$ where $P$ and $C$ are the same, fixed size. One computation of $C$ from $K,P$ or of $P$ from $K,C$ is called one block cipher call (because in the implementation you call the block cipher function for this). Now for CCM mode, which I will skip describing here, you end up with about 2 block cipher calls per data block (one for privacy, one for authenticity), yielding the aforementioned $2^{26}\approx 2\cdot 500\cdot 10^6/16$.


Given enough RSA signature values, is it possible to determine the public key value?

First, assuming any padding, the answer given by fgrieu to your related question still holds. You can associate public keys with signatures by looking at which signatures are consistenly (minimally) smaller than the modulus.

The second method, as suggested by poncho in the comments of your related question and the comments of this post cleverly uses small prime factoring to find $N$. I put this here, so it doesn't look "tagged-on" at the end of the post. The idea is the same as in the third method below, but with a clever twist. Where I collect enough samples to get a decent probability that there's on coprime pair of $t_i$ values, he suggested to take much less pairs and calculate the GCD of all $t_i$. This is $\gcd(t_1,...,t_k)=\gcd(r_1N,...,r_kN)=N*\gcd(r_1,...,r_k)$, where $\gcd(r_1,...,r_k)$ is likely to be a factor which is small enough ($<2^{128}$) to be factored out by methods which can find small primes efficiently, like ECM, yielding the desired $N$, as the largest factor.

The third method is a bit more specialized. It's basically a re-statement of my previous answer to a similar question and goes into a little more detail than poncho's answer to your related question, while standing on similar feet.

Assumptions

It needs to be assumed that you have a set of message-signature pairs, it needs to be assumed that the padding is deterministic (i.e. something like PKCS#1 v1.5) and that the public exponent is known or can be brute-forced easily.

Method

Assume you're given the public RSA exponent $e$, the set of message-signature pairs $\mathcal S = \{(m_1,\sigma_1),...,(m_k,\sigma_k)\}$ with $|\mathcal S|=k$ and the padding function $\operatorname{Pad}(m)$. Note that knowledge of the padding function implies knowledge or a good estimate of the size of the modulus.

The first step is to reduce this problem from one with a complex padding scheme to one of simple raw RSA signatures. For this, we apply $\operatorname{Pad}(m)$ to each message $m_i$ in $\mathcal S$ and and replace the unpadded $m_i$ with the padded $m_i'$ for the set $\mathcal S'$.

Now observe, that as per the normal verification process, $(m_i')^e \equiv \sigma_i \pmod N \forall 0<i\leq k$. This can be rewritten as $(m_i')^e = \sigma_i + r_i * N$. As we know $m_i', e, \sigma_i$, we can calculate $t_i=(m_i')^e-\sigma_i=r_i * N$. Now we observe that all $t_i$ share one common factor: $N$, which we can recover (with a given probability) by calculating the pair-wise greatest common divisor of all $t_i$. The smallest result is likely our $N$. The fancy writing for this would be: $N=\gcd(t_1,...,t_k)$. Once we have a guess for $N$, we can confirm it by checking if all signatures are valid, i.e. if all equations $(m_i')^e\equiv \sigma_i\pmod N$ hold.

Success Probability

The first thing to observe or assume is that the values of $r_i$ are random non-zero integers. Due to their large size (beyond $2^{100,000,000}$), we will model them as randomly distributed numbers. Next, we observe that we found the modulus, if $\gcd(r_1,...,r_k)=1$ holds, i.e. if the set is co-prime. As we modeled the integers randomly, we can use the standard approximation for the probability that $k$ random integers are co-prime which is $1/\zeta(k)$ where $\zeta(x)$ is the riemann zeta function. So the probability that our guess $N'$ for $N$ is correct, is equal to the probability that all $r_i$ are co-prime and thereby:

$$\Pr[N'=N]=1/\zeta(k)$$

This formula can be used to retrieve the number of pairs neccessary to get a good probability for finding the correct $N$. The probability is at $99.99%$ with $k\geq 14$.


What does the expression $1^n$ mean as a function argument?

If you got an expression that resembles $\{1\}^n$ (or $1^n$) at a place in a surrounding expression where you would expect an $n$-bit bit string to be, the $\{1\}^n$ expression means a string of $n$ bits each with the bit value $1$.

Conversely, $\{0\}^n$ means a string of $n$ zero valued bits, and $\{0,1\}^n$ just means any bit string of length $n$.

In the paper you mentioned, it looks like $n$ plays double duty: it both determines the set of attributes/predicates, and it is the security parameter. In this case the authors don't seem to use this notation to indicate that the setup is polynomial in the binary logarithm of the key space, but rather that it is polynomial in the maximum number of independent predicates.

The concepts Predicate and Attribute are related in such way that each entity $k$ (that might or might not have rights to decrypt a given cipher text) is associated with some set of predicates $F_k = \{f_i\}$ and the cipher text is associated with an Attribute $I$, and entity $k$ will be able to decrypt the cipher text if and only if $f_i(I)=1$ for some predicate $f_i \in F_k$ the entity has been assigned. The attribute was set as parameter when the plain text was encrypted to produce the cipher text.

The $Setup$ function defined in the referenced paper generates a master public key $PK$ and a master secret key $SK$. The master secret key is then passed to the $GenKey$ function that generates a secret key $SK_f$ for each predicate $f$

Although not written out explicitly, I suppose the argument of the Setup function could be interpreted as the union of the unhidden attributes of the cipher texts that the master secret key (generated by setup), will decrypt. With $n$ predicates, there are $2^n$ possible valid attribute value classes (there might be more than one value that instantiates each attribute), meaning that the set of attributes is isomorphic to $\{0,1\}^n$. One might in such case define the isomorphism $\phi$ such that the master attribute $I_M = \phi(1^n)$ equals the attribute such that $f_k(I_M) = 1$ for all predicates $f_k, 0 \le k \lt n$.

So how does this relate to the specific definitions in the referenced paper?

For starters, the set of attributes $\Sigma = \mathbb Z^n_N$ is a vector set with $N^n$ different values. However, the difference between $N^n$ and $2^n$ is due to there being $(N-1)^{n-k}$ different values in $\Sigma$ that all correspond to the same selection of $k$ predicates. Think of it like this:

Let $X$ be an $n\times n$ matrix over $\mathbb Z_N$, where each row corresponds to a predicate vector. Let $Y$ be an $n$ element column matrix corresponding to an attribute $I$. Let $XY = Z$. Now, since matrix multiplication of a row on the left with a column on the right corresponds to a dot vector multiplication, for each element $z_i$ in the $Z$ column matrix, $f_i(I) = 0 \iff z_i = 0$. On the other hand, if $f_i(I) \neq 0$, then $z_i$ might be any non-zero value in $\mathbb Z_N$, and there are $N-1$ such values.


Is this an issue?

That's up to you, not us.  Is 2^-33 probability of horrible cryptographic failure acceptable to you?  Multiply that by the number of times you'll use this construction (or the rate and the product life time) to get a scarier picture but one you should keep in mind.

  Is there something else I should prefer?

"should prefer" is again subjective based on your situation.  I strongly advise you to consider AES-SIV (or AES-GCM-SIV) or XSalsa20-Poly1305.

  For example, AES/CBC with encrypt-then-MAC construction would have a more reasonable IV/nonce size of 128 bits.

Sure, for another example.  But if collisions bother you and you'd like a significantly lower probability then either 1. stop using random nonces 2. go for a nonce size that's greater than ~80*2 (a la XSalsa) or 3. Use a misuse resistant algorithm.


RSA: Does it matter if you use e or d to encrypt?

Yes it matters if one uses $e$ or $d$ to encrypt. One must use for encryption whichever of $e$ or $d$ is published as part of the public key, and the other exponent must not be chosen small.

There is however no problem in choosing $d$ small (or large and random), publishing it, and computing $e$ from $d$ and the known factorization of the public modulus $N$; that will in all likelihood make $e$ large, for otherwise correct choice of $N$ and $d$; that is merely changing the letters used to name the exponents.

Update per comment: whatever $e$ or $d$ is chosen first, successfully computing the other exponent such that $ed\equiv1\pmod{\varphi(N)}$ insures that both $\gcd(e,\varphi(N))=1$ and $\gcd(d,\varphi(N))=1$. Thus if we choose large enough $N$ of known secret factorization, then $e$ large and random with $\gcd(e,\varphi(N))=1$, compute $d$, publish $(N,d)$, then it is fine to use $d$ to encrypt and $e$ to decrypt; we have only changed the letters used to name the exponents, and tested that the published $d$ verifies $\gcd(d,\varphi(N))=1$ in a slightly unusual way.

In RSA, a public key is made public, hence its name. Usually that is taken to be $(N,e)$. It is critical that encryption is with the exponent in that public key, because encryption must be public, and decryption private.

Also: as pointed by SEJPM's comment, $e$ is often chosen small ($e\le65537$ is typical); that makes $e$ is guessable; hence publishing $d$ and using it for decryption would allow anyone to decipher by guessing $e$ . As an aside, knowing $d$ and $N$, and that $e$ is small, it is possible to factor $N$ . Therefore, if in this comment "construct two new keys" is about reusing $N$ after $(N,e)$ or $(N,d)$ was published and the other exponent was small, published, or otherwise leaked, that's insecure.

Note: contrary to the question's statement, encryption of plaintext $M$ should not be as $M^e\bmod N$. One reason is that a guess of $M$ can be checked by anyone knowing $(N,e)$, that is by hypothesis any adversary; which can be a disaster e.g. when $M$ is a name on the public class roll. That's why we use RSA random encryption padding (e.g. RSAES-OAEP).

Final note: $p=3$, $q=5$ makes a much too small example for RSA: raising to the power $e$ or $d$ modulo $N=15$ has the exact same effect for all valid choices of $e$ and $d$, which all verify $e\equiv d\equiv1\pmod4$ or $e\equiv d\equiv3\pmod4$ ! In fact, until $p$ and $q$ have at least a few dozen decimal digits each, $N$ can be factored easily, thus there's no security, and size requirements on $e$ or $d$ are pointless.


Given a list of ciphertexts, how to identify the ones that used the same key for encryption

If you assume the keys are random yet the plain text are english. Xoring two cipher texts with different keys will look like random noise. Yet if you xor two messages with same key you get a complex distribution of pairs of English messages, very not random. A simple histogram should be sufficient to tell the distributions apart.
If the keys are not random(possibly leading to other attacks) you will probably still be able to pull off the same attack though you will need to study the histogram of xoring English messages so you can detect it. With random keys it won't even be necessary.


Proving a function is one way hash function

The inverse cannot be calculated, you're right. However, in can be guessed.

In many scenarios, for example cracking hashed password, it's enough for the attacker to know a set of possible inputs which result in certain output (of course if their number is reliable) instead of  one certain value.

So if the one-to-many function is weak, given the output $y$ the attacker can calculate $x_1,x_2,...,x_n$ such that for each $x_i$ $H(x_i)=y$ and try them one by one.

Concluding - it's not enough to show that it's one-to-many function. You must also show that finding the set mentioned above is computationaly hard for your function.

PS. You might wonder why $n$ can't be so big that trying all possible inputs resulting in a certain output will be impossible. This would cause another weakness - low collision resistance.


MAC-then-encrypt in SIGMA protocol for authenticated key exchange

Arnaud asked me to clarify this issue.
It is true that one should use an authenticated encryption mode or encrypt-then-MAC, and the paper says that explicitly. Indeed, the explanatory text in the paper following the figure shown above (Section 5.2 of https://webee.technion.ac.il/~hugo/sigma-pdf.pdf) addresses this issue.
It says:

We stress that the encryption function (as applied in the third message) must be resistant to active attacks and therefore must combine some form of integrity protection. Combined secrecy-integrity transforms such as those from [16] can be used, or a conventional mode of encryption (e.g. CBC) can be used with a MAC function computed on top of the ciphertext [3, 26].

Namely, the encryption denoted  $\{...\}_{K_e}$ needs to use an authenticated encryption scheme. (The need for authenticated encryption is also repeated in Appendix B that shows a more complete protocol in the form of SIGMA-R).
The fact that there is a MAC (on the identity) under the encryption is just because the MAC is (an essential) part of the SIGMA protocol and is completely unrelated to encryption (in particular, needed even if you do not care about protecting identities). So while it looks like "MAC-then encrypt" it has no relation to this mode of encryption.
Note: The reason the text says that authenticated encryption is only needed for the third message is that, as said at the beginning of that same paragraph,  SIGMA-I protects the identity of the initiator from active attackers and the identity of the responder from passive attackers.   So encrypting the identity of the responder only needs security against passive attacks for which UNauthenticated encryption suffices. This is really an academic remark since in practice one would use the same encryption scheme for both flows, namely, authenticated encryption for both.


OK, I found my own answer.
A catastrophic drawback is $M = p \times G - c \times P$, by changing $c$ to any desired data block.


Well this question depends on what you mean by $\textit{division}$. R1CS is usually defined over a finite field $\mathbb{F}_p$, so constraints about modular inverses are quite easy to represent. On the other hand, if you're asking about integer division, which is not natively supported by finite field arithmetic, then this becomes more tricky.
Let me expand on this. I'll try to follow the notation used in Vitalik's popular post. In order to represent a modular inverse operation such as $x \cdot y^{-1} = z$, we could define two constraints in our flattened arithmetic circuit:
$\text{one = y}\cdot \text{y_inv}$
$\text{z = x}\cdot \text{y_inv}$
As you can see, we've introduced the extra variable $\text{y_inv}$ and added the constraint that $y \cdot y^{-1} = 1$ (i.e., the definition of modular inverse).
Now, you might instead be asking the question of how we perform integer division i.e., $\lfloor\frac{x}{y}\rfloor = z$, using finite field arithmetic? Recall that this is much different than taking modular inverses in $\mathbb{F}_p$.
As example, let's try $7 / 2$ in $\mathbb{F}_{11}$:
$7 / 2 = 7 \cdot 2^{-1} = 7 \cdot 6 = 42 = 9 \mod 11$, since $6$ is the modular inverse of $2$ in $\mathbb{F}_{11}$.
However, $\lfloor\frac{7}{2}\rfloor = 3$ (obviously) if we're talking about integer arithmetic. This more complex operation can be represented in $O(\log(p))$ R1CS gates using non-determinsitic advice e.g., by enforcing that $x = z \cdot y + r$ and $r < y$, where $r$ is provided by the prover.


How does cryptanalysis of the Playfair cipher work?

There are several algorithms available which can attack a playfair cipher.

Hill climbing might be one option. Basically it starts with a random key (assuming it's the best one) and decrypts the cipher. The resulting clear text is scored using a fitness function. Then small changes are applied to the key and if the resulting clear text of the modified key scores better, the modified key is regarded as the best key and the process of applying small changes to the key starts over again until no better key can be found.

Sometimes Hill Climbing does not find the best solution, the algorithm gets stuck at a local maximum. An effective way to resolve this issue is to use the Shotgun hill climbing (refer to the wikipedia link provided above).

The Simulated Annealing Algorithm is another option, see also here.

Or you can use the Genetic Algorithm. The algorithm mimics the process of natural selection.

If you are interested in an online playfair breaker: http://bionsgadgets.appspot.com/ww_forms/playfair_ph_web_worker3.html. I think here the hill climbing algorithm is used. It is coded in Javascript, so the source can be studied.

If you are interested in how a clear text can be scored:
Quadgram Statistics as a Fitness Measure.


estimate of time required to crack sha512crypt password with JtR + OpenCL

The simplest and obvious solution is to just do it. JTR (or any decent password cracker) will show a realtime ETC and this is much better than speculating endlessly about hardware specifications.

But if you must, read on...

This is highly dependent on the number of iterations you used for the KDF. But you can calculate it easily. Suppose selecting one candidate and running it through sha512crypt takes time $t$.

Now there are 52 "letters" in the alphabet (I assume case matters) and 10 "numbers". So there are, in total, $52^4 \cdot 10^2 = 731161600$ candidates for your password.

Thus, on a single core, you will need $731161600 t$ units of time in the worst case to find your password. On average, it will take $\frac{731161600}{2} t$ units of time.

Now if you have $k$ different cores to work with, you will on average find the password after:

$$\frac{731161600}{2} \frac{t}{k} ~ ~ ~ ~ (\text{units of time} ~ t)$$

Let's plug in some numbers. A mainstream GPU has quite a lot of independent execution units, so let's say $k = 256$, a reasonable number. On the CPU, let's say you set up your KDF properly and it takes 0.1 seconds to compute it on the CPU. The GPU cores are slower individually, so let $t = 0.25 ~ \text{s}$.

$$\text{Average time to crack} = \frac{731161600}{2} \frac{0.25 ~ \text{s}}{256} = 357000 ~ \text{s}$$

Which comes out at around four days on average. In the worst case, it will take eight days.

Select $t$ and $k$ accordingly (I suspect in your case, your $k$ will be lower since you have a laptop graphics card, but your $t$ may also be lower). On specialized hardware, it would be faster, of course.

If worst comes to worst, you can always loan a few heavy-duty servers (or ask friends) and increase your $k$ value considerably, which can speed up the process quite a bit.

tl;dr it depends on how fast your GPU is, and how you configured your sha512crypt KDF. And if you have any additional information on the password (is the first letter a vowel, are the four letters a word, etc..) you can use this to set up rules in JTR to reduce the number of possible candidates.


Why is LCG PRNG chosen to be as c++ rand() function?

The C++ rand() function (actually C function) is not (intended | designed | standarized) for Cryptographic purposes.

  Why was this algorithm chosen?

As SEJPM noted in the comments, the rand function comes from C and C++ has no upper restriction for the implementation.

  What are the pros and cons?
  Is it good for cryptography?

Long story short answer; don't use it for cryptography. For cryptographic purposes use /dev/urandom

The good; it is fast and small. The bad; it is deterministic, and the seed is small ( as noted by poncho in the comments) that prevents it from producing a cryptographically secure RNG from LCG.


Was Enigma really that hard to crack, given that you had access to hundreds of messages per network per day?

Yes, it's just that the messages were often low value.

There was nothing like gps back then, you would not get a real time location of a submarine. At best you'd get a lat/long which is precise to several km and then spend hours trying to get a plane there.

You'd get vague obvious warnings like "Germans may be attacking this convoy"- and there was no central directions, it was up to the uboat commander to decide the details .

But that was important enough that the government gave them a few people to help them crack these messages.

So given such a small, resource poor team was allocated to the task it was a big accomplishment.


Signing an integer, which may be increased

Yes, this is possible.  Here's one simple scheme:

The scheme.  We fix an upper bound $B$ for the maximum allowed value of the counter.  Let $H$ be a cryptographic hash function and $\text{Sig}(\cdot)$ be an ordinary signature scheme (e.g., a RSA signature).  Use $H^k(x)$ to the $k$-fold iteration of $H$ on $x$, e.g., $H^2(x)=H(H(x))$.  The signature $S(n)$ on counter value $n$ is a tuple $(n,x,y,\text{Sig}(y))$ that passes the following verification check.

Signature verification. The signature $(n,x,y,s)$ is valid if $H^{B-n}(x)=y$ and if $s$ is a valid signature on $y$.

Signing. Note that the signer can create an initial signature $S(0)$ by choosing $x_0$ randomly, letting $y=H^B(x_0)$, and signing $y$ to get $S(0)=(0,x_0,y,\text{Sig}(y))$.

Incrementing. Also, given a signature $S(n)=(n,x,y,\text{Sig}(y))$ on counter value $n$, anyone can increment $n$ to get a signature on $n+1$ as follows: $S(n+1)=(n+1,H(x),y,\text{Sig}(y))$.

Performance. Creating a signature takes up to $B$ iterative hashes and one ordinary signature.  Verifying a signature $S(n)$ takes $B-n$ iterative hashes and one ordinary signature verification.  Therefore, this scheme is only efficient if the bound $B$ can be kept relatively small.

Here are two small improvements on the simple scheme above:

A trick to speed up signature verification.  If you want to speed up signature verification, at least for small values of the counter, then you could use the following trick.  Let's assume for convenience that $B$ is a power of two.  The signer creates the initial signature $S(0)$ as

$$S(0) = (0,x,H^1(x),\text{Sig}(1,H^1(x)),H^2(x),\text{Sig}(2,H^2(x)),H^4(x),\text{Sig}(4,H^4(x)),\dots,H^{2^i}(x),\text{Sig}(2^i,H^{2^i}(x)),\dots,H^B(x),\text{Sig}(B,H^B(x))).$$

In other words, the initial signature $S(0)$ can be written in the form

$$S(0) = (0,x,y_0,\text{Sig}(1,y_0),y_1,\text{Sig}(2,y_1),\dots,y_i,\text{Sig}(2^i,y_i),\dots),$$

where $y_i=H^{2^i}(x)$.

Notice that, as a special case, a verifier can verify the signature $S(0)$ with just one hash application: hash $x$ once to get $H^1(x)$, then check its signature.  For larger values of $n$, signature verification will require more iterated hash computations, but not $B-n$ iterated hashes.

To increment the counter, you increment the $n$ part (as before), hash the $x$ part (as before), and throw away any $y_i$ parts where $2^i \le n$ and the corresponding signatures.

Consequently, the signature on $n$ now becomes

$$S(n) = (n,x,y_i,\text{Sig}(2^i,y_i),y_{i+1},\text{Sig}(2^{i+1},y_{i+1}),\dots),$$

where $i=\lfloor \lg n \rfloor + 1$.

With this trick, verifying a signature $S(n)$ now can be done in $O(n)$ time: it requires up to $n$ iterated hashes and one ordinary signature verification.  Note that signature verification is not constant time; as the counter gets larger, verification gets slower.  This trick does increase the length of the signature by a $\lg B$ factor.  One can trade off the length of the signature against the speed of verification, to a certain extent.

A trick to speed up signature creation. If you want to speed up signature creation, the following variant may be useful.  However, this variant does not speed up signature verification, so this variant probably won't be very useful on its own in practice.  The signer can select a RSA modulus $N$ (whose factorization is kept secret), and use the hash function $H$ given by $H(x)=x^2 \bmod N$.  Note that this is a one-way function.  However, it has the special property that there's a shortcut that allows the signer to compute $H^B(x)$ with much less effort than iteratively hashing $B$ times: namely, $H^B(x) = x^{2^B} = x^k \bmod N$ where $k=2^B \bmod \varphi(N)$ and $\varphi(N)$ is Euler's totient function applied to $N$.  The signer knows the factorization of $N$, so can compute $\varphi(N)$ and then compute $k$ using modular exponentiation mod $\varphi(N)$.  This is the shortcut; however, only the signer can use this shortcut, because no one else knows the factorization of $N$.  This shortcut can be used to efficiently create an initial signature $S(0)$.

Of course, you can combine both tricks into a single scheme, if you want to speed up both signature verification and signature creation.

Related work. You might also be interested in the following papers:

Cryptographic Counters and Applications to Electronic Voting.
Jonathan Katz, Steven Myers, Rafail Ostrovsky.  EUROCRYPT 2001.

A Cryptocounter Based on the Paillier PKCS.
Adam L. Young and Moti M. Yung.
Advances in Cryptovirology, Chapter 6.


A Zero knowledge proof for set membership?

I think what you want is a ring signature. This is a signature mechanism that allow you to prove someone signed within a set of actor without revealing which one.

You may want to read https://link.springer.com/chapter/10.1007%2F3-540-45682-1_32 and https://github.com/Blockstream/borromean_paper/raw/master/borromean_draft_0.01_34241bb.pdf


Given a prime exponent e and a prime number n, find b, where b^e = 1 mod n

If $n$ is prime, $\mathbb{Z}_n^{*}$ has a primitive root $g$ and order $n-1$. So if $e$ divides $n-1$ you have $(g^{\frac{n-1}{e}})^e=1$.
For $n=11$ you  have e.g. the primitive root $g=2$ and therefore with $$b\equiv 2^{10/5}\equiv 2^2 \equiv 4 \pmod {11}$$ you compute $$b^5 \equiv 4^5 \equiv 1024 \equiv 1 \pmod {11}.$$

With the remaining primitive roots $g=6,7,8$ you get other solutions
$b\equiv 6^2 \equiv 3 \pmod {11},$  $b\equiv 7^2 \equiv 5 \pmod {11},$
and $b\equiv 8^2 \equiv 9 \pmod {11}.$

But be aware that your problem may have no solution: in your example there is no $b\not \equiv 1$ with $b^3\equiv 1 \pmod {11}!$


In perfectly secret scheme, if key and message space are uniformly distributed, is ciphertext space always uniform as well?

Question: If we say that the message space and key space are uniformly
  distributed, this seems to me to imply that the ciphertext space must
  also be uniform. How would one go about proving this fact?

You don't because this statement is false.
Here's a simple counter-example:

Let $k,m\in\{0,1\}$ be a key and a message bit, both chosen uniformly at random. Then let the ciphertext $c=m\oplus k\parallel 0$, that is you do the standard OTP encryption and append a zero bit. Obviously this scheme is perfectly secret because the OTP is and the zero bit is completely independent of the key and the message. Also obviously the ciphertext doesn't have a uniform distribution from the set $\{00,01,10,11\}$ because $11$ cannot occur.

A more interesting (new!) question though would be though whether for each length-preserving perfectly-secret encryption scheme the ciphertext follows a uniform distribution.


What can be learned from an encrypted text?

First lets have a look at your attack model: attacker is eave dropping only. This means no modification, just listening.

You also assume that the encryption system is perfect and you can't differentiate it from a random oracle (if I'm not mistaken we call this indistinguishability).

Due to all these restriction, if the system is well devised (no meta data). The only pieces of informations that you would be able to catch are the length of the data or the existence of the transmission (when are they communicating etc...)

Nowadays in order to avoid giving such data, (military grade) communications just send random noise when not used. That way, you won't be able to tell whether or not they are communicating. So no you cannot retrieve informations in this context.

Considering the use of meta-data, then you can retrieve some kind of "context-sensitive" pieces of informations by doing traffic analysis.
E.g. you can track communications between the hospital and your employees ... You don't know what they are about, but you know that your employee might be having some health problems...

More to read here : TRAFFIC ANALYSIS: or... encryption is not enough by Carmela Troncoso, IMDEA Software Institute.


How to use AES-CBC to password-encrypt a small block of stored data

Do I really need a random IV if I salt the data? Prepending 128-bits
  of random salt to the data is the same as using a 128-bit random IV,
  right?

Yes, it should do the job, but if I'm reading your question correctly you don't really have to optimize storage away, but if you want to, I'd rather recommend going with AES-128 and a 128-bit IV which is derived from the PBKDF result (simply split the 256 bits in half).

  What should I use for a PBKDF?

This is a difficult question. If possible you should pick a password hashing function from the password-hashing competition winner's portfolio.
If it's not possible you should implement PBKDF2 with SHA-256, because you then get those 256-bits from a single iteration chain which you can use for key and IV. All you can do optimize your defense is to measure the time it takes for your actual encryption code to run and then give what is left to the PBKDF.

  Most discussions of using a PBKDF emphasize the importance of
  including a salt value. That means I also have to store the PBKDF salt
  along with the IV and the ciphertext, right?

Yes, but as discussed above, you can swap the IV for the salt and derive the IV from the PBKDF output to save space again.

  They aren't using any salt in the PBKDF algorithm?

If they didn't prepend a salt to the ciphertext and the payload is always 16-bytes, then yes, there's no way they're using a salt.

  They must be using an IV produced by the PBKDF (or a constant IV)?

Again, if you don't see an IV, that means that any of the two options holds with the constant one being significantly worse than the PBKDF derived one.

Now that I have actually answered the question, I'd like to point out improvements in your format.

The format:

      16-byte salt
frame:
      16-byte payload
frame-end
      32-byte authentication tag

This way you get a strong salt, which won't yield any collisions and other undesirable outcomes on accident. You can feed it into the PBKDF and get the key and IV (both 128-bit) back for AES-CBC. You use this to encrypt the payload and the payload only. Finally you HMAC-SHA256 the salt, the (temporarily buffered) IV and the payload-ciphertext with the AES-key (yes it's ugly but should be safe) and append this tag to the ciphertext.

This has the advantage, that you don't do hash-then-encrypt which is a worse variant of mac-then-encrypt, you can actually use your salt where it's useful (why was it part of the plaintext in the first place?) and you get strong authentication with overall 128-bit security.


Determine the RSA private key from public key

I was told that you can determine the private key of an RSA encryption with the public key. Were they joshing me or can it be done?

Yes, it can be done. What you have not been told is that to factor a public key (usually hundreds of digits) to find the private key,  requires a time exponential in the length of the public key,
therefore even a supercomputer could take years, if not centuries. Factorization is believed to be a Hard Problem.
 On the other hand, if you already know the private key, you can get the plaintext in very few CPU's cicles.
This is the general principle underlying asymmetric cryptography:


There is no such thing as the most secure curve. For one you can always come up with a larger curve if you need one. For another there are many measures of security and not all curves are directly comparable.

If you wanted the curve for which the current best known attack is the slowest, then by that measure sect571k1 is actually the most secure out of the curves that are in use.

However, that is not necessarily a very useful requirement, because any curve for which the best known attack is slower than ~128-bit strength equivalent will never be broken without either advances in attacks or the arrival of practical quantum computers. Those advances need not apply equally to all curves, while quantum computers would break all curves regardless of strength.

Binary field curves like the one in question are sometimes considered more risky because better attacks are known than for prime field curves of similar size, so it is thought that new attacks are more likely. That is a judgement call.

Likewise there are other measures of security that do not apply to all curves. Perhaps the most talked about is the potential for some kind of backdoor in the parameters, which makes some distrust NIST curves in particular and any curves without a good explanation for the parameters in general. Also things like ease of secure implementation may matter in practice.


What is the use of REAL random number generators in cryptography?

For some types of algorithms (or protocols) we only need non-guessable (by the attacker) bits/numbers, not reproducible non-guessable ones (like from a deterministic PRNG).

In this cases, "real" random numbers are in theory (i.e. from an information-theoretic point of view, not a cryptographic one) better, since they can't be guessed (or even influenced) by an attacker, even if she could break our PRNG.

Some cases that I can now think of, where we don't need deterministic random numbers:

key generation (both symmetric and asymmetric)
initialization vectors for block cipher modes of operation (these are usually sent with the message, so the same plaintext will not result in recognizable ciphertext for the next message)
random padding in asymmetric encryption (for example OAEP)
salts for password storage (these are stored with the hash)
challenges in zero knowledge proofs (sent to the partner)
random values used in digital signatures (the k in DSA)
one time pads (OTP)  (Here, for the security proof, we actually need "real" random numbers.)
chaffing and winnowing

In practice, pseudo-random bits are cheaper and just as secure for real-world attackers (e.g. with resources limited by our earth mass and universe lifetime), as long as the PRNG is not broken and has enough entropy input to start with.

(If the attacker can control the seemingly random input to the "true random" generator, this would be even worse than a good PRNG.)

Often for these uses we use a combination of a cryptographically secure (deterministic) PRNG and an entropy pool, which gets filled (and re-filled) by random bits gathered by the OS. This would be a non-deterministic PRNG.


Embedding SHA256 inside SHA1 for BitTorrent

The problem with SHA-1 is the collision attack that way before the actual attack shattered.io NIST dropped it in 2011 from digital signatures since finding collision has catastrophic result in Digital Signatures. The generic collision of SHA-1 requires $2^{80}$-time and that was considered low for 2011 and beyond. The Rabin was the one first to use the hash ( it was then called compression) to prove the security of their signature scheme that we call now the Rabin Signature Scheme. SHA-1 is still allowed by NIST for for
using non-digital-signature applications as Acceptable status in 2019, NIST.SP.800-131Ar2

BitTorrent uses SHA1 for its hashes, but SHA1 is unsafe and people can tamper the preimage and still obtain the same hash, right?

That is not the pre-image attack that is given a hash value $h = H(m)$ for some message $m$ find a pre-image $x$ of the hash function $H$ so that $h = H(x)$. We can have $m=x$ or not. Equality is not required from the pre-image attack by definition. As one can see, this is very helpful for password cracking, it doesn't matter you have found the same password or not since both are working. There is no pre-image attack on SHA-1 better than the generic pre-image attack and that still requires $2^{180}$-time.
What you have tried is the second-preimage attack that is given a message $m$ and its hash values $h = H(m)$ find another $m'$ such that $h = H(m')$. SHA-1 has no second-preimage attack that faster than the generic pre-image attack and the cost of the generic second-preimage attack is $2^{160}$-time for SHA-1.
Tampering one-bit arbitrary you will get $1/2^{180}$ probability that has the tampered files same hash if we consider the output of the SHA-1 as uniform random.
Finding second pre-images is very dangerous. For example; one can design a new malicious IOS for the existing ISO and replace it. There is a problem here on the BitTorrent network that is many people share the same file and this will create conflict on the IOS that people downloaded. Therefore for an active download, it may not possible. For a new download, if the attackers are fast on finding the second-preimage attack, then they may replace the original copy before distribution, too IFs, right?

So imagine I want to be very sure the file I'm sharing on BitTorrent will be correctly downloaded by who is downloading it. Does it work to include 2 files, being:

The file I'm actually sharing;
A file containing the SHA256 of the file I'm sharing.
Then the receiver must just check if the SHA256 matches (plus check if the SHA1 matches, which will be done automatically by the BitTorrent client).

SHA256 calculation is free since it has no key. The IF attacker can still calculate the malicious ISO and their SHA256 hash and store as you did.
Risk Management
The usage of the SHA-1 really depends on risk management. For example, Git still uses SHA-1 and Linus has a clear reason for this;

Git does not require the second preimage resistance of SHA-1 as a security feature, since it will always prefer to keep the earliest version of an object in case of collision, preventing an attacker from surreptitiously overwriting files.

Now what about BitTorrent
BitTorrent divided files into 64 KB – 2 MB chunks. The torrent's metadata file (.torrent file) stores each piece's size and hash value. Together with the info_hash that store makes BitTorrent quite resistant to intentional tampering (poisoning). To verify the chunks SHA-1 is used the value in the info_hash.
There is research on this;
Adaptive Content Poisoning To Prevent Illegal File Distribution in P2P Networks*

We discover that BitTorrent is most resistant to content poisoning.
....
Because the index file is distributed outside of the P2P file-sharing system, each chunk can be verified with a reliable hash contained in the metadata. This verification provides BitTorrent protocol with high resistance to content poisoning.

There is also a long talk about this problem on the GitHub of the Bittorent; In short, if you trust the host that shares the .torrent file, you are safe.


AES MixColumns using L and E lookup tables

The values in the tables are listed in hexadecimal; hence the Log table maps $\mathtt{87}$ to $\mathtt{0x74} = 116$.  Similarly, it maps $\mathtt{02}$ to $\mathtt{0x19} = 25$, and $(116 + 25) \bmod 255 = 141 = \mathtt{0x8D}$; looking up $\mathtt{8D}$ in the Exp table gives us... $\mathtt{15}$ (actually, $\mathtt{0x15}$).


So, I found a way to do it but it's neither elegant nor a general solution. It relies on the (heavy) assumption that the initial chosen keyword is English and a second assumption that the resulting cipher text is also English. It then becomes a relatively crude bruteforcing exercise:

1) Choose an English word

2) Create a cipher instantiated by that word

3) Decrypt the ciphertext using that cipher

4) Check whether the decrypted plaintext contains English words

Using a relatively large wordlist (400k), it took around 30-40 seconds to break, the keyword itself was 9 chars long. As such, the solution would be completely unpractical if the keyword is random (which incidentally is the second part of this challenge and as such I will update this answer if I solve that one too).


There is a typo in the article. The primitive polynomial must be $$x^5 + x^4 + x^3 + x^2 + 1$$

The easiest way to see that there is a mistake or not is coding!
There is an almost good pylfsr library. This library also lists primitive polynomials in their format.
L.get_fpolyList(m=5)

[5, 2]
[5, 4, 2, 1]
[5, 4, 3, 2]

The list verified, too.

$x^5 + x^2 + 1$
$x^5 + x^4 + x^2 + x^1 + 1$
$x^5 + x^4 + x^3 + x^2 + 1$

I've created a python program to test these. Luckily I've found it on the first try!
import numpy as np
from pylfsr import LFSR

state = [1,1,1,1,1]
fpoly = [5, 4, 3, 2]
L = LFSR(fpoly=fpoly,initstate =state, verbose=False)
L.info()

for i in range(1,21):
    print(L.state[-1], end=",")
    if L.outbit == 0:
        L.next()
    else :
        L.next()
        L.next()
print("\n")
print("1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1")

It produces the output
5 bit LFSR with feedback polynomial  x^5 + x^4 + x^3 + x^2 + 1
Expected Period (if polynomial is primitive) =  31
Current :
 State        :  [1 1 1 1 1]
 Count        :  0
 Output bit   :  -1
 feedback bit :  -1
 1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,

 1,1,1,0,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1

Thanks to Nikesh Bajaj to indicate better usage of the library ( See in the other library).
Therefore there is a typo in the article. The primitive polynomial must be $$x^5 + x^4 + x^3 + x^2 + 1$$