What are the weaknesses of Shamir's Secret Sharing?

let's say have used a 64-bit secret key to encrypt a file and then we split the key into 2 pieces of 32-bit

That right there is your misunderstanding. Shamir secret sharing does not split a secret into pieces that are smaller than the original secret. Instead, it splits the secret into pieces that are the same size as the original secret.

A simple graphical example typically does the best job describing Shamir's method. Assume that my secret is the number $42$ and that I want to split this into $3$ pieces to give to my friends such that any $2$ of them can get together and recreate my secret. So my threshold is $2$, so I pick a random polynomial of degree $1$ (one less than the threshold) and set the zero term to my secret. So let's say my polynomial is $f(x)=42+17x$. To generate my shares, I evaluate the polynomial at the points $1,2,3$ and get $(1,59),(2,76),(3,93)$.

I then give one share to each friend.

Now, to understand the security of this, you need to think back to the line that we used to generate these shares. If I give you 1 point on the line, what does that one point tell you about the line that was used to share the secret?
 How many lines can you draw through that one point? The answer is infinitely many. So, by having that one share, you have gained no useful information about the secret.

That is the beauty of Shamir's method. Having the less than the threshold number of shares gives you no useful information. It is only when you have that one share that you have any useful information at all.


Yes it could work for simple ciphers. Here's a quick example:

# dependencies
import numpy as np

# machine learning
from keras.models import Sequential
from keras.layers import Dense

# constants
BASE = 97
MAX = 26

# let's assign a = 1, z = 26, ciphertext x and decrypted value y
y = np.arange(0,MAX,1)
x = np.roll(y,-7)

model = Sequential()
model.add(Dense(256, input_dim=1, activation='relu'))
model.add(Dense(128, activation='relu'))
model.add(Dense(64, activation='relu'))
model.add(Dense(32, activation='relu'))
model.add(Dense(MAX, activation='softmax'))

model.compile(optimizer='adam', loss='sparse_categorical_crossentropy', metrics=['accuracy'])

history = model.fit(x, y, epochs = 500, verbose=0)

for x_test in [['o', 'l', 's', 's', 'v'], \
               ['i','f','l'], \
               ['d', 'v', 'y', 's', 'k']]:
  x_test = list(map(lambda x: ord(x) - BASE, x_test))
  # print (x_test)

  pred = model.predict_classes(x_test)
  print(list(map(lambda x: chr(x + BASE), pred)))

Predicted output: link here

['h', 'e', 'l', 'l', 'o']
['b', 'y', 'e']
['w', 'o', 'r', 'l', 'd']


Extracting randomness from highly-biased RNG

If the source as 3 entropy bits per 1024 source bits, constructing a 128-bit seed requires $\lceil128\cdot 1024/3\rceil=43691$ source bits at least.

The "XOR 350 bits with jump 128 bits" translates to (correcting the question's formula)
$$o_i=n_i\oplus n_{i+128}\oplus n_{i+2\cdot128}\oplus n_{i+3\cdot128}\oplus\dots\oplus n_{i+348\cdot128}\oplus n_{i+349\cdot128}$$
That can not be guaranteed to work. For example, a source that outputs one truly random independent unbiased bit every precisely 256 bits, and outputs 0 the rest of the time, has a rate of 4 entropy bits per 1024 bits, but the 128-bit seed generated by the proposed method has a single bit of entropy (and worse, can take only two values).

Without a model of the source, a common solution is to hash the entropy source. That protects against a wide array of accidental failure modes (like unwanted feedback of the conditioned output to the entropy source). Of course, it remains of paramount importance, and difficult, to reliably detect a broken or rigged source that does not meet its assumed entropy rate.

For the utmost output entropy and common Merkle-Damgård hashes, it is best to truncate a hash wider than the output: there may not be quite 256-bit entropy in the output of SHA-256 with ample entropy in the input, in particular if the last message block hashed is constant. So for a 256-bit seed it is best to use SHA-512/256. For up to desired 240-bit seed, and all except adversarially rigged entropy source, SHA-256 truncated to the seed width is fine.

It is reasonable to use HMAC-SHA-512(K, N) truncated to the seed size, where N is the input entropy, and K remains unknown to the designer of the entropy source; this way, the best said designer can hope is make the output repeat, but s/he has no control on the values at the output.

EDIT: if the source is (the power-on state of) SRAM, and its addressing is natural (matches physical organization), then the proposed "XOR bits with jump 128 bits" entropy extractor makes me especially nervous: it is all too possible that all the bits entering a given $o_i$ share a common bias, because they are on the same row or column (or a small number of these). Using an odd jump could help somewhat. This illustrates the need to have a model of an entropy source to make recommendations about its conditioning.

Also, beware that adversarial control of the power-on conditions might reduce your entropy rate (think system reset without a power cycle after the RAM has been set to a repeatable state, slow controlled power rise at low temperature obtained by evaporation of an appropriate liquefied gaz, and other things hackers do); and that some marketed-as-SRAM really is DRAM with a hidden refresh, or could become so for cost-optimization reasons.

Even with the same mask set, the entropy rate might change drastically from one fabrication batch to another; it should at least be validated on "corner lot" wafers. Even if things are done once at wafer testing time, don't assume that all wafer testers will yield the same entropy, and that it won't depend on the testing temperature, which someone at the fab might decide to change (e.g it is common that at start of production of a new chip test is performed at several controlled temperatures, then move to different temperature(s) when the process has stabilized).

EDIT2: If the thing must be done in silicon, a 128-bit CRC for the source might be the way to go, e.g. using primitive polynomial $x^{128}+x^{99}+x^{62}+x^{33}+1$ (source: eq-primpoly-w5.txt in Jörg Arndt's useful and ugly page of mathematical data).

In a non-adversarial context, a CRC is a fine alternative to a hash, because for any natural entropy source (not designed with knowledge of the CRC polynomial, and not influenced by the CRC being computed), the output will be unbiased, and all input bits will have the opportunity to influence all output bits (for standard definition of CRC in crypto and telecoms, that is remainder of the division by the CRC polynomial of degree $k$ of a polynomial of degree $m+k$ which $m$ high-order coefficients are the entropy bits, and the $k$ low-order bits are zero).

Notice that "I don't have place to store all the needed ~50 Kbits" is no excuse not to use a hash or MAC: SHA-256 and HMAC-SHA-256 can be computed with 128 bytes of temporary memory, regardless of the input length.

FINAL NOTE: With that idea of RAM content as entropy source, be at the very least cautious about the (aforementioned) attack where an adversary makes a reset (or many) without removing power!


Has there ever been more then a theoretical difference between preimage resistance and second preimage resistance?

Yes, it has happened. If you look at the SHA3 hash zoo, there are a number of hashes who has the best attack listed as "2nd preimage".

One general place this can occur is if you have a hash function with a weak message compression step, but a fairly strong finalization step.  Here, we might not be able to generate first preimages (because we don't know what needs to be presented to the finalization step to generate that image), but we may be able to do a second preimage (because we attack the weak message compression, and generate the exact same data to the finalization).


The Encode algorithm of Garbling scheme is probabilistic or deterministic?

I don't know of any Yao-type garbling scheme where Encode is probabilistic. Think about Yao circuits - the encoding is providing the garbled key on the input wire for the associated bit. Note that the garbling is of course probabilistic and must be. However, once the garbling is fixed, the encoding is typically deterministic.

Having said the above, as a way of defining things, it is better to define it as probabilistic. This is due to the fact that although we don't know of any probabilistic way now, it doesn't mean that in the future there won't be. Since any deterministic algorithm is also (vacuously) probabilistic, this is more general.

This can also explain the confusion. As a definition, probabilistic is more general and thus preferable. But, in practice, Yao garbling using deterministic encodings until now.


Comparing Files: Is it better to use multiple hash algorithms or just one?

MD5 is vulnerable to a lot of collision attacks, so if you don't trust the users it is possible for them to make files which hash to the same value as other files but which are not in fact the same.

I think you are misunderstanding how a hash works though.  It does not read bits and pieces of the file, it processes the whole thing into a small output which is a "signature" of that file.  With very, very high probability (if your hash function is good) it is unlikely that two files will create the same hash if they are not, in fact, the same file.  But, it is not by itself any faster than comparing piecewise whether two files are equal.

Where it helps is when you have a bunch of files and you want to check whether a new file is the same as one that you already have.  You can store the individual hashes of the files, and then just check the hash of the new file against all of the existing hashes.  Now instead of manually checking file vs file over and over, you can just compare the small hash values.


I think that this notation "$(A,N_X,T_B),K_{BS}$" isn't correct and must be transcripted as "$(A,N_X,T_B).K_{BS}$", which could be interpreted as the resulting cipherText of "$(A,N_X,T_B)$ under the Key $K_{BS}$".
Under these conditions, we could try to understand that the attacker X begin by impersonating A, by sending to B the plainText $(A,N_X)$

X: Impersonating A:    X(A) -> $(A,N_X)$
B: Ask the Server to generate a shared key for A and B, But the message is intecepted by the Attacker who doesn't know the Master Key $K_{BS}$
The attacker then return back the initial cipherText to B, who can easilly decrypt as he knows its shared Key $K_{BS}$ with the trusted third part.

But there is a problem, this protocol doesn't work, because there is no generation of shared Key by the Server for A and B, and then B after checking the existence of Nonce and TimeStamp, and the absence of shared Key, must logically abort the session, under the assumption that a master Key is never and NEVER send in a plainText.


AES file encryption with PBKDF2. Safe parameters?

As this question is still on the list of "questions without answers", I'll quickly answer it (Basically repeating all of the above comments).

Increase iteration count to something larger (1 Million?)
You don't want to attach your HMAC of the plain-text after the contents. Rather authenticate either the ciphertext or (even better) use CCM/EAX/GCM mode.
Store the PBKDF's params in the header of the file.
Don't use PBKDF2 if possible. Rather use scrypt (best choice currently, for the next weeks), bcrypt (if no other option) or some of the PHC finalists.


Is there a cryptographic approach to availability

Flooding.  Consider a node on the internet in conversation with a peer.  Anyone can send packets to the node, but only the peer knows the secret key to compute authenticators for the packets so that the node will accept them.

The maximum amount of memory on the node that an adversary on the network can waste at any given time is the number of packets in parallel that the node can process times the maximum size of a message that the node is willing to accept.  Design your protocol with small limits on packet sizes and you reduce this denial of service vector.

For example, TLS records are limited to $2^{14}$ bytes, or 16 KB.  However, TLS is layered inside a TCP stream rather than a packet protocol (unless we're talking DTLS, which by the way gave us Heartbleed).  So there's no way for a TLS receiver to drop a packet on the floor—forgery of a TCP segment will kill an entire TLS session.  Same with SSH.  Oops.  Lesson: put crypto at a packet layer, not at a stream layer inside a packet layer.
The amount of bandwidth still available to the peer is the total bandwidth going into the node minus the amount of bandwidth used by the adversary.  There's nothing particularly cryptographic in here, per se—it's just a matter of network or processing capacity.  And remember that a well-designed high-level denial of service flood is indistinguishable from a large number of legitimate users.

Erasure.
Consider an erasure channel: if a sender sends a packet, the recipient receives it with some probability $p$, or the channel eats it with some probability $1 - p$.  An erasure code, such as a Reed–Solomon code, is a method for encoding a message into $n$ packets so that any $k$ of them suffice to recover the message.  This raises the probability of transmission, at the cost of bandwidth in the channel.  But it also sets a lower bound on the number of packets that an adversary must block before they block a whole message—or, alternatively, sets a lower bound on the number of packets that must make it through for a message to go through, namely $k$ of $n$.

For example, Tahoe-LAFS splits files (‘messages’) into Reed–Solomon shares (‘packets’) to store on different servers.  If an adversary like the world's biggest paperclip maximizer (‘capitalism’) decides to erase a storage node, you can still recover your data from the other storage nodes you stored them on.  (Tahoe-LAFS also encrypts each file before erasure-coding it, and authenticates each share so the worst the adversary can do is erase a share—attempts at forgery will be detected and function like erasure.)

Proof-of-work.
In the Bitcoin network, the fraction of processing power that an adversary controls determines the adversary's success probability at double-spending.  Knock off a competitor, and you get a bigger fraction of processing power.  (Of course, someone might notice a double-spend in a fork.  So there may also be a high expected cost to attempting this attack.)

A little more broadly, the study of how much performance can be attained in a network when a certain fraction of nodes are malicious is the study of Byzantine fault tolerance.  Is this ‘cryptography’, per se?  I don't know—ask three Byzantine generals and you'll probably get three different answers.  But it's the formal field of study for questions like this, with goals and adversaries and true love and castle-storming.


What methods allow us to determine the language used in a monoalphabetic substitution cipher?

I can't tell you which method is the best, but I can point out some places to look. The longer the message the easier it is easier to identify. How long is the message?

n-gram frequency: Look at the likelihood that groups of n-letters appear next to each other (often called n-grams). For example is does the n-gram AAA appear frequently (not many languages have words that contain the same letter repeated three times). N-grams are often used for language recognition. Bi-gram and Tri-gram (2-gram and 3-gram) frequency tables can be found here. Any long subsections of the ciphertext repeat?

Writing analysis Is this a hand written note? Often different languages that share the same character sets have different ways of writing characters (Germans/Mathematicians tend to put a line in the middle of their Z's, members of the US military tend to cross-slash their zero's).

Size of Alphabet: Are there 26 different letters in the ciphertext? Are the characters the standard latin alphabet. Any whitespace? Any punctuation? Numbers (many WW1 ciphers were broken by attacking ciphered numbers)? Capitals/Lowercase?

Plaintext: Do you have any clues about what the plaintext might be? Even if you don't know the language if you know that the ciphertext might be about battleships you can try translating water/gas/ships/boats/knots/depth into the candidate languages and see if you find any matches. You can try a similar approach with common words (equivalents of 'to be', 'to', 'it', 'hello' etc).


Cipher Feedback Mode - sizes of the blocks and shift registers

I dont understand which special case the first picture describes. Is really the entire ciphertext (after the XOR with the plaintext) is taken as the argument in for the next block or just s bits?

It depends on what version of CFB you're using.  In the olden days, they used to try to encrypt (but not integrity protect) communication channels.  What some random (non-attacker generated) errors could do on these channels is insert or remove a few bits or bytes.  If we consider (say) CBC mode, this insertion or deletion would cause the blocks on the sender and receiver to not line up, and so receiver would just get gibberish.  What the special property of CFB-s is that, assuming if we insert/delete a multiple of s bits, the next 64 bits (assuming DES, after all, this is the olden days) would be garbled, but then (assuming no further errors) everything else would be received properly.  Now, the cost of this is that each set s bits would require a separate DES encryption/decryption, however this was deemed an acceptable cost.

Now, in the more modern days, we don't care about this resynchronization property (we assume instead if the decryption result isn't exactly the same as the original plaintext, it needs to be discarded), and so if we use CFB mode at all, we use the full size (CFB-128, assuming AES, after all, we've stepped back into the modern days).

Because we don't care about CFB-s for s < 128, modern descriptions omit the shift registers (which are no longer needed).

And, to answer your questions

  Is the resulting ciphertext of this operation always the size of the Key (128 bits in this case)?

Nope; the size of the ciphertext is always the same size as the plaintext, that is, 256 bits (plus the IV if you explicitly send it).

  What is the resulting ciphertext at the end?

The ciphertext generated by the CFB process is all the blocks.  After all, if we encrypt a 256 bit block, it'd be rather hard for the decryptor to reconstruct it if we handed him a 128 bit block...


Is there an additive homomorphic encryption that supports exponentation

What you want is a cryptosystem that supports linear operations, and some bounded number of multiplications (supporting exponentiations by bounded values is equivalent to supporting multiplication, as to compute a*b homomorphically, you can always compute (a-b)²-a²-b² homomorphically and divide this by two). Without requiring a bound on the number of multiplications, this is just fully homomorphic encryption.
With a bound, it is known as somewhat homomorphic encryption (SHE). Most constructions for SHE are based on lattice assumptions (such as LWE). A noticeable exception is the Boneh-Goh-Nissim (BGN) cryptosystem which uses pairing based cryptography; the scheme is homomorphic for linear operations and one multiplication (e.g. one squaring as in your example), in any order (e.g. the function f:(a,b) -> a² + b² can be computed homomorphically with the BGN scheme). However, as decryption requires a discrete logarithm, the plaintexts must be small for the decryption algorithm to be efficient.
However, for your particular example, there is even a simpler way: there is a generic conversion from any linearly homomorphic encryption scheme (with some reasonable properties) to an homomorphic scheme that supports linear operations, then one multiplication, then a bounded number of linear operations (once the multiplication was performed, the ciphertext grows linearly with the number of additional linear operations you perform). The article is "Boosting Linearly-Homomorphic Encryption to Evaluate Degree-2 Functions on Encrypted Data". f:(a,b) -> (a-b)² is typically the kind of operations supported by this conversion. Such a cryptosystem can be constructed from the (additive variant of the) ElGamal cryptosystem, or the Paillier cryptosystem, for example. From the Paillier cryptosystem, you get such a degree-two homomorphic cryptosystem, with no restriction on the plaintext size as in ElGamal or BGN.


I thought that the seed for BBS was computed via prime multiplication.

This is not how BBS works. To help better understand the seed, it's necessary to explain BBS.
Blum Blum Shub is realized in the form of $x_{i+1} = x^2_i \bmod N$. The initial seed, $x_0$, merely has to be co-prime to Blum primes $p$ and $q$ (where $N = p\cdot q$, making $N$ a Blum integer), and must not be $0$ or $1$. The seed is $x_0$, not $p$ and $q$ (which were likely generated once to create the hardcoded $N$ and then thrown away*). They are likely using the raw hash output as the seed, since it's unlikely that it won't be co-prime to $N$. They give you the modulus on the page you linked, but not the primes:

5360751114622011236087979022735306713592537659947455285353148181
8526455500785383194936281698585494806464721601253386562653528822
5543322562532917886396992291116815877218495559211688377961466145
0857446201926232198015028137924055146650866097197909406089918491
4133568666470293429076893274969016410915119621659901793350665953

This is a 1062-bit modulus. Unfortunately, it seems that BBS can be broken† up to $10^{54} n^3$ times faster than it takes to factor the $n$-bit modulus. This means that BBS used with their parameters can be broken $10^{54} \times 1062^3 \approx 1.20 \times 10^{63}$ times faster than it takes to factor the modulus, which is a significant enough speedup that the proof is completely useless. Additionally, the proof assumes only a single bit is extracted from each $x_i$ (officially by taking the parity of $x_i$). If more bits are extracted at a time, it becomes even weaker. Parameters that seem acceptable are terrible for BBS.
The security proof for BBS is only a reduction to a problem with no known solution. That is, a correct implementation (i.e. one where only one bit is extracted from each $x_i$, and only when the modulus is "sufficiently" large) can only be broken if the quadratic residuosity problem (QRP) is solved.‡ It is "proven secure" in the same way that RSA is "proven secure" because a proper implementation is provably reducible to the security of the RSA problem (the difficulty of finding the $e^\mathrm{th}$ root of an integer, modulo semiprime $N$), but no one thinks of RSA as having perfect security. In other words, BBS has a security reduction to a yet-unproven problem, and is not information-theoretic secure.

How can above steps 600 and 605 be connected together?

Are you asking how the 140-byte seed comes from the 160-bit hash? That is actually answered in the link you provided. There are seven SHA-1s. The seventh hashes every seventh byte, the sixth hashes every sixth byte, etc. The bytes come from an image of the lava lamp itself. The final hash values are concatenated to form a 140-byte (1120-bit) value. This value is used, directly, as $x_0$.
* The only thing you are losing by not having access to $p$ and $q$ is the ability to calculate any $x_i$ value directly from $x_0$ without having to calculate $x_1 \cdots x_{i-1}$ first. Euler's theorem can be used to do $x_i = (x_0^{2^i \bmod \lambda(N)}) \bmod N$ where $\lambda$ is the Carmichael totient function. If an attacker factors $N$, they can do this as well, breaking the security reduction.
† Broken in this context does not refer to the ability to predict the random stream or recover the seed. Instead, it means the security proof is invalidated and that the algorithm is no longer reducible to a known hard problem and that a break could exist which does not rely on solving QRP. Critically, it does not automatically imply that such a break does, in fact,  exist.
‡ Although the quadratic residuosity problem is often thought to be as difficult as integer factorization, this has not been proven. It is possible that a method to break BBS could be exist which solves QRP without solving integer factorization.


Derive operations from an arbitrary number

Is there a formula to do that?

Your example looks like a problem about Partitions to me. A partition is a way of representing a positive number as a sum of $n$ positive integers, for example:

The partitions of the number $5$ are:

$5 \space (+0)$
$4 + 1$
$3 + 2$
$3 + 1 + 1$
$2 + 2 + 1$
$2 + 1 + 1 + 1$
$1 + 1 + 1 + 1 + 1$

Since partitions consider every possibility valid, the number for possible ways of any integer $n$ can grow very fast, i.e. the number of possible partitions of the number $100$ is $190,569,292$.

There exist some formulas (some more complicated or faster than others and some are only approximations).

In your example you only have an operator once, so here $4 + 1$ and $3 + 2$ would be a possiblity.

Since you mentioned "more than one operation", a possibility would also be to represent numbers as their prime factors, for example:

The prime factorization of the number 22 is:

$2 \times 11$

There's always only one possiblity to represent a number as it's prime factors (if you don't care about the way you write it ($2 \times 11$ is the same as $11 \times 2$)).

There are a lot of factoring algorithms, since this is still a unsolved problem (Does P = NP ?) and this problem is important for cryptography.

I assume that a problem occurs if you'd try to do this with the operators of division and subtraction, for example:

There are infinite possibilities to represent a number as a subtraction, for example:

For the number $5$:

$6 - 1$
$7 - 2$
$8 - 3$
$9 - 4$
$\ldots$


Name and security of these non-invertible functions?

If I understood your question correctly, you want a message authentication code (MAC). The "hidden input" is usually called key and the "visible input" is just the message. The output of the MAC is called tag (or also MAC).

The main security goal for MACs is resistance against forgery: It should be computationally infeasible for an attacker who does not possess the key to obtain a valid tag for any message whose tag they have not observed before.

Common variants of that primitive include HMAC, CMAC, or Poly1305-AES, just to name a few.

Now, about your algorithm: Usually, homebuilt ad-hoc constructions are a very bad idea. Unfortunately, I did not find a trivial way to completely break yours during the few minutes I thought about it, even though I'm sure the mathematical properties of the sine function are highly useful to attack it. However, if you look at the examples I just linked, you will see that these are quite a bit more complicated than your proposal — and there is a reason for that. Many simple constructions suffer from unforeseen vulnerabilities once examined a bit more carefully: My favourite example is the "keyed hash" $\mathit{msg}\mapsto H(\mathit{key}\Vert \mathit{msg})$, where $H$ is a Merkle-Damgård hash such as MD5, SHA1 or SHA2. This suffers from a length extension attack and is thus not a secure MAC even it may seem so at first.

The bottom line is: Crypto is hard. Please use one of the well-established primitives from a well-established implementation if you have to protect anything of importance.


Why is "semantically secure" important for cryptosystems?

Let me try to answer your second question, and hopefully shed some light on the first one in doing so.

When we encrypt a message, it's because we want to keep something about that message secret.  But what is it that we actually want to protect?

Let's say the message we're encrypting is AGENT DOE REPORTS 23 UNITS ON BOARD SHIP TO BASE ALPHA, DEPARTED ON THE 20TH.  Is the secret that we wish to protect the name of the agent, or the number of units, or their destination, or their time of departure?  All of those?  Something else?

When designing a general-purpose encryption scheme, we really cannot know which aspects of the message being encrypted are sensitive.  Perhaps the user of the encryption scheme wants to pass off the message above as a routine weather report, and even just allowing the adversary to detect that it's probably not a weather report would count as an unacceptable security failure.  We can't know.

What we really want to do is to prevent an adversary (who does not know the key) from learning anything about the message.  That is, seeing the ciphertext should not allow the adversary to guess any property of the message with a better chance of success than if they had not seen the ciphertext.*

In other words, what we really want is perfect secrecy.  Unfortunately, as Shannon famously proved, perfect secrecy against an arbitrarily capable adversary is impossible to achieve unless the number of possible keys is at least as large as the number of possible (sequences of) messages encrypted with a single key.  In practice, this makes true perfect secrecy all but impossible; in particular, as it requires the key to be as long as all the encrypted messages combined, securely distributing the key becomes (almost) as hard as securely distributing the messages would've been in the first place.**  This is true for a simple reason: if there are $N$ possible keys, and $M > N$ possible messages, then the attacker can simply try to decrypt the ciphertext with each key, and thereby rule out those (at least) $M - N$ messages that are not the result of decrypting the ciphertext with any key.

However, in practice, even with the most powerful computers available today, no conceivable attacker can test more than, say, 1,000,000,000,000,000,000,000,000 keys, give or take a few factors of 1,000.  So if we just make the keyspace reasonably large (and it's not very hard — a random ten-byte key has more possible values than the huge number given above, and we can always add a few more random bytes for good measure), we can hope to make an encryption scheme that, even if theoretically not perfectly secret, is just as good in practice.

Informally speaking, this notion of "practically perfect secrecy" is just what semantic security is.  Or, to quote Goldwasser & Micali (1984)***:

  "Whatever is efficiently computable about the cleartext given the cyphertext, is also efficiently computable without the cyphertext."

The tricky parts of the formal definition (which I'm not going to give here; look it up in your favorite crypto textbook), involving strange theoretical concepts like asymptotic complexity and probabilistic polynomial-time algorithms, comes from trying to formalize this notion in terms of computational complexity theory, without assuming any specific computer hardware or resources for the attacker.

Basically, the reason for doing this (besides just wanting to make use of the toolkit that complexity theory gives us) is that, in practice, we won't really know just how much computing power the attacker can spare to break our encryption.  But we do know that, if the only (or at least the biggest) weakness of our encryption is the limited size of the keyspace, then we can increase the number of possible keys exponentially just by making them a little bit longer, with (typically) little impact on encryption speed, whereas the attacker can only increase their computing power linearly by buying more computers (and in general, only polynomially even by switching to a more powerful model of computation).

Thus, if we can prove (at least, subject to some reasonably plausible assumptions) that the difficulty of breaking our encryption (i.e. learning anything about the message) increases faster than any polynomial function of the key size, then we can safely conclude that we can make the encryption practically unbreakable by any given (or conjectured) adversary just by modestly increasing the key length.

*) Note that there's a hidden "gotcha" in the standard definitions of both perfect secrecy and semantic security: the length of the message is assumed to be public knowledge, and thus not necessary to conceal.  The reason for this is simple: the only effective way to fully conceal the length of the message is to pad all messages up to the length of the longest possible message; and if the message length is potentially unbounded, even this is impossible.  But this "gotcha" is indeed a practical issue, and can easily translate into real, practical attacks, like the CRIME and BREACH attacks against HTTPS.

**) The one practical advantage of OTP-like schemes with perfect secrecy is that you can distribute the keys before you know what you want to encrypt.  Even so, secure key generation and distribution is still the hard part of any such scheme.

***) This paper also contains a nice, and in some sense the archetypical, proof of the (conditional) semantic security of the cryptosystem defined in it.  If you want to see an example of how such proofs are done, this is not a bad place to start.


You can use Sage or MATLAB. Among the two sage is free and uses python as the programming language.


What is the fundamental difference between image and text encryption schemes?

TLDR: None worth academic interest.

All modern encryption techniques intended for digital computers are applicable, and secure, for all kinds of digitized data, including text and image. There is no need for such encryption specialized to image or text. Argument: the modern baseline for encryption security is resisting Chosen Plaintext Attack, and that model assumes the attacker can choose the plaintext, including image in whatever format.
We can encrypt image, or pretty must anything digital, with e.g. AES-CTR or Chacha. These are widely available on most computer platforms, there is no known attack against them (baring side-channel attacks and IV reuse, which really are attacks on the implementation), and with a competent implementation, speed is faster than most processing peripheral to image processing, like compression, transmission, storage.
From a sampling of papers on image encryption (those at MDPI are free access), most have precisely no advantage over standard techniques: these paper's technique typically is slower and comes with weak security claims (often, relying on some standardized algorithm or metric; that's even though, assuming the existence of secure encryption, we demonstrably can't make a polynomial-time algorithm that recognizes good from bad encryption by examining ciphertext and plaintext). Reasons for why these papers are published (often, for a fee) are discussed there. Whatever these reasons are, peer-reviewed IACR publications seldom if ever buy them: I've only found preprints with this query.
Still, there are a few legitimate reasons to special-case image:

It calls for special techniques for the most efficient data compression (before encryption), in order to exploit the correlation between nearby pixels and characteristics of the human eye. There is an interaction with encryption, in that we must be careful that the compressed size does not leak exploitable information.
When we want the ciphertext to be a meaningful image: steganography, and Thumbnail-Preserving Encryption (where plaintext and ciphertext are images, and the ciphertext a thumbnail of the plaintext).
When we want decryption by analog means, such a superposition of transparencies. That's visual cryptography, a legitimate (if limited) field of research.
If we also wanted encryption by analog means. That's the goal of optical image encryption. It has been theorized in this (extremely cited) article (1995), and demonstrated experimentally (1996). I find several reports that it is practically broken in a ciphertext-only setup believable. There are countless variations, many simulations only with bogus security argument.


How to reduce factorization into Independent Set Problem?

IF can be reduced to 3SAT. This was already addressed here before - https://cs.stackexchange.com/questions/11718/generating-3sat-circuit-for-integer-factorization-example

It should easy to convert that 3SAT to ISP - http://www.mi.fu-berlin.de/wiki/pub/ABI/ComputabilityComplexityWS11/Complexity2.pdf


How to be able to change the password to access data encrypted with AES-GCM, without reencrypting?

This is case for the Fundamental theorem of software engineering which states:

"We can solve any problem by introducing an extra level of indirection."

In this case what is usually done is introducing an extra randomly drawn intermediate key (usually called "data encryption key, DEK").
You then encrypt the DEK with a key derived from your password (also sometimes called "key encryption key, KEK") and whenever you want to change the password you simply rederive the KEK, decrypt the DEK and derive the KEK under the new password to encrypt the DEK with (also preferably using a fresh salt).


What systems of robust steganography are out there?

The field of research that deals with robustness is watermarking. There are hundreds of techniques to deal with the different existing attacks (resize, crop, recompress, etc).

Currently there is no system that overcomes all possible attacks. But there are some approaches that solve a lot of attacks under certain circumstances.

For example, this is a classic paper for solving RST (Rotation, Scale, Translation) attacks.

But I think the most robust current methods are based on zero-bit schemes. Check, for example, this paper.

I suggest that you define the most important attacks for your application, and try to find papers that deal with these attacks. But it is quite complicated to implement these techniques for non-experts in the field.

The alternative is to try to deal with the different attacks by using simple techniques. For example, use a copy of the original image for mark extraction. This keeps things easy.

Use a DCT transform of the image. Then hide information by modifying the DCT coefficients. You can recover the original DCT coefficients from the original image and the mark from the differences between the original and the marked image.

This resists the resizing process to some degree. If the user makes a crop, use the original image to find the same crop in the original image. Then you can recover the mark as before. The same procedure can be used to deal with rotation.

This approach has many problems, but it provides you with an easy starting point.


Can a TLS certificate using ECC secp384r1 as PK algorithm uses RSA for signature

No, RSA cannot be used as a signature algorithm if the certificate has an EC public key in it - you're restricted to ECDSA. You would not be able to verify the signature using the public key after all. The algorithm used must comply with the public key algorithm. However, some keys can be used for different related signature schemes, e.g. RSASSA-PKCS1-v1_5 and RSASSA-PSS (although TLS 1.3 only allows PSS style signatures).

Previously RSA could also be used for session key establishment / authentication using encryption / decryption of the master secret value: the cipher suites starting with RSA_. That use has been deprecated in TLS 1.3, but it is certainly incompatible with EC certificates in versions earlier than TLS 1.2.


What you are proposing is bad.

RSA-KEM uses RSA encryption without padding, but not in the way you are proposing. See the second part of its Wikipedia Page

The problem with your construction is that if you encrypt a short message (i.e. AES key) with RSA without padding, then it might get decrypted through e-rooth calculation or through Coppersmith.
It actually depends on the message size and on your public key, for example if your public key is $e=3$ then you just need to compute $(E_{pk}(random\_key))^{(1/3)}$ to get the decrypted text.

In order to properly use RSA-KEM you first need to generate a random message $m: 1 < m < N$

Then derive your AES from it: $key=KDF(m)$

And finally encrypt your message with $key$ and send it along $E_{pk}(m)$.

Note that there are variants:

You can derive, with the same KDF call another key, used to MAC your (encrypted) message.
Or as specified in RFC 5990 with the KDF you generate a KEK (Key Encryption Key) which is then used to wrap the actual AES key used for the message encryption. This has the benefit to allow KEM to be used with an already encrypted message.


Reveal a plaintext with 3 encryptions of Textbook RSA


A general definition for cryptocurrencies

I write here a partial answer to my own question (but it is only partial, feel free to write an answer of your own).

In the book "Introduction to Cryptography with Coding Theory" (2nd edition), by Wadde Trappe and Lawrence C. Washington, chapter 11, Digital Cash, p.288, we can find the following list of properties coined by T. Okamoto and K. Ohta:

  The cash can be sent securely through computer networks.
  The cash cannot be copied and reused.
  The spender of the cash can remain anonymous. If the coin is spent legitimately, neither of the recipient nor the bank can identify the spender.
  The transaction can be done offline, meaning no communication with the central bank is needed during the transaction.
  The cash can be transferred to others.
  A piece of cash can be divided into smaller amounts.

In the article "Blind Signatures for Untraceable Payments", by David Chaum, the digital cash holds the following properties:

  Inability of third parties to determine payee, time or amount of payments made by an individual.
  Ability of individuals to provide a proof of payment, or to determine the identity of the payee under exceptional circumstances.
  Ability to stop use of payments media reported stolen.

From all theses definitions, the definition I would find the most suitable is the following (I obviously forgot to speak about the security of each transaction):

Security of Transactions: Transactions between several participants must
be secured and non-repudiable. It must not be possible to pretend to
be someone else during or after a transaction or to spend more
cryptocoins that we really have.
Unfalsifiability: The creation of new legitimate (or not)
cryptocoins must be under strict control of the system.
No double spending: Once cryptocoins have been spent for a
transaction, they must not be reusable by the original owner in
another transaction.
Centralized/Distributed (Altnerative): The transactions using
the cryptocurrency is done in a centralized/distributed manner.

Then, comes optional properties:

Anonymity (Optional): A transaction may be anonymous, meaning
that the previous owner of a cryptocoin should not be easy to find.
Fraud tracing (Optional): A fraudulent transaction may lead
to the unveiling of the original fraudster.


You've been given the key length, plus half the characters in the key text. By the look of things, the ciphertext even contains word spaces and punctuation, which will help a lot.

Start by decrypting the text using the characters you already know:

> Peit Wokm! Mhfa fepatgb ets bvvrvxmea ebte bae twkd qiqi
  .a.i .a.i  .a.i .a.i.a. i.a .i.a.i.a. i.a. i.a .i.a .i.a
< .e.l .o.e! .h.s .e.s.g. w.s .n.r.p.e. w.t. t.e .o.d .a.i

Assuming the plaintext is English, it seems likely that the first character of the key is t, since this would decrypt the 5th and 8th words to was and the. Let's see how that changes things:

> Peit Wokm! Mhfa fepatgb ets bvvrvxmea ebte bae twkd qiqi
  ta.i ta.i  ta.i ta.ita. ita .ita.ita. ita. ita .ita .ita
< We.l Do.e! Th.s me.sag. was .ncr.pte. wit. the .ord .axi

Actually, you can stop here. It's already obvious what the message says.


I recommend Chris Peikert's survey, called A Decade of Lattice Cryptography.


homomorphic encryption E(x+y)=E(x) . E(y)?

could you please tell me what is it that I'm missing ?

Typically, when we write $a \times b$, the operator $\times$ needn't be multiplication over the integers (or reals or complex numbers).  Instead, it is often some group/ring/field operation that is somehow analogous to the more common multiplication operations we all learned in grade school.

That's exactly what is happening here.  In this case, the elements $a, b$ (or, in this case, $E(x), E(y)$) are understood to be elements in the group $\mathbb{Z}^*_p$, and so the multiplication is done in that group.  That multiplication can be implemented by performing a standard integer multiplication, and then taking the result modulo $p$; writing that out explicitly gives your result.

So, why do we do such a short-hand? Are we lazy?  Well, partially, yes, we have no reason to clutter the equations with things that are well-understood.  On the other hand, sometimes we work with things, such as extension fields, or elliptic curve groups, which do not have such a simple "do a normal addition/multiplication and then fix things up" way of looking that things; trying to write things out explicitly in the 'grade-school approved notation' would be tricky...


How is an X.509 public key used for TLS?

When a (EC)DHE (non-anon) cipher suite is used, the server's public key is used to verify the signature of the ServerDHPublic. Diffie-Hellman is an anonymous key-exchange protocol. A signature is used to make sure that the client is talking with who he thinks to talk and no MITM attack has took place.


What is the complexity of the Square attack against the reduced 4-rounds 128-bit Rijndael variant?

There are two well-known distinguishers of reduced-rounds version of AES based on integral cryptanalysis. The first one is a 3-rounds distinguisher from Daemen and Rijmen while the other is a 4-rounds distinguisher from Gilbert and Minier.

The 3-rounds distinguisher relies on the fact that one byte $y$ of the state in the third round is the xor of four one-to-one mappings $z_i:x\mapsto z_i(x)$ from a given byte $x$ in the state of the first round, and therefore, on the property that $\sum_{x\in GF(2^8)} \left[z_1(x)+z_2(x)+z_3(x)+z_4(x)\right]$. Hence, the distinguisher requires $2^8$ (well crafted) plaintexts and as many encryptions, but basically no memory.

The 4-rounds distinguisher relies on the fact that the above-mentioned byte $z$ is actually a function of $x$ and three constants $c_1$, $c_2$, $c_3$ hereafter referred to as $c$ and the probability that there is an unusually high chance that the functions $z_{c'}$ and $z_{c''}$ are equal: this can be tested through the equality of the linear combination of four bytes resulting from the encryption of the two corresponding plaintext. The property is observable after browsing through $2^{16}$ values of $c$ (and enough of the possible values for $x$). Hence, the disinguisher requires about $2^{20}$ plaintexts and as many encryptions as well as less than $2^6$ bytes of memory.

These distinguishers are meant to be turned into key recovery attacks, but these extend to at least 6-rounds AES. Since you mentionned 4-rounds attacks without further details, I assume you referred to one of the above. If you need a more precise answer, you should refine your question. Also, make it precise which version of Rijndael you're referring to as it may impact the underlying complexity.


You have asked about the authentication of a hand-written message, but let's also include an integrity check as a desired service.

Let's say that your message was encrypted with a one-time pad. The following methods of early modern cryptography will not do:

  (1)  Russian
  copulation  (which is designed to further conceal names, headers, salutations, etc.)

  (2)  Variable-length padding

  (3) Using a reasonably-sized tabula recta

For example:

Plaintext (your message):        DONOT  NEGOT IATE
Truly random key:                JQOXF  RMSUA PWBI
                                -------------------
Ciphertext:                      MEBLY  EQYIT XWUM

Variable padding added:

KIPXQ NECEM EBLYE QYITX WUMRZ NUDOA DIEHL ARAIT EMONG ESEBO SLAVO

But this is no solution.  People used to simply take it for granted that the message was authenticated because their pre-shared symmetric key worked to decrypt it.

Option A

However, one could take advantage of having pre-shared secrets, especially with the OTP because this must have already been done anyway.  First, determine the size limit of the ciphertexts that will be sent. For example--choose thirty-one characters-- and draw a box, say 31 columns wide and 34 rows deep.  Write the plaintext across the top in the first row.  Yes, this is going to be a short message, but notice that this system might be amenable to using code. Next, under each character of the plaintext, write the predetermined 31-character authenticator for that character.  For example:

DONOT NEGOT IATE  (__truly random, pre-established, one-time, filler__)

DONO...
FTID...
GWOZ...
NRFG...
RIUW...
QESD...
JFLK...
GUEE...
MUNF...
ARAI...
TEMO...
NGES...
EBOS...
LAVO...
WAZY...
QLYX...
etc.
etc.

To clarify, this means that each character in the plaintext will have a thirty-one character authenticator, and these will always be different (which recalls homophonic substitution and your reference to Mary Queen of Scots).

It is crucial that all of these values be generated in a "truly random" manner.

There will be a table similar to this:

If 1st character is "A" =  KFGEIOGZUZDOITSEHAJNWNSYFEBMAXY
If 1st character is "B" =  BREHYEMKIDHFDDJBDIHTDZGDOODYHWV
(etc.)
If 2nd character is "A" =  VRDABALALAJEOQZFURJVLPQWVMVAECZ
(etc.)

So, each character in the ciphertext will correspond to one of the 26 possible authenticators, and this is going to end up being a little booklet of truly random values.

The last two rows will be a truly random authenticator which will match the indicator tag.  The indicator tag will appear above the message, and will mainly be used for convenience--to indicate message sequence and which key to use.

For example (which is not to be encrypted):

AVRAL OBESE XIANG POLAR GRIME TIARA HANOI THUGZ

It will, of course, correspond with the shared secret authenticator in the last two rows of the message.  Both will be non-sequential.  The shared secret authenticator will only be used once. As you can see, the pre-established size of the message is very important.

Again, the authenticator will be 62 characters long and take up the last two rows of the message.

For example:

ATSOHKIFZPYTSWTEHKANNAVASUUXWO
IMDYSDFFLHTGEISOUBZFWQBXRQOKSI

Now, pass your intended one-time pad key over the whole thing.

Note:  for this option we could expand the alphabet for added strength. Everything is going to depend on the strength of the key, and a long key it will be.

Option B

Using Poly1305 by hand might be a solution, but that is going to take some work. You are also going to have to devise a method for adding that information to your message.  Poly1305 has a 32-bit preshared key that cannot be reused. Good advice, coming from forest and, graciously, from Ross J. Anderson himself, says use a Carter-Wegman universal hash function.

Option C

Construct a one-time MAC according to these instructions.


If RSA is limited to 117-200 bytes or so, is that a very limited use case?

In practice, asymmetric algorithms like RSA are usually used for key transport. In other words, instead of a true message, they are used to encrypt a secret key for a symmetric cipher.

That symmetric cipher key is used to encrypt the actual message, and that could be gigabytes, depending on the algorithm.

Standards like TLS, PGP, and S/MIME use RSA in this way.

By the way, a limit of 117 bytes is for a 1024-bit RSA key. Keys that small are no longer recommended.


Using same keypair for Diffie-Hellman and signing

The paper "On the Joint Security of Encryption and Signature in EMV" shows that ECIES and EC-Schnorr signatures can be used together without compromising security:

  In the random oracle model ECIES-KEM and EC-Schnorr are
  jointly secure if the gap-DLP problem and gap-DH problem are both hard

Ed25519 is extremely similar to EC-Schnorr, and both ECIES and Curve25519 are based on EC-DH, so this gives some indication that using both Curve25519 and Ed25519 with the same key-pair is secure.

Still a proof that directly refers to a keyexchange as used in Curve25519 would be nice.


what is the motivation behind quantum key distribution with Continuous variable?

It's easier to work with a lot of photons in a stream than to work with a single photon at once.  This is explained in the paper introducing continuous-variable quantum key distribution.  (With apologies for the paywall.  Ms. Greene, tear down this wall!  Or read the arXiv preprint if you're not a rebel.)

P.S.  I originally answered the question as follows, with the above paragraph at the end, and the answer was accepted.  It spawned a long discussion in comments and chat, but, while it represents my perspective on the market for quantum key distribution products today in the context of information security and cryptography, it wasn't appropriate as an answer to the question as asked, about continuous-variable quantum key distribution in the context of the basic research program of quantum key distribution in physics.  I am leaving it here for context of the discussion:

  One word: money.

  Quantum key distribution networks serve no useful cryptographic purpose.

  They do not work without classical cryptography to authenticate the peers.
  The best speeds for quantum key distribution are measured at megabits per second rather than the gigabits per second achievable by classical cryptography on $100 mass-market CPUs.
  The widely advertised security guarantees founded on laws of physics are nonsense.

  But because rich governments are apparently easily bedazzled with mumbo-jumbo about laws of physics guaranteeing security, it is highly profitable for companies like ID Quantique and MagiQ Technologies to sell packages of snake oil at hundreds of thousands of dollars a pop.

  As for the specific case of continuous-variable systems...

  (Financial disclosure: I'm not getting a piece of the pie that ID Quantique and MagiQ Technologies are splitting.  But then I'm also not getting a piece of any pie in classical cryptography either.  In fact I'm pretty bereft of pie at the moment.)


Relationship between generating elements given by cycles in Cayley graph

By the Chinese remainder theorem, we have that:
$$(\mathbb{Z}/pq\mathbb{Z})^* \cong (\mathbb{Z}/p\mathbb{Z})^*\times (\mathbb{Z}/q\mathbb{Z})^* \cong (\mathbb{Z}/(p-1)\mathbb{Z})\times (\mathbb{Z}/(q-1)\mathbb{Z})$$
From this, we should be able to write:
$$(\mathbb{Z}/pq\mathbb{Z})^* \cong \langle g_q, g_p\mid [g_q, g_p] = e, g_q^{q-1} = e, g_p^{p-1} = e\rangle$$
Where $e$ is the identity element of the group, $[g_q, g_p]$ is the commutator, etc. Essentially, this is the free abelian group on two generators, subject to the relations on the order of the generators that come from the CRT representation.

We can then write all the quantities you talk about in terms of the generators $g_q, g_p$.
Say that $z = g_q^{z_q}g_p^{z_p}$, and $y = g_q^{y_q}g_p^{y_p}$.
Then your equation:
$$y^r = z\implies g_q^{ry_q}g_p^{ry_p} = g_q^{z_q}g_p^{z_p}\implies g_q^{ry_q - z_q}g_p^{ry_p - z_p} = e$$
Gives us the "cycle". In particular, if you view the Cayley graph as being on vertices of the form $g_q^{x}g_p^{y}$ (so we can sort of visualize it as being some subset of $\mathbb{Z}^2$), this reduces the problem of finding cycles to finding points $(y_q, y_p)$ such that $(ry_q \equiv z_q \bmod (q-1))$ and $(ry_p\equiv z_p\bmod (p-1))$.
You may want to enforce some non-triviality condition (such as $ry_q\neq z_q$ and $ry_p\neq z_p$), I'm not sure.
If you want to find the minimum/maximimum length cycle, you could then find the minimum/maximum non-trivial $(y_q, y_p)$ such that $ry_q \equiv z_q\bmod (q-1)$ and $ry_p\equiv z_p\bmod(p-1)$. Note that if you know the factorization of $N = pq$, you can compute $y_q \equiv r^{-1}z_q\bmod(q-1)$ and $y_p\equiv r^{-1}z_p\bmod(p-1)$ easily (assuming $r$ is invertible in both rings), and then find particular representatives $(y_p, y_q)$ with properties you want by searching through the cosets $r^{-1}z_q + (q-1)\mathbb{Z}$.

I believe we can read off the length of any cycle fairly easily.
In particular, a cycle is a path from $(0,0)$ in $\mathbb{Z}^2$ to $(k_q, k_p)$ such that $k_q\equiv ry_q-z_q\bmod (q-1)$ and $k_p\equiv ry_pz_p\bmod(p-1)$.
The length of the shortest path from $(0,0)$ to $(k_q, k_p)$ is therefore $|k_q| + |k_p|$, which is the length of your cycle.
As $k_q\equiv 0\bmod(q-1)$ (and similarly for $k_p$), we see that the length of any cycle must be of the form $|a_p|(p-1) + |a_q|(q-1)$ for non-zero integers $a_p, a_q$, which puts some restrictions on which possible lengths are achievable (this is related to the Frobenius coin problem). There are likely upper bounds on $a_p$ and $a_q$ which come from the group relations of the type $g_q^{q-1}$, but this requires defining a good notion of "trivial" cycle first.

As for the computability of this, it can be efficiently computed if you know the factorization of $N = pq$ (all of the discussion above does this), and (likely) can't without this. I don't know if there are any gains to rewriting RSA in this way (I don't see any immediately), and don't guarantee the computations above are correct, but they seem vaguely right to me at least.

One thing to worry about is compact representation of the edges. All of the above required knowing the factorization of $N$. If we remove this, then we can abstractly view the cayley graph will as a graph on $\phi(N)$ vertices, which as $p,q\approx 2^{n/2}$ will be $\phi(N)\approx 2^n$.
Vertices can be communicated by indexing into $[\phi(N)]$, and since the graph is 4-regular (I think, edges from each vertex being $\{g_p, g_p^{-1}, g_q, g_q^{-1}\})$ each particular edge can be efficiently described. But I don't know how you can efficiently transmit the entire graph, as there are $O(2^n)$ edges, meaning that treating it as an abstract graph means you cannot efficiently communicate it.

Of course there are efficient ways to "compress" the graph (this must implicitly be done in traditional RSA-based cryptosystems), but its unclear how much of that compression will generalize to other groups, which appears to be your intention.


How can frequency analysis be applied to modern ciphers?

Classical ciphers operate on letters. If we consider the frequency attack on classical ciphers it considers the frequency of the letters. Modern ciphers, if we consider only block ciphers, operates on blocks - 64, 128, or more bit blocks. Let see how you can perform a frequency attack on modern ciphers to infer some data.

Example attack on Databases:

Let assume that a sensor network has deployed in a rural area to observe animals by researchers. When an animal's tag is detected, the nodes stores this information on a database table; here for simplicity only the type of the animal and date and time encrypted in ECB mode;

|  TYPE  | D&Time|
|-----------------
| 0x443  | 0x7FE |
| 0x122  | 0x1E0 |
| 0x443  | 0x651 |
| 0x443  | 0x6AA |
| 0x084  | 0x09C |
| 0x112  | 0xC9F |
| 0x443  | 0x18D |
| 0x112  | 0x76B |

Now, assume that the poachers cannot extract the encryption key from the nodes but they can read the information. What can they learn from this data?

In ECB mode $E_k(x) = E_k(y)$ iff $x=y$ and this can leak information. This mode is used for equality and count queries on encrypted databases, see the CryptDB paper by Popa et.al. An attacker can calualte the frequency of the ciphertext and infer information from them.

By the Kerckhoffs's principle, we assume that they know everything but the key. The poachers also know the region, so they know how frequently a deer or a wolf appears around this sensor node. Assuming that mostly deer than wolf then bears appears in this region.

If we look at the ciphertext frequencies the 0x443 appears most. So they deduce it actually represents a deer. And similarly 0x122 is a bear data.

Long story short result:  Frequency analysis can break deterministic encryption. If you have pre-knowledge on the frequency of the data you can infer information without decryption. So a ninth-century attack of Arab philosopher and mathematician al-Kindi still lives.

The attack Naveed et.al is performed using electronic medical records. Some of the data is also publicly available like the frequency of the illnesses, drug sales, etc. So their experimental result shows that an alarming amount of sensitive information can be recovered

Mitigation: Don't use ECB mode. Then, you cannot have simple equality queries on the encrypted data. The CryptDB designed to execute queries of TPC-C ot measure the capability and performance.

The future may reside using equality under the FHE, however, it may not easily solve all of the problems.

Some further readings on modern frequency analysis;

Inference Attacks on Property-Preserving Encrypted Databases, by Naveed et. al. Applied frequency attack on electronic medical records.
On the Difficulty of Securing Web Applications using CryptDB, by Akın and Sunar, example how to infer the data form Hospital records.
Access pattern disclosure on searchable encryption: ramification, attack
and mitigation by Saiful Islam et. al.


how do you calculate the private exponent in asymmetric key encryption

You compute the modular inverse of $e \pmod {20}$ with the Extended Euclidean Algorithm, but in this simple case with $e=3$ you can guess $d=7$ because $3\times 7 = 21$.


Key derivation design to avoid key leaks

I finally found out what you're asking for:

A specific (working?) related-key attack on AES!

For this answer I changed the notation a bit:

AES-DEC(K,P) got converted to $D_K(P)$
derived_key_X got converted to $DK_X$
seed (which is known) got converted to $S_K$
chosen_seed got converted to $S_C$
temp_key got converted to $K_T$

Now the answer:

AES by itself is immune to related key attacks to a great extent (there are some attacks but I think they require at least four related keys and I'd doubt the relations would be that complex).

So for an attacker to uncover $DK_1=D_K(S_K)$ he'd need to know $K$. There's no other way in doing this.
Now you're asking if knowing $DK_2=D_{D_K(S_C)}(S_K)$ does help. Let's de-construct this. An attacker can choose $S_C$ to be decrypted to $K_T=D_K(S_C)$, in order to learn $K_T$ he'd need to get K which is infeasible for AES. Now as the attacker has no chance to know $K_T$ there's the question left if $DK_2=D_{K_T}(S_K)$ does help him anyhow. He can't deduce $K_T$ from this equation as this would be a known-plaintext attack, which is infeasible on AES. The final question is if there're some strange relationships that may help the attacker in uncovering $K$ and hence $DK_1$.

No, he'd be (maybe) able to brute-force by trying out every possible $S_C$ until $K_T=D_K(S_C)=K$ which is extremely unlikely, as he could as well just brute force the normal key as he has no control over the value of $K_T$.

I hope this answers your question.


What you are using is the so-called Text-Book RSA. For encryption, we always want the correctness requirement and for public-key systems, this is;
$$D(prv,(E(pk,m)) = m$$ where $E$ is the public key encryption with the public key ($pk$) and $D$ is the decryption with the private key ($prv$).
In Text-Book RSA if we let the messages $m\geq n$ then as you noticed the decryption is not giving back the original message instead provides the $m'$ such that $m' = m \pmod n$ $(9 \equiv 152 \pmod{143})$. Therefore the meaningful resolution is restricting the message space into $[0..n-1]$. Then we can have the correctness requirement.
If you want to encrypt messages with Text-Book RSA then you can split your files into a chunk of sizes in bits at most $\lfloor \log_2 n \rfloor$-bit*.  Here one should consider putting information like the $i$-part of $\ell$, etc. This, however, is not the way to encrypt messages and you must never use the text-book RSA.
We prefer a hybrid-cryptosystem in which the public-key is used to key exchange like RSA-KEM or DHKE and a symmetric cryptosystem is used to encrypt the message with the key.
If you still want to use RSA for encryption then use the correct padding to be secure since the text-book RSA is not secure. RSA should be used with PKCS#1 v1.5 padding or with OAEP.

* To find the number of digits in binary representation of given base 10 integer $n$, calculate $\lfloor \log_2 n \rfloor +1$. Using bits, or actually bytes is much fastert than calculating the data as integer and comparing to the integer $n$.


Paillier Homomorphic encryption to calculate the means

The Paillier encryption of an integer $x_i$ is given by $c_i = (1+x_iN)r_i^N \bmod N^2$ for some random $0<r_i<N$.  Given the encryption of $x_1, \dots, x_k$, the encrypted mean is defined as $$[\![\mu]\!] = \left(\prod_{i=1}^k c_i\right)^{k^{-1}\bmod N} r^N\bmod N^2$$
for some random $0<r<N$.

If we now apply Paillier decryption procedure to $[\![\mu]\!]$, we get $$\mu = \frac{\sum_{i=1}^k x_i}{k} \bmod N$$
We assume $\sum_{i=1}^k x_i< \sqrt{N}$. Now an application of Lagrange-Gauss lattice-reduction algorithm yields $\mu$ as an element in $\mathbb{Q}$.

Based on: [FSW02] Pierre-Alain Fouque, Jacques Stern, and Jan-Geert Wackers. Cryptocomputing with rationals. In Financial
Cryptography, volume 2357 of Lecture Notes in Computer Science, pages 136–146. Springer, 2002.

Alternatively, instead of using Lagrange-Gauss algorithm, we can adapt the extended Euclidean algorithm:

 [u1, u2] = [0, N]; [v1, v2] = [1, mu];
 while (u2 > sqrt(N)) do
   Q = u2 div v2; [t1, t2] = [u1, u2] - [v1, v2]*Q;
   [u1, u2] = [v1, v2]; [v1, v2] = [t1, t2];
 endwhile

 return u2/u1

Here is a toy example with $p = 739$, $q = 839$, and $N = pq = 620021$. Suppose $x_1 = 97$, $x_2 = 74$ and  $x_3 = 46$.

We are given their respective encryptions: $c_1 = 206197787317$, $c_2 = 267770082390$, and $c_3 = 49804921902$. We have $k=3$ and $k^{-1} \bmod N = 206674$. We choose a random $r<N$, say $r = 559196$ and compute $$[\![ \mu]\!] = (c_1c_2c_3)^{k^{-1}\bmod N} \, r^N \bmod N^2 = 127639014845$$

The decryption of $[\![\mu]\!]$ yields $\mu = 206746 \pmod N$.  Lagrange-Gauss algorithm then yields $206746 \equiv \frac{217}3 \pmod N$ and thus $\mu = 217/3 = 72.33$.


How do we know a cryptographic primitive won't suddenly fail?

We don't.${}{}{}{}{}{}{}{}{}{}$

Moderator note: This answer exists for historical significance, but it does not meet the guidelines for answering questions, so please do not use it as evidence that you can post similar answers here. This answer and its comments are frozen and cannot be changed. More info: meta.


Generate the token as a random number. Have each of the parties sign the token independently. Each will provide one signature on the token. Concatenate all the signatures into a big string. That string can then be sent when resources are requested. Each party can verify that its own signature exists in the string.


Is finding collisions in a part-hash not often enough a bad problem?

There are different birthday bounds when we draw independent uniform random integers less then $d$  (for some large $d$, including $d=2^{32}$ of the question) and watch for collision(s):

In crypto, we often consider the bound of $\sqrt d$  ($65536$ for $d=2^{32}$) draws, at which there is a fair probability of collision: $p\approx1-1/\sqrt e\approx39.3\%$. This is also about the number of draws for which it is most likely that the first collision will occur.
The number of draws starting at which it becomes probable ($p\ge1/2$) that there is at least a collision; that is about $\sqrt{\log4}\sqrt d$  ($\approx1.17741\sqrt d$ , $\approx77163$ for $d=2^{32}$); more precise formulas are here.
The average (equivalently: expected) number of draws at which the first collision appears; that is about $\sqrt{\pi/2}\sqrt d$  ($\approx1.25331\sqrt d$ , $\approx82137$ for $d=2^{32}$); more precise formulas are here.

The difference between the three is because mode, median and mean of a discrete probability distribution are not the same thing (sort of: we rarely have a collision much before $77163$, and often have the first collision way after that, hence the significantly larger mean). The confusion is probably what causes the discrepancy in the question.

Image credit: Cmglee; source; Creative Commons license.

If for some would-be hash function we consistently observe collisions much less frequently than predicted by these bounds, for would-be random input (restricted to a domain still much larger than the output domain is), then

our would-be random input (or its domain) is biased
and our hash function is not secure in the random oracle model, in a manner that is related to the bias in our random input.


Why is the El Gamal commitment scheme information theoretically binding?

How is this impossible to be found? Since generators are cyclic, it should be possible to find an $r\neq r'$ that with $g^r = g^{r'}$, or am I overseeing something?

Yes, you're probably thinking the wrong way, possibly like this: there are values $a,b$ with $a\neq b$ and $a^2 = b^2$. But if you look closely, in this case the base is the same and the exponent differs.

The main arguement here is: If the group order is $t$, and we have $r \neq r' \mod t$, then $g^{r} \neq g^{r'}$. Alternatively: set $x = r' - r \mod t$, which is non-zero modulo $t$. Then $g^{r'} = g^{r + x} = g^r \cdot g^x$. This can't be equal to $g^r$ if $x$ is not zero or a multiple of the group order.

With a fixed generator, the first element in the tuple fixes $r$ - even if you don't know what $r$ actually is. And that in return fixes $h^r$. And for a given ElGamal ciphertext this fixes $m$.


When would I need DSA as opposed to RSA for digital signature?

The digital signature algorithm encrypts a hash using the senders private key and the receiver's public key.

Huh?  I see two problems with the above statement;

"Encryption"; using the word encryption implies that there's a way somehow to decrypt it.  However, there's no way to anyone, even with the private key, to "decrypt" a signature to generate the hash.
"using ... the receiver's public key"; the signature operation most certainly does use the signer's private key, but it doesn't use any key (public or private) from the receiver.

  On the other hand the RSA-based digital signature algorithm encrypts the hash using only the senders private key, which is a much cheaper operation.

Not necessarily; if we're talking about the standard DSA operation, the expensive operation is a modular exponentiation of the generator over a (perhaps) 256 bit random exponent modulo the prime; for RSA, the expensive operation (I'm assuming CRT) is two modular exponentiations of arbitrary values modulo primes half in length of the key size.  I believe that you can implement the DSA operation (which, using precomputed tables, would take perhaps 50 multiplications modulo a 2048 bit prime) considerably faster than you can the RSA operation (which might take perhaps 2000+ multiplications modulo 1024 bit primes)

In addition, with DSA, you can potentially perform this computation before you learn the value you're signing; if you can do this in time where you would otherwise be idle, you can make the signing operation very cheap indeed.

And, if we're talking about DSA over Elliptic Curves, that is, ECDSA, the balance tilts even more radically towards ECDSA.

Where RSA shines is the signature verification operation; there's, it's considerably faster than (EC)DSA.

  Under what circumstances would I need to use the expensive DSA as opposed to using the much faster RSA?

Quite apart from your mischaracterization of DSA as expensive and RSA as cheap, actually, straight DSA is fairly rarely used in practice.  ECDSA (and relatives, such as EdDSA) are becoming more popular, in part because it is cheaper...


Does the diffie helman rachet in double ratchet do anything if one side never replies?

Bob will keep sending his public key. Since he only ratchets on receiving messages, his DH Rachet will never activate and there is now no forward secrecy for the N messages he sent?

If there are indeed no answers over the ratcheted channel, this is correct.
However, some implementations send their receive receipts via the ratcheted channel, meaning that the ratchet is only not advanced if the recipient never actually receives the messages or can't send the confirmation.

Also alice will receive the same public key multiple times. Surely this is an issue. Keys should be changing on sending,no?

This is not an issue, the protocol instructs which public key to use, which should be the first new one.


How to rigorously prove that $Enc_{\Pi'(k)}(M) = Enc_{\Pi(k)}(M) || LSB(k)$ is CPA secure assuming $\Pi$ is?

We want to prove that

$\Pi$ is CPA secure $\Rightarrow$ $\Pi'$ is CPA secure.

So, let's prove it using the equivalent contrapositive proposition:

$\Pi'$ isn't CPA secure $\Rightarrow$ $\Pi$ isn't CPA secure.

So, it means we have to suppose that there is an adversary $\mathcal{A'}$ that can win the CPA-game of $\Pi'$ with non negligible probability and then construct some adversary $\mathcal{A}$ to break the CPA security of $\Pi$, in other words,  $\mathcal{A}$ must win the CPA game of $\Pi$. (This is the point you seem to be missing, since you are not interacting with $\Pi$ at all).

So, we construct  $\mathcal{A}$ as follows:

$\mathcal{A}$ receives $m_0$ and $m_1$ from  $\mathcal{A'}$.
$\mathcal{A}$ sends both messages to the encryption oracle of $\Pi$.
$\mathcal{A}$ receives a ciphertext $c_b = Enc_{\Pi(k)}(M)$.
$\mathcal{A}$ chose a random bit $b_k$ and send $c_b||b_k$ to  $\mathcal{A'}$.
$\mathcal{A}$ receives a guess $b'$ from $\mathcal{A'}$.
$\mathcal{A}$ outputs $b'$.

Now, what is the chance that  $\mathcal{A}$ wins CPA game against $\Pi$? It is
$Pr[b' = b]$, that is equal to

(i) $Pr[b' = b | b_k = LSB(K)] \cdot Pr[b_k = LSB(K)]$

plus

(ii) $Pr[b' = b | b_k \not =LSB(K)] \cdot Pr[b_k \not = LSB(K)]$

But $Pr[b' = b | b_k = LSB(K)] \ge \frac{1}{2} + \alpha$ for some non-negligible function $\alpha$ (because $\mathcal{A'}$ can breaks $\Pi$). Therefore, (i) is greater than or equal to $(\frac{1}{2} + \alpha)\frac{1}{2}$.

And if $\mathcal{A}$ didn't guess the least significant bit of $K$ correctly, we don't know how $\mathcal{A'}$ would proceed, so, let's say that $Pr[b' = b | b_k \not =LSB(K)]$ is $ \frac{1}{2} + \beta$ some function $\beta$, then, we have that (ii) is equal to $( \frac{1}{2} + \beta ) \frac{1}{2}$.

Therefore,

(i) + (ii) $\ge  \frac{1}{4} + \frac{\alpha}{2} +  \frac{1}{4} + \frac{\beta}{2} = \frac{1}{2} + \frac{\alpha}{2} +  \frac{\beta}{2}$.

If $\beta$ is negligible, then $\alpha \ge \beta$ and then (i) + (ii) $\ge \frac{1}{2} + \frac{\alpha}{2} +  \frac{\alpha}{2} = \frac{1}{2} + \alpha$.

If  $\beta$ is non-negligible, then take $\gamma$ to be the minimun between  $\alpha$ and $\beta$. That way, we get (i) + (ii) $ \ge  \frac{1}{2} + \frac{\gamma}{2} +  \frac{\gamma}{2} = \frac{1}{2} + \gamma$.

In both cases, $\mathcal{A}$ can guess the bit $b$ output by the oracle to $\Pi$ with non-negligible probability, i.e., $\mathcal{A}$ breaks the CPA security of $\Pi$.


Uniqueness of checksums using DES-MAC encryption?

Think of it this way:

How many possible files are there?
How many possible checksums are there?

If the number of possible files is larger than the number of possible checksums, then there must be at least two files with the same checksum.

This is one of the things known as the "pigeon-hole principle"; the idea is that if you are placing pigeons in pigeon holes, and there are more pigeons than holes, then some hole somewhere will have two pigeons.

Now, if you go on further, you'll find that, if you know the MAC key, it's actually quite easy, with DES-MAC, to produce two files with the same checksum (or, for that matter, a file with a specific checksum).  However, you're not quite ready for that.


In Paillier homomorphic encryption, do we need to take modulo after multiplication of 2 ciphertexts?

Yes, both will give the same result. However, taking mod after each multiplication is far more efficient: if you do not take modulos during intermediate multiplications, the size of the strings you are multiplying keeps increasing, and so does the time it takes to multiply new strings, at a very fast rate (if you multiply $n$ ciphertexts over the integers before taking the mod, you'll blow up their size by about $n$). This would be a huge unnecessary waste of computation, so you'd better take the modulo after each multiplication.


Existence of 99% successful unbounded adversary against randomized secret key encryption scheme with short keys

Eventually, I was able to solve this question.
For anyone wondering, my problem was (mainly) the generalization of the deterministic adversary decision rule to the randomized case.

Originally, the deterministic decision rule was $$A(ct)=\begin{cases}m_0 & ct\in\{E_{sk}(m_0)\mid sk\in\{0,1\}^n\}\\m_1 & otherwise\end{cases}$$
And I generalized it to
$$A(ct)=\begin{cases}m_0 & ct\in\{E_{sk}(m_0;r)\mid sk\in\{0,1\}^n,r\in\{0,1\}^n\}\\m_1 & otherwise\end{cases}$$
But the good generalization would be
$$A(ct)=\begin{cases}m_0 & m_0\in\{D_{sk}(ct)\mid sk\in\{0,1\}^n\}\\m_1 & otherwise\end{cases}$$

Also, this time around you fix $m_1$ and check out random $m_0$'s.
Well, the names do not really matter, but the point is that the decision rule depends on the random message, not the fixed one.


Can I work around these padding issue in AES 256 ECB due to Reed solomon encoding?

You can use ciphertext stealing as the padding mode and the length won't be increased, see: ECB ciphertext stealing .


Minimum number of independent trials needed to detect a bias

I searched the web, and finally (I think) I got:

In page 47, 48 of this thesis, it is mentioned that -

  To detect a bias of $p(1+q)$ (where $p$ is the probability for an Uniform Random event), we need roughly $\dfrac{1}{pq^2}$ samples.


Bob has his private color and mixture from Alice. When he mixes them up he has the same color as Alice when she mixes up mixture from Bob and her private color.

Eve has only two mixtures but no private color, so she can't produce the same color as Alice and Bob.

Eve here can only see colors Alice and Bob exchang but can't change them (Eve is for eavesdropper), if she can change them (intercept mixture from Bob and send her mixture instead) she should be called Mallory (from man in the middle). In this case we have to assume that Alice knows Bob's mixture - he showed it to her earlier in real life or something - and she won't be tricked by fake mixture Mallory sent her.


What happens for factoring algorithms if P=NP?

Proving P=NP would not necessarily give you an algorithm, because there are many different methods to prove something (i.e. Direct proof, Proof by contradiction, etc.).

But it is shown that if you were to find a polynomial time algorithm to solve a NP-complete problem that you could modify that algorithm to solve all NP-problems, including the Integer factorization problem.


Hash or compression function in Merkle tree nodes?

In a Merkle Tree, data is eventually and inevitably lost, because it is compressed away. If a Merkle Tree used a non-padded compression function, the size of the resulting hashes would go down level by level, resulting in a top hash that is very short. The shorter that top hash is, the less it CAN say about the contents of its tree. The longer the resulting hashes in a Merkle Tree are, the more unique the tree is, and the better it expresses its data. In addition, if the results of the compression functions are not standard (i.e. dependent on tree level), than it is very hard from a developer perspective to create software that can work for any and all sizes of Merkle Tree. In short, a non-padded compression function would destroy the "uniqueness" of a tree, and be harder from a developer perspective (keeping the top hash of a long enough size to preserve data)


AES-256-ECB to encrypt VOIP audio-stream?

I would be very scared about using ECB with audio (or anything really).  Note for example that attacks have been demonstrated on variable bitrate compressed encrypted audio:

  Despite the rapid adoption of Voice over IP (VoIP), its security implications are not yet fully understood. Since VoIP calls may traverse untrusted networks, packets should be encrypted to ensure confidentiality. However, we show that when the audio is encoded using variable bit rate codecs, the lengths of encrypted VoIP packets can be used to identify the phrases spoken within a call. Our results indicate that a passive observer can identify phrases from a standard speech corpus within encrypted calls with an average accuracy of 50%, and with accuracy greater than 90% for some phrases. Clearly, such an attack calls into question the efficacy of current VoIP encryption standards. In addition, we examine the impact of various features of the underlying audio on our performance and discuss methods for mitigation.

So right off the bat I have to worry that techniques similar to that paper could perhaps be adapted to ECB.  Note for example (section 2):

  Generally speaking, the codec takes as input the audio stream from the user, which is typically sampled at either 8000 or 16000 samples per second (Hz). At some fixed interval, the codec takes the $n$ most recent samples from the input, and compresses them into a packet for efficient transmission across the network.

So even if we used constant length packets, if each one is compressed separately in ECB mode, I would worry that it might interact poorly with the packetization described in this quote—would somebody with a good speech model and knowledge of the codec be able to use ECB ciphertext block frequencies to decode the speech?  Speech has a lot of phonemic, phonotactic and metrical redundancy and apparent limits on its information rate, after all, enough that compressed packet lengths are enough to recover 50-90% of the phonemic segmental stream.

One simple question that could serve as a starting point is this: could a cryptanalyst reliably identify which ECB blocks encode silence, or is the audio's noise floor high enough to defeat this?

In any case, I wouldn't go my own way on this topic—there seems to be a body of research on VoIP encryption, so I'd track that down and read it.


The use of RIPEMD-160 is not a cause for concern. It's the relatively small number of PBKDF2 iterations which is problematic. More than a decade ago, the minimum recommended number of iterations was 10,000. Nowadays, you should probably not be using less than 100,000, regardless of the hash function in use. However, even that is not ideal. If possible, you should be using a memory-hard KDF like Argon2. That limits the parallelism that an attacker can use against you with any given amount of resources.

Also, TrueCrypt used only 2000 iterations, not 3000, of RIPEMD-160 and 1000 for any other hash.


Here is a partial result:

Assume that we have a way, given $x^e \bmod N$, to derive the parity of $x_S$.  We further assume that $2 > N / 2^k > 1.5$ for some integer $k$, that is, the two msbits of $N$ is set (if the second msbit is clear, then a similar procedure will work, using the second msbit of $x$).

Then, to get a bit with a correlation to the msbit of $x$, we first derive the parity $x_S$.  Then, we compute $x^e \cdot 2^e = (2x)^e$, and then the parity of $2x_S$.

We then guess that the msbit is a 0 if $x_S = 2x_S$, and 1 if they differ.

Now, if the value $2x < N$, that is, if the doubling does not cause an overflow, then the parity $x_S$ will be the same as the parity of $2x_S$; if $2x > N$, then the doubling is really the computation $2x - N$, and the parity of that value will be uncorrelated with the parity of $x$.

Now, if the msbit of $x$ is a 0, that is, if $x < 2^k$, then the doubling will cause an overflow with probability $1 - N / 2^{k+1} < 0.25$, and hence our procedure will guess '0' over 75% of the time.  If the msbit is a 1, the doubling will always cause an overflow, and so our procedure will guess '1' 50 % of the time.

This gives a way to get the msbit in a probabilistic manner; the cited results show how that can be used to derive everything.

Note that this result is weaker than the original; we assumed that we have a error-free way of determining the parity of $x$; however the original result covered weakly probabilistic methods.  It might sound like this could easily be adapted to cover weakly probabilistic methods as well, however it is possible that the errors in determining the parities of $x_S$ and $2x_S$ might be correlated (which would invalidate this argument unless the errors were constrained to be fairly small)


There is no cryptographic way to attest to the deletion of a key. Cryptography deals with mathematical properties of information. If someone knows the key, they have the key and that's that.
To have assurance that some information has been deleted, you need to use non-cryptographic means. The root of trust, i.e. the system that can provide the assurance you're looking for, needs to have several aspects:

You need assurance that the root of trust is protected, so that what happens inside the root of trust stays inside the root of trust. This can rely partially on cryptographic means, for example if the root of trust stores data outside the protection zone in encrypted form, but there has to be a non-cryptographic means of protecting the data encryption key. The assurance comes from the manufacturing process of the root of trust.
You need assurance from the root of trust that the information you're interested in was never shared with untrusted parties.
You need assurance from the root of trust that it deleted all of its copies of the information you're interested in.

In the real world, the root of trust typically consists of multiple parts:

The secure enclave hardware and firmware.
The manufacturing, provisioning and delivery processes of the secure enclave.
The software, running inside the enclave, that generates and later deletes $S$.

From the secure enclave manufacturer, you get a promise that the secure enclave preserves the integrity of the applications that it executes, and the integrity and confidentiality
of the data manipulated by the applications. Furthermore, the secure enclave contains a signature key which it uses to sign attestations, and you get the corresponding public key. An attestation is a promise about the state of the enclave, for example “Version 1.3 of ACMESecureKeyApp is installed”.
From the software manufacturer, you get a promise that the software doesn't share $S$ with anyone, and eventually deletes all copies of it. This promise is often delivered from an attestation coming from the software running in the enclave: the enclave sends a message “ACMESecureKeyApp 1.3 said ‘…’, signed, your secure enclave”, and ‘…’ is ‘I deleted $S$ securely’. You trust ‘I deleted $S$ securely’ because you trust the manufacturer of the software, and you trust “ACMESecureKeyApp 1.3 said ‘…’” because you trust the manufacturing and the chain of custody of the secure enclave.


Hashing into a supersingular elliptic curve

Elligator works just fine for any (including supersingular) elliptic curve with a point of order $2$, with the sole exception of $j=1728$. The latter special case can also be done; see Section 4.2 here.

(The requirement that the curve has a point of order $2$ is trivially fulfilled for supersingular $E/\mathbb F_p$ where $p>3$ is prime, since this implies $\#E(\mathbb F_p)=p+1$ which is always even.)


Convert numeric message from RSA ciphertext to alphabetic

The term you are looking for is Modular Arithmetic.

In the case of 1535, if it is indeed a combination of 3 values ranging 0 to 25, you do the following:

1535 mod 26 = 1
(1535 - 1) / 26 = 59
59 mod 26 = 7
(59 - 7) / 26 = 2

The set of values that generated 1535 is 2,7,1 (c,h,b?), which can easily be verified.


A PRF is indistinguishable from a function sampled at random from the set of all functions with the same domain and range. But that does not means that you need to pick a function at random across all possible functions to get a PRF. That can clearly not work: a random function has, with very high probability, a circuit of exponential size. So you cannot sample such a function in polynomial time, yet alone actually evaluate it on an input.

Sampling a PRF will be done by sampling it from a much smaller set, that contains only functions with a bounded polynomial size. Think of a PRF as a family of functions $\{f_k\}_{k \in \{0,1\}^\lambda}$, and sampling a function from this set is done by simply sampling its index $k$ - i.e., the key of your PRF. Note that even though they are easy to sample, there are $2^\lambda$ such $f_k$, so it is not implausible that an adversary that runs in polynomial time cannot distinguish a sample from this "small" (but still exponential-size) family, from a sample from the set of all functions. Note also that the adversary does not get the functions themselves when he tries to distinguish the set they have been sampled from - rather, he gets black-box access to the input-output behavior of the function.

Then, once you sample a single PRF key, you can use the same function for arbitrary polynomially many evaluations, since the function remains indistinguishable from a random function for the adversary, even if he gets to see an arbitrary polynomial number of evaluations of the function.


Given a sequence of integers, would applying AES encryption to the sequence produce a unique set of strings?

Since any cipher must be able to decrypt every message that it encrypts, it follows that, given a fixed key, any cipher must be an injective function:

  In mathematics, an injective function or injection or one-to-one function is a function that preserves distinctness: it never maps distinct elements of its domain to the same element of its codomain. In other words, every element of the function's codomain is the image of at most one element of its domain.

Or graphically, think of X as plaintexts and Y as ciphertexts:

Although often ciphers are more than just injective—they're also bijective:

And permutations as well: X and Y are normally the same set.  E.g., for AES, X and Y are the sets of 128-bit strings.


Password hashes need first pre-image resistance and should not cause many collisions among typical passwords (preserve the entropy). This collision "attack" violates neither requirement and causes no practical security issues.

While this issue can find trivial collisions, they're not between commonly chosen passwords. A SHA-1 hash (and thus the shorter of the colliding passwords) has 160 bits, the longer has at least 65 characters. There is no way two users will end up with such a colliding pair by accident.

Doing it deliberately doesn't cause any problems either. It only means that the legitimate user knows two valid passwords for their own account.

I'm sure that cryptographers have known about this issue for years, but didn't care since it's no real attack if PBKDF2 is used as intended. I mainly posted it for fun and because I'd prefer new password hashes coming out of the PHC competition to be collision resistant. Programmers expect these function to be collision resistant, so they might use it in an unusual way that, unlike normal password hashing, relies on collision resistance.

It's also fun to surprise the "MD5 is bad as a password hash because collisions" crowd a bit since it's just as easy to find collisions in the "proper choice". (MD5 is bad because it's fast. Its known cryptographic weaknesses don't apply to password hashing.)

We had a discussion about this on the password hashing competition mailing list, where I posted this:

  This results from PBKDF2 using the password as HMAC key instead of message.

  HMAC seems to be designed with a fixed length uniformly random key
  (i.e. it aims to be a PRF),
  so I consider using the password as key instead of message abuse.

  HMAC is a bit weird with variable size keys:

  If the key is shorter than the block size, pad it with zero bytes
  If the key is longer than the block size, hash it

  This is generally not a problem for the usual thread model of HMAC
  (assumes uniformly random keys with fixed size) and PBKDF2 (password
  hashing, only first pre-images matter). But it means that there are
  trivial collisions and even second pre-images (add a 0 byte at the
  end, if the original key was shorter than the block size, this won't
  have any effect).

  As an example with nice printable characters in both passwords:

  plnlrtfpijpuhqylxbgqiiyipieyxvfsavzgxbbcfusqkozwpngsyejqlmjsytrmd
  and eBkXQTfuBqp'cTcar&g* have the same PBKDF2-HMAC-SHA1 hash (no
  matter the salt or the number of iterations).

  I found those with a CPU and unoptimized code. One of our GPU hashing
  friends could easily find a similar pair for PBKDF2-HMAC-SHA-256.


How does generating random numbers "remove entropy from your system"?

As others have stated, the problem is the entropy pool. The operating system maintains a count of entropy in the pool that it decreases every time random numbers are generated from it and increases when it adds some timing or other information that is assumed to have entropy.

Requesting numbers does not actually remove randomness from the pool in practice, unless it is severely broken. The state will still be unknown and the numbers received cannot be used to derive future numbers.

However, the /dev/random interface on Linux blocks if the count is zero. This means that requesting a lot of random numbers from the OS may starve any programs that use the blocking interface. This is the practical issue with using the command, since especially on server machines that have no input devices the entropy count can be slow to increase.

The usual advice is to use the non-blocking pool in most applications so that they cannot get starved, but not every program out there does that.


This signature scheme doesn't even provide UF-KOA security.

The attack is simple: When you want to forge a signature for a message $m$, given a public key $P$, simply compute $h=H(m), h'=h^{-1}\bmod q$ and $S=h'\cdot P$, with $q$ being the order of the subgroup generated by $G$ (usually the curve order). $S$ is then your forged signature for $m$.

This works as:

We can efficiently compute the order of a curve.
We can efficiently find modular multiplicative inverses.


Statistical closeness implies computational indistinguishability

A probabilistic distinguisher is still a deterministic function of its input and random coins. So a probabilistic distinguisher trying to distinguish $X$ from $Y$ is equivalent to a deterministic distinguisher trying to distinguish $(X,R)$ from $(Y,R)$ where $R$ is a uniform distribution over random coins (importantly: independent of $X$/$Y$).

But:

\begin{align}
  \Delta\Bigl( (X,R), (Y,R) \Bigr) &= \frac12 \sum_{\alpha,r} \Bigl| \Pr[(X,R)=(\alpha,r)] - \Pr[(Y,R)=(\alpha,r)]\Bigr|
\\
   &= \frac12 \sum_{\alpha,r} \Bigl| \Pr[X=\alpha]\Pr[R=r] - \Pr[Y=\alpha]\Pr[R=r]\Bigr| \\
   &= \frac12 \sum_{\alpha,r} \Bigl| \Pr[X=\alpha] - \Pr[Y=\alpha]\Bigr| \Pr[R=r]
\\
   &= \frac12 \sum_{\alpha} \Bigl| \Pr[X=\alpha] - \Pr[Y=\alpha]\Bigr| \;\underbrace{\sum_r \Pr[R=r]}_{=1} \\
   &= \frac12 \sum_{\alpha} \Bigl| \Pr[X=\alpha] - \Pr[Y=\alpha]\Bigr|  \\
   &= \Delta(X,Y)
\end{align}

In short, having access to some distribution that is independent of $X$/$Y$ doesn't help (or hurt) to distinguish $X$ from $Y$.


What is the largest performed/possible bruteforce attack to date?

The last major effort I know of for cracking keys was the Distributed.net effort.

You can find the project page at http://www.distributed.net/RC5/en. In 2002, they cracked a 64-bit RC5 key using at total of 331,252 computers over 1,757 days. Their maximum throughput was "equivalent to 32,504 800MHz Apple PowerBook G4 laptops or 45,998 2GHz AMD Athlon XP machines or (to use some rc5-56 numbers) nearly a half million Pentium Pro 200s." as it said in their press release.

At the time, they moved on to doing a 72-bit key, which would be 256 times harder.

If we do some Moore-Law-type hand waving, we'd see a $2^7$ (128×) increase in compute power in ten years. That means that if you started today, it would only be twice as hard as breaking 64-bits was a decade ago. Doable, but not many people would actually want to bother.

Even if you're a government, buying a zero-day exploit and tailoring your own malware would be cheaper.


Point addition equation in projective co ordinates

Your second equation seems a bit off. In the curve of equation:
$$ y^2 + cy = x^3 + ax + b $$
in a binary field $\mathbb{F}_{2^m}$, to add point $P_1 = (x_1,y_1)$ to point $P_2 = (x_2,y_2)$, resulting in point $P_3 = (x_3,y_3)$, then the two equations are:
\begin{eqnarray*}
x_3 &=& \lambda^2 + x_1 + x_2\\
y_3 &=& \lambda (x_1+x_3) + y_1 + c
\end{eqnarray*}
where
$$ \lambda = \frac{y_1+y_2}{x_1+x_2} $$

In projective coordinates, the point $(x,y)$ is represented by the triplet $(X,Y,Z)$ such that $x = X/Z$ and $y = Y/Z$. It is important to realize that the projective coordinates are not unique; $(X,Y,Z)$ and $(\mu X, \mu Y, \mu Z)$ represent the same point, for any non-zero $\mu$. If we have projective coordinates for $P_1$ and $P_2$, then we get:
\begin{eqnarray*}
\lambda &=& \frac{\frac{Y_1}{Z_1}+\frac{Y_2}{Z_2}}{\frac{X_1}{Z_1}+\frac{X_2}{Z_2}} \\
        &=& \frac{\frac{Y_1 Z_2 + Y_2 Z_1}{Z_1 Z_2}}{\frac{X_1 Z_2 + X_2 Z_1}{Z_1 Z_2}} \\
        &=& \frac{Y_1 Z_2 + Y_2 Z_1}{X_1 Z_2 + X_2 Z_1}
\end{eqnarray*}
Then:
\begin{eqnarray*}
\frac{X_3}{Z_3} &=& \frac{(Y_1 Z_2 + Y_2 Z_1)^2}{(X_1 Z_2 + X_2 Z_1)^2} + \frac{X_1}{Z_1} + \frac{X_2}{Z_2} \\
\frac{Y_3}{Z_3} &=& \frac{Y_1 Z_2 + Y_2 Z_1}{X_1 Z_2 + X_2 Z_1} \cdot \left(\frac{X_1}{Z_1} + \frac{(Y_1 Z_2 + Y_2 Z_1)^2}{(X_1 Z_2 + X_2 Z_1)^2} + \frac{X_1}{Z_1} + \frac{X_2}{Z_2}\right) + \frac{Y_1}{Z_1} + c
\end{eqnarray*}

The goal is to compute without making divisions; thus, we need to define $Z_3$ such that all these inconvenient fractions disappear. One possible solution, given the equations above, is to set:
$$ Z_3 = Z_1 Z_2 (X_1 Z_2 + X_2 Z_1)^3 $$
from which we deduce:
\begin{eqnarray*}
X_3 &=& (X_1 Z_2 + X_2 Z_1)(Z_1 Z_2 (Y_1 Z_2 + Y_2 Z_1)^2 + (X_1 Z_2 + X_2 Z_1)^2(X_1 Z_2 + X_2 Z_1)) \\
    &=& Z_1 Z_2 (X_1 Z_2 + X_2 Z_1) (Y_1 Z_2 + Y_2 Z_1)^2 + (X_1 Z_2 + X_2 Z_1)^4
\end{eqnarray*}
and some even more complex -- but without any division -- expression for $Y_3$ (that I am too lazy to compute).

So you get the two main points:

yes, to get projective coordinates, you "just" replace $x$ with $X/Z$ and so on;
but ultimately you still get some choice in the expression for $Z_3$, since projective coordinates are not unique. You thus choose an expression which minimizes overall computational cost, which usually means "the simplest expression which avoids divisions".

Since you have a choice in $Z_3$, you do not necessarily end up with the same formulas as other people, and it is not necessarily mean that your formulas are wrong.