Perfect Steganography History contain many example of old steganography. We also have digital steganography.

Is there any kind of “Perfect Steganography”, in a sense that only the designer can extract the concealed message?

Update
Is there a (formal?) definition of 'perfect steganographic hiding' where only the key-holder / designer can provably recover the data and if so are there any known constructions satisfying it?

"Perfect Steganography" is not well defined. Whatever that is, it must obey Kerckhoff's principle: adversaries know all about the system, except non-public keys. That's enough to exclude many steganography systems in actual use.

I'll use the following largely standard terminology:

Payload is digital data one wants to transmit covertly; that's the question's "concealed message". Only its size is constrained.
Carrier is the data in which a payload might be concealed.
Channel is the vehicle by which said carrier is transmitted, and imposes a set of constraints on the carrier (like: being a bytestring of at most such size conforming to JPEG syntax, though perhaps with stricter constraints on padding and comment fields)
Original (if any) is data from which the carrier is prepared, with a set of constraints of its own (like, being the output of a consumer digital camera) and prescribed relation with the carrier (typically, a rendition of the carrier for human perception must be perceived as one for the original; or at least as a reduced-quality version of the original).

A steganography system must allow a sender holding a key (perhaps, public) and possibly a payload to construct a carrier; and a receiver with a key (same symmetric key, or private key matching public key) to determine if there was a payload in that carrier, and in the affirmative recover the payload.

An adversary's goal is to distinguish if a carrier carries a payload or not (better than random). The receiver must be extra careful not to leak that info, and that's hard, especially against active adversaries. We can assume that the adversary has the choice of payload within size constraints, much like modern cryptography assumes chosen plaintext.
Note: the question's goal "extract the concealed message" could mean that an adversary tries to reduce the size of the carrier while keeping the possibility to recover the payload when latter given the key, but that is not a usual goal, and I won't consider it further.

Payload confidentiality follows from security under chosen payload (argument: if the payload was intelligible, comparison with chosen payload would yield a distinguisher). It would anyway be trivial to add payload encryption on top of steganography if chosen payload was not assumed.

Often, extra properties are required:

The original must be a valid carrier per the channel constraints.
The security goal is met even if the adversary get holds of the original from which the carrier was prepared.
When there's no payload in a carrier, the carrier must exactly match the original.
The process by which an original is transformed into a carrier when no payload is embedded is constrained (e.g. is a certain pre-existing program).

Property 3 implies 1, and is incompatible with 2. There is overlap between channel constraints and constraints in 4.

Note: I've left aside watermarking, even though there is overlap with steganography.

The possibility (or not) of making a demonstrably secure steganography system depends heavily on the constraints set: on channel, original, payload size, and extra properties. There are many combinations of constraints depending on use case. Channel and original constraints vary immensely. Payload size can range from the text GO to terabytes.

The simplest demonstrably secure steganography system are those where constraints allow to embed a little more uniformly random bits in a carrier than the payload length (after compression). We can set these bits of the carrier either to true randomness (for no payload), or to the ciphertext of some authenticated encryption of the payload having the property that ciphertext is indistinguishable from random (which is easy and common). The receiver extracts the bits, perform the decryption/integrity check, concludes there's no payload if the integrity check fails, and otherwise has recovered the payload.

Such system must match whatever reasonable definition of perfect steganography is chosen (if a reusable key is not required, we can even use an information-theoretic MAC and replace encryption by a One-Time-Pad, to become information-theoretically secure regardless of the adversary's computing power).

Here is an example with properties 2 and 4, where original is any JPEG file, and channel is a PDF file with a PAdES digital signature made using 4096-bit RSA per RSASSA-PSS with SHA-512. I posit existence of a program that transforms JPEG files into signed PDF with said signature that uses a CSPRNG at step 4 of EMSA-PSS-ENCODE, reading:

  Generate a random octet string salt of length sLen

In the context, sLen is 4096-64-512 = 3520 bits, which can legitimately be random per the channel's constraints and property 4. That is enough for a 64-bit MAC per HMAC-SHA-256, a 64-bit IV for the most significant bits of a counter for AES-256-CTR, and 424 bytes of payload (over 1k byte of compressed text), used instead of the random octet string when there is a payload.

When the channel allows no bit that can be arbitrary random, it becomes much more difficult to make a demonstrably secure steganography system. In particular, with property 3, it becomes critical that the adversary can't have a better model of the original than the system assumes.


Are checksums essentially non-secure versions of cryptographic hashes? Are checksums basically toned-down versions of cryptographic hashes? As in: they are supposed to detect errors that occur naturally/randomly as opposed to being designed to prevent a knowledgeable attacker's meticulous engineering feature?

So, essentially they are non-secure versions of cryptographic hashes, one could say? Thus for the same reason, these checksums are "cheaper" to compute than cryptographic hashes? (e.g. CRC32 vs SHA-256)

Sorry for my poor english and potentially trivial question. I just need to get the concepts straightened out.

Are checksums basically toned-down versions of cryptographic hashes? As in: they are supposed to detect errors that occur naturally/randomly as opposed to being designed to prevent a knowledgeable attacker's meticulous engineering feat?

That is one way to look at it. However, hash functions have many purposes. They are also meant to be one-way (an attacker cannot know the preimage without guessing), for which there is no parallel with checksums.

  So, essentially they are non-secure versions of cryptographic hashes, one could say? Thus for the same reason, these checksums are "cheaper" to compute than cryptographic hashes? (e.g. CRC32 vs SHA-256)

Due to their different requirements, checksums are not just "worse, but faster hashes". They are meant to prevent particular kinds of errors. Cyclic redundancy check can detect e.g. all 1-2 bit errors in short inputs, as well as some other common classes of errors in typical applications (e.g. bursts errors). This is better than a truncated cryptographic hash of similar length would be able to do.

A cryptographic hash truncated to 32 bits can easily collide with two inputs that differ in only one or two bits, whereas a CRC won't. The CRC is geared towards reliably detecting error patterns that commonly occur in transit, so it will do better on those kinds of errors and worse on others. The short hash does optimally over all inputs, and as a result does worse than CRC on the inputs CRC is good at dealing with.


For a random permutation $P$, what's the probability of the following event? For a random permutation $P$ and $q$ distinct inputs $x_1,\ldots,x_q\in\{0,1\}^n$, what's the probability of the event that there exists at least one collision among $\{P(x_1)\oplus x_1,\ldots,P(x_q)\oplus x_q\}$?

Note: I have tried to compute this probability, but it is quite hard for me to obtain the result, either for the exact probability or the lower bound of this probability. The following is my attempt to solve this problem when $q=2,3$.

Denote by $\mathsf{E}$ the event that there exists at least one collision among $\{P(x_1)\oplus x_1,\ldots,P(x_q)\oplus x_q\}$.

If $q=2$, it is easily seen that $\Pr[\mathsf{E}]=\Pr[P(x_1)\oplus x_1=P(x_2)\oplus x_2]=\frac{1}{2^n-1}$

If $q=3$, we have 3 random elements $P(x_1)\oplus x_1,P(x_2)\oplus x_2,P(x_3)\oplus x_3$. We focus on computing $\overline{\mathsf{E}}$ the complementary event of $\mathsf{E}$:
 \begin{align}\Pr[\overline{\mathsf{E}}]=&\Pr[P(x_1)\oplus x_1\neq P(x_2)\oplus x_2 \wedge P(x_1)\oplus x_1 \neq P(x_3)\oplus x_3 \wedge P(x_2)\oplus x_2 \neq P(x_3)\oplus x_3]\\
=&\Pr[P(x_1)\oplus x_1 \neq P(x_3)\oplus x_3 \wedge P(x_2)\oplus x_2 \neq P(x_3)\oplus x_3\mid P(x_1)\oplus x_1\neq P(x_2)\oplus x_2]\cdot\Pr[P(x_1)\oplus x_1\neq P(x_2)\oplus x_2]

\end{align}
Without loss of generality, assume that the value of $P(x_1)$ is fixed. There are $2^n-1$ possibilites for $P(x_2)$. Conditioned on the event $P(x_1)\oplus x_1\neq P(x_2)\oplus x_2$ happening, the probability of the event $P(x_1)\oplus x_1\neq P(x_3)\oplus x_3\wedge P(x_2)\oplus x_2\neq P(x_3)\oplus x_3$ may change according to the choices of $P(x_2)$:

If $P(x_2)=P(x_1)\oplus x_1\oplus x_3$ or $P(x_2)=P(x_1)\oplus x_2\oplus x_3$, then the probability of the event $P(x_1)\oplus x_1\neq P(x_3)\oplus x_3\wedge P(x_2)\oplus x_2\neq P(x_3)\oplus x_3$ is $\frac{2^n-2-1}{2^n-2}$.
If $P(x_2)\neq P(x_1)\oplus x_1\oplus x_3$, $P(x_2)\neq P(x_1)\oplus x_2 \oplus x_3$ and further $P(x_2)\neq P(x_1)\oplus x_1\oplus x_2$, then the probability of the event $P(x_1)\oplus x_1\neq P(x_3)\oplus x_3\wedge P(x_2)\oplus x_2\neq P(x_3)\oplus x_3$ is $\frac{2^n-2-2}{2^n-2}$.

Hence,
\begin{align}
\Pr[\overline{\mathsf{E}}]=&\frac{2}{2^n-1}\cdot\frac{2^n-3}{2^n-2}+\frac{2^n-1-3}{2^n-1}\cdot\frac{2^n-4}{2^n-2}\\
=&\frac{2^{2n}-6\cdot 2^n+10}{(2^n-1)(2^n-2)},
\end{align}
and $\Pr[\mathsf{E}]=1-\Pr[\overline{\mathsf{E}}]=1-\frac{2^{2n}-6\cdot 2^n+10}{(2^n-1)(2^n-2)}$.
For $q\ge4$, the computation is complicated and I haven't found a good method to tackle it.

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

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

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


Where should i start? I am very interested in cryptography and would like to learn more about it and how to code. However, I dont know how to start. I would love to know some more mathematical background and how to apply it. I enjoy creating little codes and such in my free time, but there is a limit to what you can just "think up". I honestly dont know what alot of these things such as 'AES-GCM' or 'md5'. I dont know where to start or where to apply cryptography in my life besides for fun. Any advice would be appreciated! Thanks!

I started with books on amazon, such as Understanding Cryptography: A Textbook for Students and Practitioners and open public documents such as FIPS-PUB-197 and 180. I found everything to be pretty easy along my way up. I still cannot calculate or prove anything mathematically, that you want to dig into mathematical reasoning, but I have no problem implementing any algorithms and mix match them to suit my needs.

-- me, 2017-02-14

EDIT:
2 years later, I'm back with a few college level crypto courses in my bag. I want to add that "implementing any algorithms and mix match them to suit my needs" was a terrible idea I want to steer you all clear from. Why? Because this field, cryptography, is full of vulnerability landmines and trip wires, and implementing your own crypto for any production system is asking for trouble. Correctly implementing crypto is hard even for professional groups of people who are intensely experienced and employs in-depth code review.

The solution is to rely on reputable, low-level crypto libraries. Such as OpenSSL. That being said, don't let this stop you from implementing crypto for fun! The sense of achievement is immense when you do so. Happy learning!

-- me, 2019-05-07


Stateless hash based public key cryptography? Merkle-Winternitz signatures based on fractal hash trees are an attractive alternative to other post-quantum cryptographic schemes, in particular since they are conceptually simple, the security properties are easily understood and they are easy to implement correctly.

However, all schemes based on Merkle trees appear to be stateful, in the sense that the signer must keep track of the number of signatures already generated, and because some optimizations make it significantly impractical to generate several signatures in parallel. This is a huge minus e.g. for server authentication, where the same key might have to be used for several connections in parallel.

Furthermore, stateful private keys are vulnerable to server crashes if the private key state is not immediately persisted (which further increases stalls from serialized signing). Randomized schemes (such as DSA/ECDSA), or schemes based on trap door functions rather than one way functions (such as RSA) do not have these problems.

Does there exist any public key scheme based solely on hash function that does not require a stateful private key?

You can build a gigantic, enormous tree that has capacity for up to $2^{80}$ one-time signatures (say).  Then, each time you want to sign something, you randomly pick a 80-bit value and use that to select which of the $2^{80}$ subtrees to use to sign the message.  As long as the number of messages you intend to sign is much less than $2^{40}$ messages, a collision is unlikely.

It takes some extra work to make this work.  In particular, if your tree used only hash functions, then to precompute the public key, you'd have to do $2^{80}$ work to populate the entire tree -- no good.  So, in fact we do a multi-level tree where the entries at one level are used to sign a subtree the next level down (signed, using Merkle-Winternitz signatures).

For more details on how to make this work, you can see, e.g.,  https://www.imperialviolet.org/2013/07/18/hashsig.html or https://www.cdc.informatik.tu-darmstadt.de/reports/reports/BDKOV07.pdf.

This does increase the size of signatures and the amount of computation needed a bit, but if you want a stateless scheme, it might be viable.


Zero knowledge proof with sum All zero-knowledge protocols I have read so far for discrete log works like this:

1) Prover generate a random number $r$, creates a commitment $t=g^r$ and sends $t$ to the verifier.

2) Verifier generates a random challenge $c$ and sends it to the prover.

3) Prover creates a response $s=r+x*c$ and sends it to the verifier

My question is: is the security affected in any way if, in step 3, the prover responds with $s=r+x+c$?

I don't understand why multiplication $x*c$ is used instead of sum $x+c$.

Hint: what happens if the prover, instead of sending $g^r$ for a random $r$ that he knows in the first round, sends instead $g^{-x}\cdot g^r$ for a random $r$ that he knows?


Parity of an encrypted key Does encrypting a double-length 3DES application key (that has an odd parity) under a double-length 3DES zone master key (also with an odd parity) affect the parity of the application key?

No it does not affect the parity bits.

The plaintext or ciphertext doesn't have any parity bits specified. The application key is just a input to the cipher, which is a Pseudo Random Permutation. Permutation means a 1:1 mapping from plaintext - including parity bits - to the ciphertext. If you perform the permutation in the opposite direction the plaintext - again including the parity bits - will be restored.

The same goes if the master key is used within a specific mode of operation for the block cipher; the 1:1 relationship between plaintext and ciphertext will be maintained.

Note that as the ciphertext doesn't have any parity bits, the parity of the ciphertext is completely random; the parity of the plaintext is not mirrored in the parity of the ciphertext in any way. That also means that if you perform key derivation with the master key that you need to explicitly set the parity afterwards.

Note that some libraries do not actually validate the parity bits. It's better to set them none-the-less.


Is there an efficient 2 out of 3 secret sharing scheme based on XOR? I want to know if there is an efficient secret sharing scheme based on XOR such that a share of the message is given to three people and at least two must combine their share in order to construct the message?

What I have tried so far:

Suppose I got a message $M$, and three people A, B and C. Then what I do is

A gets
$a_1 = M \oplus \alpha$ and $a_2 = \beta$
B gets
$b_1 = M \oplus \beta$ and $b_2 = \alpha$
C gets
$c_1 = \alpha$ and $c_2 = \beta$

Where $\alpha$ and $\beta$ are two randomly generated bits the size of the message.

This works fine (with some modification), but the problem is that each person have to store twice the size of the message. Is there a more efficient one?

Here is a simple (2, 3) secret sharing scheme that used only xor's, and each share is the same size as the secret (assuming that the secret is an even number of bits long)

First, we divide the secret $s$ into two equal sized halves, $s_1, s_2$.

And, we pick two random values of the same size, $r_1, r_2$

Then, the Alice shares are $a_1 = s_1 \oplus r_1$, $a_2 = s_2 \oplus r_2$

The Bob shares are $b_1 = s_1 \oplus r_2$, $b_2 = s_2 \oplus r_1 \oplus r_2$

And the Carol shares are $c_1 = s_1 \oplus r_1 \oplus r_2$, $c_2 = s_2 \oplus r_1$.

It is straight-forward to show that any two parties can recover the secrets $s_1, s_2$

With the Alice and Bob shares, we have $s_1 = a_1 \oplus a_2 \oplus b_2$, $s_2 = a_1 \oplus b_1 \oplus b_2$

With the Alice and Carol shares, we have $s_1 = a_2 \oplus c_1 \oplus c_2$, $s_2 = a_1 \oplus a_2 \oplus c_1$

With the Bob and Carl shares, we have $s_1 = b_1 \oplus b_2 \oplus c_2$, $s_2 = b_1 \oplus c_1 \oplus c_2$

And, with a single share, neither Alice nor Bob nor Carol gain any information about the value of the secret (assuming $r_1, r_2$ was picked randomly).

And, if the total length of the secret is n bits (and so each half of the secret is $\lceil n/2 \rceil$ bits long), the total length of each share is $2 \lceil n/2 \rceil$ bits, which is $n$ bits if $n$ is even.


Will adding space to the Vigenère block make it truly unbreakable? I just have gotten into cryptography and learned about the Vigenère block. I think it's a very good idea because, if used correctly, it is unbreakable. But the only downsite is, the key must be the same length as the message. Well, can't you just simply make the block 27x27 big by adding the space into it. That way you could have no space at all, or you can make spaces where ever you want. Is there anything like this already or am I overlooking something here?

I believe you need a few clarifications to answer this question yourself.

The first is the one time pad (OTP). This is the only truly unbreakable system if it's used correctly.

Using correctly means that for every symbol of the message there is exactly one truly random symbol in the key. Specifically, this means that there is no chosen symbol of the key that is used twice (of course a symbol can occur twice in the key; I mean that for every symbol of the message there is a new symbol chosen for the key with its own randomness). The message includes spaces, so spaces need to be encrypted as well! This is what your thought was when you said to extend the table with a space.

The Vigenère cipher has a repeating key in its original definition. If you choose the key to be exactly as long as the message (and encrypting every symbol of the message, not just the letters) and you chose this key randomly, then the Vigenère cipher becomes the One Time Pad and is thus, as you correctly said, unbreakable.

If your message has more than 27 symbols (for instance capital letters, punctuation etc.) then your key must be extended, as well.


CP-ABE Key generation random parameters In the key generation algorithm of cp-abe there are attributes: $x_1, x_2,...x_n \in \{0,1\}^*$

$r, r_{x_1}, r_{x_2},...r_{x_n} \xleftarrow{R} Z_p$ are chosen randomly to generate the private key $SK$ where.

$SK = [g^{\left(\alpha+r\right)/\beta},
g^r \cdot H(x_1)^{r_{x_1}}, g^{r_{x_1}}, ...,
g^r \cdot H(x_n)^{r_{x_n}}, g^{r_{x_n}}]$

My question is, are those random $r's$ randomly chosen by the key authority each time a user requests a private key for certain attributes or is it generated once for all users and each user will be given the private key based on their attributes.

To be more clear assume user A claims attributes $x_1, x_2$ while user B claims $x_1, x_3$. They both at different times request a private key containing a component for attribute $x_1$. So is $r_{X_1}$ generated once for each user request or is it the same for both requests? Of course $g^r \cdot H(x_1)^{r_{x_1}}, g^{r_{x_1}}$ will be affected as well if they are different.

You're talking about the KeyGen algorithm of Bethencourt's CP-ABE. The scheme is described in general and this KeyGen algorithm is supposed to be executed for each user secret key request in full which includes choosing new $r_x$ values.
So, your (actual?) concern that different users who have the same attributes could collude is unfounded.

However, a key authority can add single attributes to an existing user secret key, but for this it is necessary to know $r$ (by storing it in an internal database) or a trick shown by Denisow et al. in "Dynamic Location Information in Attribute-Based Encryption Schemes".


Symmetric property of DDT of inverse function Given a bijective function $F: \mathbb{F}_2^n \rightarrow \mathbb{F}_2^n$.

The entry of the Difference Distribution Table (DDT) at row $\alpha$ and column $\beta$ is defined as

$$DDT_{F}(\alpha,\beta) = \delta_F(\alpha, \beta) = |\{ x \in \mathbb{F}_2^n | F(x) + F(x+\alpha) = \beta  \}|$$

I need to show that

$$DDT_{F}(\alpha,\beta) = DDT_{F^{-1}}(\beta, \alpha)$$

with

$$DDT_{F^{-1}}(\beta, \alpha) = \delta_{F^{-1}}(\beta, \alpha) = |\{ x \in \mathbb{F}_2^n | F^{-1}(x) + F^{-1}(x+\beta) = \alpha  \}|$$

Unfortunately, I do not know how to start to show the equality, but I assume substitution is the way to go. Can you please give me a hint?

I tried the same approach I used to show that this symmetric property does also hold for the Linear Approximation Table (LAT), i.e.

$$LAT_{F}(\alpha,\beta) = LAT_{F^{-1}}(\beta, \alpha)$$

with

$$LAT_F(\alpha,\beta) = \widehat{F}(\alpha,\beta) = \sum_{x \in \mathbb{F}_2^n} (-1)^{<\alpha,x> + <\beta,F(x)>}$$

$$LAT_{F^{-1}}(\beta,\alpha) = \widehat{F^{-1}}(\beta,\alpha) = \sum_{x \in \mathbb{F}_2^n} (-1)^{<\beta,x> + <\alpha,F^{-1}(x)>}$$

For the LAT, the trick was to substitute. Since $F$ is a permutation and the sum goes over all elements in $\mathbb{F}_2^n$, substitution only changes the order in which the elements in $\mathbb{F}_2^n$ are processed.

$$x = F(y)$$

This leads to:

$$\widehat{F^{-1}}(\beta,\alpha) = \sum_{x \in \mathbb{F}_2^n} (-1)^{<\beta,x> + <\alpha,F^{-1}(x)>} = \sum_{y \in \mathbb{F}_2^n} (-1)^{<\beta,F(y)> + <\alpha,y>} = \widehat{F}(\alpha,\beta)$$

Unfortunately, substituting $x = F(y)$ did not solve my issue with the DDT.

The proof for DDT is shown as following:

given:
$$y=F(x) ;\\ x=F^{-1}(y) \> \> (1) $$
The forward DDT is
$$F(x) + F(x+\alpha) = \beta \>\> (2)$$
substituting (1) into (2)
$$F(x) + F(F^{-1}(y)+\alpha) = \beta  $$

$$y+ \beta +F(F^{-1}(y)+\alpha) =0$$

re-arranging and applying inverse function
$$F^{-1}(y+ \beta) +F^{-1}((F(F^{-1}(y)+\alpha))=0 $$

$$F^{-1}(y+ \beta) +F^{-1}(y) = \alpha$$

Therefore ,

$$DDT_{F^{-1}}(\beta, \alpha) = \delta_{F^{-1}}(\beta, \alpha) = |\{ x \in \mathbb{F}_2^n | F^{-1}(x) + F^{-1}(x+\beta) = \alpha  \}|$$

The same concept applied to LAT proof.


SHA-256 Hash identical on two similar but not exact items There are two discs that we have that have all the same files. However, using a new method for burning the discs, the second disc had modified file dates of 5/30/2018 while the original disc has dates of 2013.

The hash value of each CD is identical.

I tried to recreate this by making a Microsoft Word document that had the word 'blue' in size 12 Times New Roman. First I had my name as the author and hashed the file. I added an other through Windows Explorer in the details tab of the properties menu. The hash value of each file, though stored in the same folder with the same content differed between the two files.

Is there an easy explanation for what two cds with files having different modification dates be identical?

Thanks in advance.

The hash value of each file, though stored in the same folder with the
  same content differed between the two files.

That is because MS Word encodes things like who last changed the file in its actual file instead of just in the filesystem metadata. Thus this change indeed affects the hash.

  Is there an easy explanation for what two cds with files having
  different modification dates be identical?

CodesInChaos provided the answer in the comments:

  Change dates are part of the filesystem metadata and not of the file
  content itself, and thus don't get considered when hashing the file
  content.


Differential privacy basics: Universe \mathcal{X} and database $x$ The "Algorithmic Foundations of Differential Privacy" book (DOI: 10.1561/0400000042) introduces formally the "universe" and "database" on page 17 roughly as:

$\mathcal{X}$ is a universe
databases $x$ are collections of records from the universe
For convenience, we use histogram of types from the universe $\mathcal{X}$ to represent $x$, such that: $x \in \mathbb{N}^{|\mathcal{X}|}$ where each entry $x_i$ represents the number of elements in the database $x$ of type $i \in \mathcal{X}$

If you take the example from Wikipedia

The universe $\mathcal{X}$ is a set $\{0, 1\}$?
The database $x$ is

a vector [3, 3] (assuming the universe is ordered)?
or a map {0:3, 1:3}?

My two questions are:

Is my understanding correct?
Why is it "convenient" to do so? What would be the non-convenient alternatives?

I am a little late. Your understanding seems correct. $\mathcal{X}=Names \times \{0,1\}$ Where $Names$ are all the possible names that could exist and $x \in \mathbb{N}^{2}$ (Because of $|\mathcal{X}|=2$).
Then you can choose one column and select the histogram of the type you want. Then you can express $x=(x_0,x_1)=(3,3)$ or $x=(x_{ross},...,x_{Rachel})=(1,..,1)$. A you see the first one is more convenient.


How much entropy is lost via hashing when you add known or low entropy data? (I updated the title, as I think there was some confusion as to the question)

Here's the question:

For example, if I have a bit stream that is 64K bytes long and there is about 16 *8 bits worth of entropy randomly dispersed in that byte stream, so I have 16*8 bits worth of entropy.

However, if I SHA256 that byte stream, I will now only have 32 bytes total rather than 64K bytes.

Some information has been lost of course, but perhaps all of the entropy is retained?

Another way of looking at the question, is the entropy of SHA256(10GB with 16 bytes of entropy) equal to SHA256(16 bytes with 16 bytes of entropy) and if not, how much exactly has been lost?

I'm having a hard time finding any literature which estimates entropy loss, just a lot of hand waving by various crypto engineers that it's all good.

Here's an algorithmic way of looking at it:

#!/bin/sh
HASHV=`echo <random secret> | sha256`
echo $HASHV
while(true) ;
do
HASHV=`echo "$HASHV 00000000000000000000000000000000" | sha256`
echo $HASHV
done

Will the entropy of HASHV decrease over time?

Anyone got anything specific? (refs to papers, books, etc are grand)

Relevant questions:

What happens to the entropy of a password when you hash it?
Entropy of system data - use all and hash, or trim least significant bits?

A simple way to imagine the effect of the hash function is a truncation. A "good" hash function ought to behave like a random oracle. If your source has entropy $s$ bits, then this means that the source somehow assumes $2^s$ possible values. When processed with a random oracle with an $n$-bit output, you force the $2^s$ input values into $2^n$ possible outputs.

When $s$ is smaller than $n/2$, then it is expected that the hash function will produce $2^s$ distinct values, and all your $s$ bits of entropy are preserved. When $s$ reaches $n/2$, collisions begin to appear, and each collision means a tiny fraction lost entropy. You still preserve most of it, though. When $s$ reaches $n$ (e.g. you hash an input with 256 bits of entropy, with SHA-256), then it is expected that you get about $0.6·2^s$ distinct output (you lost one third of the inputs to collisions), so the resulting entropy will be a bit more than $n - 1$ bits. When $s$ is higher than $n$, the output entropy will still rise, but never exceed $2^n$: you cannot have more than $2^n$ distinct outputs of $n$ bits...

To sum up, when hashing your input, you preserve almost all your input entropy, up to at most the output size of the hash function. To make things simple: when you hash with SHA-256 an input of entropy $s$ bits, then you get an output entropy at least equal to the lower of $s-1$ and 255 bits.


SEAL Homomorphic multiplication In SEAL homomorphic encryption library, there is an internal procedure to decompose a polynomial with large coefficients into a vector of polynomials with smaller coefficients. The procedure is described in pages 3-4 here. I wonder if someone can paraphrase the procedure and provide a simple example to show how polynomial multiplication can be done via that procedure and why it is better than school-book polynomial multiplication followed by modular reduction.

Let $n = 4$, $q = 199$, $w = 16$. This means that $\ell_{w,q}=2$, $\mathbb{Z}_q = \{-99,...,99\}$, and $\mathbb{Z}_w = \{-8,...,7\}$.

Let $a = 70X^2 + 56X+45$ and $b = 61X+31$.

Please show $Dec_{w,q}(a)$ and $Pow_{w,q}(b)$ and how the dot product is equivalent to polynomial multiplication as follows: $\langle Dec_{w,q}(a),Pow_{w,q}(b) \rangle = a.b \pmod q$.

In this answer, I am reducing using that centered representation of $\mathbb{Z}_q$ and $\mathbb{Z}_w$. Also, I am writing $\ell$ instead of $l_{w,q}$ to simplify the notation.

Concrete examples:

$Dec_{w,q}(a) = (6x^2 - 8x - 3, 4x^2 + 4x + 3)$
$Pow_{w,q} = (61x + 31, 61\cdot16x + 31\cdot16) = (61x + 31, -19 x + 98) \pmod q $

Therefore, we have the following dot product:

$$\begin{align}
Dec_{w,q}(a)\cdot Pow_{w,q}(b) &= (6x^2 - 8x - 3) \cdot (61x + 31)+( 4x^2 + 4x + 3) \cdot  (-19 x + 98) \\
                 &= (366 x^3-302 x^2-431 x-93) + (-76x^3+316 x^2+335 x+294)\\
                 &= 290 x^3+14 x^2-96 x+201 \\
                 &= 91x^3 + 14x^2  -96x + 2
\end{align}$$

And the usual product reduced modulo $q$ is:

$a \cdot b = 4270 x^3+5586 x^2+ 4481x+1395 = 91x^3 + 14x^2 + -96x + 2$

Explanation:

In order to have a simple understanding, think of the integers (or, polynomials with degree equal to zero): in this case, it is easy to see that given an integer $a$, we can write $a$ in base $w$ obtaining digits $a_\ell, ..., a_1, a_0$ such that

$$a = \sum_{i=0}^\ell a_i \cdot w^i$$

In particular, if $w = 2$, then this is the binary representation.

The key point now is to understand why it is still valid if $a$ is any polynomial. In fact, it is valid because we just write each coefficient in base $w$, obtaining $\ell$ digits for each coefficient and then we define $\ell$ polynomials, with each polynomial $a_i$ having the $i$-th digits of each coefficient...

For instance, let $p(x) = 3x^3 + 2x + 1$, $q = 199$ and $w = 2$, then, write each coefficient in base $w$, obtaining $3 = (1,1)_w$, $2 = (0,1)_w$, and $1 = (1, 0)_w$, thus, we got
$$Dec_{w,q}(p) = (\underbrace{1x^3 + 0x + 1}_{\text{First digits}}, \underbrace{1x^3 + 1x + 0}_{\text{Second digits}})$$

So, once we have accepted that the summation above holds for any polynomial $a$, i.e., we can decompose any polynomial writing its coefficients in base $w$, then, understanding why the dot product is equal to the usual product is straightforward.

The function $Pow_{w,q}(b)$ just put the exponents of the decomposition of  the summation above in a vector with the polynomial $b$: $Pow_{w,q}(b) = (b\cdot w^0, b\cdot w^1, ..., b\cdot w^\ell)$.

Therefore, we have

$$
\begin{align}
Dec_{w,q}(a) \cdot Pow_{w,q}(b) &= (a_0, ..., a_\ell) (b\cdot w^0, ..., b\cdot w^\ell) & \\
 &= \sum_{i=0}^\ell a_i b w^i & (\text{By defn. of dot product}) \\
 &= b \sum_{i=0}^\ell a_i  w^i & (\text{Since } b \text{ doesn't depend on } i)\\
&= b a  & (\text{With the above equality})
\end{align}
$$

About your other issue:

  why it is better than school-book polynomial multiplication followed
  by modular reduction.

I think you have miss understood SEAL's manual... Those two functions are used in the relinearization step (called KeySwitch on the original paper), and they are not used to increase the efficiency of the multiplication, they are used to guarantee the correctness of the decryption under the original private key (and also to manage the noise growth). I suggest that you read section 5 of the original YASHE paper.


Why is proving "parties' views are simulatable" enough in semi-honest model? To prove a protocol is secure in semi-honest model, we have to prove: the view of each party, on each possible pair of inputs, can be efficiently simulated based solely on its own input and and output.

So let's consider this example, Alice holds $x$ and Bob holds $y$, they wants to compute $f(x, y)$ without revealing their inputs. I constructs a protocol which is insecure: Bob simply sends $y$ to Alice, and Alice outputs $f(x,y)$.

But it seems it can be proved according to the definition of semi-honext model. Let's assume Bob is honest, we construct a simulator for Alice. The simulator feeds Bob with a random $y'$, Alice cannot distinguish $y$ and $y'$. So Alice's view can be simulatable. But the protocol is of course not secure.

I am having a hard time understanding your argument why you think this could be simulated. However, here is an explanation of why it could not.

Assume Bob is honest and has input $y$, now we have to simulate the view of Alice. As the simulator, as you state, we only get the input and output of Alice. I.e, we only know $x$ and $f(x,y)$. We only need to simulate the one message in Alices view, i.e., the first message where Bob sends $y$ to Alice. Since we do not know $y$ the best we can do is to randomly guess at some $y'$. Now the probability that $y' \neq y$ is going to be high, so the simulation is going to be clearly distinguishable from the view of Alice.

What might be confusing you is that, when we do the simulation we do not know the inputs of the honest parties. But when we try to distinguish the real view from the simulation we know all the inputs.


Understanding LFSR stream ciphers and the content scrambling system I'm a little confused over how exactly Linear Feedback Shift Registers (LFSR) work, I kind of get it, but not really, can someone help me understand it? I know it XORs bits in a loop against some mask, how is the shuffling defined?

A content scrambling system is a synchronous stream cipher made from 2 LFSRs of different lengths, one with 17 bits and the other with 25 bits. If a 40 bit key is loaded into the LFSRs, 2 bytes into the first LFSR and 3 bytes into the second remaining bits in all set to 1. The outputs are combined to produce the keystream.

How would I go about finding the max period of each LFSR? Is it as simple as $2^d-1$ (simple ($2^{17})-1=131071$ and ($2^{25})-1=33554431$) or is it a little more complex?

Why does the content scrambling system use different LFSR lengths, why must it be 17 and 25 and not something different?

How would I go about brute forcing it, and what would the complexity of the brute force attack be?

If i simply XOR the two LFSR outputs, what would be the result be like (I'm assuming there would be some sort of way to identify information out of it)? Would a known plain text attack prove effective?

How would I go about finding the period of each LFSR?

If the polynomial generating an LFSR is primitive polynomial then the LFSR has maximal period, $2^\ell-1$ where $\ell$ is the length of the LFSR. It is general practice that they are chosen as primitive polynomials. In your case periods are $2^{17}-1$ and $2^{25}-1$ for $L_1$ with length 17 and $L_2$ with length 25, respectively.

In LFSR's there might be a negligible chance that the key is all-zero then the stream will be all-zero. To eliminate an all-zero case, the fourth-bit is injected with 1 for $L_1$ and $L_2$.

  Why does the content scrambling system use different LFSR lengths?

If the LFSR lengths and taps are the same, then there might be the case that the two LFSR produce the same stream to cancel each other. We can call this a weak-key.

More importantly, an LFSR is linear and linear systems are not secure in Cryptography. You need to add non-linearity. One way to achieve this is by Filtering the states of an LFSR with a non-linear function or using a combining function like in CSS.

In CSS the combining function is 8-bit adder. After 8-clock, which produce 8-bit per LFSR, these 2 bytes are added. The carry is saved for the next addition.

Since addition is non-linear in bit case, the non-linearity is achieved. Of course for security non-linearity is necessary but not sufficient. A good read for LFSR with non-linear combing functions is the correlation attack. A famous article is Decrypting a class of stream ciphers using ciphertext only by Siegenthaler (pay-walled). He showed that a correlation attack can be performed on non-linear combiners.

  How would I go about brute-forcing it, and what would the complexity of the brute force attack be?

To execute a brute force, you need keystream from the cipher. Assuming that you have;

$2^{40}$- the keyspace is not hard to reach in 1996. The reason for low keyspace is well stated in Wikipedia;

At the time CSS was introduced, it was forbidden in the United States for manufacturers to export cryptographic systems employing keys in excess of 40 bits
In 1999 Stevenson showed 3 attacks including brute-force on CSS.
Even DES with $2^{56}$- keyspace can be easily searched with special hardware §,‡ or cluster during 1999s.
There is also a correlation attack that recovers the key with $2^{16}$ complexity.
One can also, attack with guessing $L_1$ and determing the $L_2$ with $2^{16}$ complexity

  If I simply XOR the two LFSR outputs, what would be the result be like (I'm assuming there would be some sort of way to identify the information out of it)?

It will be completely linear and will be much more easy to attack; first, produce algebraic equations then solve by Gaussian elimination. As explained before, the basic countermeasure is adding non-linearity.

  Would a known plain text attack prove effective?

You need a keystream to attack therefore you need to know the plaintext.

§ RSA DES challange in 1997

‡ DES hardware machines since 1997


Finding Small Roots of Multivariate Polynomial Modulo an Integer in Sage (Coppersmith's Attack on RSA) I am trying to implement Coppersmith's attack to find small roots of an example bivariate polynomial.

$f(x,y) = (8x+7)(8y+7) - N \pmod{8}$

In this example, the results should be $x = 2$ and $y = 8$  (obviously you could brute force it, but that's besides the point).

For univariate polynomials, Coppersmith's attack is implemented via the .small_roots() function.  However, it is to my understanding that finding small roots of a multivariate polynomial modulo an integer is not implemented in Sage.  Is there any workaround code / method that will allow for small root finding of multivariate polynomials?

Relevant papers:

http://honors.cs.umd.edu/reports/lowexprsa.pdf

http://www.jscoron.fr/publications/bivariate.pdf

Thanks, and your time and effort are greatly appreciated.

If you calculate modulo $8$, your polynomial becomes constant: $f(x, y) = 1-N \pmod{8}$

So something is wrong about what you are trying to do!


Machine learning to break imperfect randomness I have a shared randomness between two user. But to make situation worse Eve can listen to exchanges and guess noisy or error prone version of shared randomness, whose correlation varies depending on it's proximity from either party. Are there works to help leak secret based on Eve's observation using machine learning?

Both cryptography and machine learning are very broad terms. I gather you are wondering if it's possible to use some sort of inference techniques (like support vector machines or deep learning) to exploit a weak PRNG to extract a secret key. If this is possible, it's only true in a very limited manner, and there are probably more effective ways to infer secret material (see, for example, Bleichenbacher’s method for learning about biased nonces).

The only obvious application to me seems to be in the validation of the strength of a PRNG.

If you're willing to consider other kinds of applications of machine learning, you may be able to make some progress. For example, in this paper (unfortunately behind a paywall), the author trains a neural network to carry out a known-plaintext attack against DES and 3DES and infer the plaintext from a given ciphertext. Of course, DES and 3DES are not secure, and the key is not leaked by the method. Furthermore, I don't find this approach any better than just brute-force. Why not?

Machine learning is most useful when it can teach you something about your data. Good cryptosystems publish their designs, so I already know what they will do with the data, so again, I can really only learn about the security of the generation of secret key material: Kerckhoff's Principle in action.

Machine learning may fit into the security landscape in other ways.  Enter adversarial machine learning, which concerns the security of the ML itself. How do you know someone isn't feeding you deliberately-biased training samples to skew your algorithms, for example?

Also, consider the learning with errors problem: given a system of linear equations mod some $q$, solve it assuming some additive random noise is added in. The "random noise" part makes the solution very difficult. In a way, it flips your question on its head: trying to learn about vectors in this system has created a useful hard problem that cryptosystems can be built from!


Does a thermodynamic limit on key search apply to quantum computers? There is (or at least was) a thermodynamic reasoning that any form of brute force key search would require an energy at least $k\,T$ per key tested, where $k$ is Boltzman's constant and $T$ the device's absolute temperature in Kelvin. It concludes that at the evaporation temperature of helium, our sun's whole radiated energy is short to challenge 192-bit crypto in decades, or 256-bit crypto ever.

Does such thermodynamic limit apply to (still hypothetical) quantum computers doing key search for a symmetric cryptosystem by Grover's algorithm or the like?

From this Thermodynamic Analysis of Classical and Quantum
Search Algorithms, Sep 29, 2017;

  For the problem of collision finding, previous work suggested that quantum algorithms were unlikely to provide an asymptotic advantage in terms of circuit size (despite using fewer oracle queries). Our thermodynamic analysis leads to a similar conclusion. We compare in detail the classical collision finding algorithm of Van-Oorschot and Wiener, and the quantum collision finding algorithm of Brassard, Høyer, and Tapp (BHT) including parallelized generalizations of BHT. We find that the energy consumption
  required to search for collisions on a range of size $N$ using a memory of size $M < \mathcal{O}(N)$ in time $t$ is $\mathcal{O}(N/Mt)$, regardless of the choice of algorithm

  For the problem of unstructured search, it was known previously that Grover’s algorithm does achieve a quadratic speedup over classical exhaustive search, both in terms of circuit size, and in terms of oracle queries. Quite surprisingly, we do not find a quantum advantage using our thermodynamic analysis. On the contrary, we find that a Brownian implementation of classical random search can achieve the same asymptotic performance as Grover’s algorithm (up to logarithmic factors), where we measure the performance in terms of running time, memory size and energy consumption.

According to this article Battle between Quantum and Thermodynamic Laws Heats Up, March 30, 2017 in Scientific American, we don't have the same heat and efficiency rules there, yet.

  Many physicists hope that rebuilding thermodynamics from the laws of quantum mechanics will help to settle long-debated conundrums. Whether the concepts of heat and efficiency apply to tiny electronic components and even atom-sized machines.

The Quantum Thermodynamics Revolution is also a nice article to read.


PHP AES-256 CBC faster than AES-128 CBC? For the last couple of days, I have been learning a bit about encrypting data in PHP, as I need a good encryption/decryption function for storing users' passwords in a DB. I use openssl_random_pseudo_bytes() for the IV, hash_hmac with SHA256 and openssl_encrypt(). Here's the function for encryption:

// 32 bytes (256-bit) (64 char) encryption key
define('ENCRYPTION_KEY', 'd027e7*+7b6d5fcd55f4b5c32611b87cd923e88837b63bf2941ef819dc8ca282');
// 16 bytes (128-bit) (32 char) encryption key
define('ENCRYPTION_KEY2', 'b6d5fcd55f4b5c32611b87cd923e88ae');
function pw_encrypt($encrypt, $key, $type){

    $hmac_key = 'd027e7*+7b6d5fcd55f4b57su921b87cd923e88837b63bf2941ef819dc8ca282';

    $encrypt = serialize($encrypt);

    $method = "AES-$type-CBC";

    $isCryptoStrong = false; // Will be set to true by the function if the algorithm used was cryptographically secure
    $iv = openssl_random_pseudo_bytes(openssl_cipher_iv_length($method), $isCryptoStrong);

    if(!$isCryptoStrong)
        throw new Exception("Non-cryptographically strong algorithm used for iv generation. This IV is not safe to use.");

    $mac = hash_hmac('sha256', $encrypt, $hmac_key);

    $passcrypt = openssl_encrypt($encrypt.$mac,$method,$key,OPENSSL_RAW_DATA,$iv);
    $encoded = base64_encode($passcrypt).'|'.base64_encode($iv);

    return $encoded;
}

So I've run this bit of code to test AES-128/-256 with 128 bit / 256 bit encryption keys. Now the thing that bothers me that AES-256 seems faster than AES-128, is that normal?

Here are the results-- times are usually something similar to this:

$data = '&>tsX@(3BjsAepZW';
Encrypted Data AES-128 128bit key: Length: 153 Total Execution Time: 2.6027361551921E-6 Mins
Encrypted Data AES-128 256bit key: Length: 153 Total Execution Time: 1.8000602722168E-6 Mins
Encrypted Data AES-256 128bit key: Length: 153 Total Execution Time: 1.7166137695313E-6 Mins
Encrypted Data AES-256 256bit key: Length: 153 Total Execution Time: 1.7166137695313E-6 Mins

So, what bugs me:

Am I doing something wrong here, or is AES-128 really slower than AES-256?
How come the length of encoded string is in all 4 cases the same?
Does the encryption key have to be in HEX format or can I use *+/-_.,'?
The key for has_hmac, should it be randomly generated or just as I have it, predefined? If random, what's the best pratice for creating a random key? And what length and type should it be (hex or +*/-'.?)?

I'll answer in order:

No, you may not be doing something wrong. This is just the compiler warming up and performing optimizations. The second run you see that AES-128 is already about as fast, which is what you would expect (it should be ever so slightly faster in the end, but that might not even be noticeable).
Don't know, you'd have to debug, because that's certainly wrong.
The key should not be in any kind of encoding. The key used by OpenSSL should consist of bytes indistinguishable from random. You can use hexadecimals for storing keys in string (something that's rather questionable as well) but you should decode it before using it.
Same as for the encryption key; you'd use openssl_random_pseudo_bytes or another secure random number generator. Then you may encode it to hexadecimals or base 64, as long as you decode it again to binary before you use it.

Note that if you provide a 16 byte key as 32 hexadecimals that you might be using AES-256 without realizing it yourself. Best test against another framework / crypto library (but NOT mcrypt).

You should not store your users passwords encrypted. Instead you should use a password hash such as bcrypt.


Can the attack against SHA-1 be parallelized? Can this attack be parallelized?  It is a $2^{57}$ complexity collision attack on SHA-1 based on disturbance vectors.

If it is practical it is easy on a GPU ($\approx1.1$ GPU-days).  If it is completely sequential it is much more tedious but still possible ($\approx556$ days on a 3GHz CPU).

Both numbers are small enough to beg the question "Why has nobody done it already?".

Reference: Classification and Generation of Disturbance Vectors
for Collision Attacks against SHA-1

Based on the more recent Disturbance vectors for collision attacks against SHA-1 by the same author, which Maarten Bodewes mentioned in the comments, the initial attack/complexity was optimistic/erroneous. The algorithm actually leads to a disturbance vector that had already been published:

  Using our algorithm and those cost function we retrieved all previously
  known vectors and found that the most efficient disturbance vector is the one first reported as Codeword2 by Jutla and Patthak, A matching lower bound on the minimum weight of SHA-1 expansion code.

The estimated complexity of that attack based on the original source is $2^{62}$. The later paper by Stéphane Manuel quotes two estimates of $2^{65}$ and $2^{69}$ depending on the cost function used, and gives some evidence that even those may be optimistic:

  Furthermore, the statistical evaluation of local collisions’ holding probabilities described in the next section shows that local collisions are not independent. Consequently, this type of cost function only gives a rough basis for an estimation of the complexity of the attack.

Either way, this is more costly than the freestart collision attack recently performed ($2^{57.5}$), and similar or slower than Stevens' proposed full collision attack. So that explains why it has not been performed  so far.

Regarding the original question about parallelization, yes, these types of attacks should be "easily" parallelizable (to the degree that implementing them on a GPU is easy).


How to compute the storage cost of encrypted data Let's say I have (as an example only) 1 MB of plaintexts. I want to encrypt it using symmetric encryption algorithm (e.g. AES) and store the plaintext and ciphertext in a memory space. Does a ciphertext take the same size as its corresponding plaintext? I mean, in my example, does this mean I need 2 MB to store plaintexts and ciphertexts? Can you provide references?

Your question is too broad in this form.

There are plenty of different symmetric encryption algorithms. Most of them produce 1MB output for 1MB input. Most of them are block-based, so they round up the input size to a multiple of a block-size. If you choose a specific algorithm, you can check the exact details yourselves. You should not choose encryption algorithm based on the overhead though, but rather choose one based on security and performance.

Also, it is usual to compress data before encrypting it, because it is impossible to do so after encryption.


Algorithm to securely exchange identities Say four people each have a public/private key pair that they can use to encrypt or sign messages. They have an anonymous way to post messages such that the others can see them. Malicious entities can post messages as well, but they can't forge the signatures these four can make.

I'm looking for an algorithm so that the four can, by exchanging posted messages, agree on a new set of four public keys such that each of them knows exactly one corresponding private key. But here's the hard part: None of the four of them can know which private key any of the other three parties know.

If they had a trusted intermediary, they could do it this way: Each of them submits the full set of four public keys to the intermediary, signed with their key. The intermediary confirms the key sets are identical and one set is signed with each key in the set. Each of them submits a new public key, signed with their existing public key, encrypted with the intermediary's public key. The intermediary decrypts these messages and publishes only the list of new public keys in random order, signed with his key.

Of course, I need to do it without a trusted intermediary.

It is okay if observers know the new set of public keys (they're public after all) so long as they don't know which new public key belongs to the same entity as each public key from the start.

It is critical that an attacker who can post messages not be able to slip his public key in. This is a challenging requirement because any message that contains a new key can't be signed with an old key or you can tell which old key corresponds with which new key.

The Simple Protocol:

Alice generates a signature key pair (to sign in step 4, all other signatures in the protocol will be from the original key pairs), calculates its encryption under each of the other participant's public keys, indicates which encryption corresponds to which key, and then signs and posts the result.
The other three participants each decrypt the message encrypted with their public key, calculate the encryption of that under the public keys belonging to the other two of those three participants, indicate which encryption corresponds to which key, and then sign and post the result.
(With signed messages) Those three participants confirm that they got the same signature key pair from all three sources, and then all four participants agree on a time period for step 4.
Each participant generates a new key pair, and posts the public key along with its signature under [the signature key pair from step 1].
Once four posts with a public key and its signature under [the signature key pair from step 1] have appeared, each participant posts a signed confirmation, with the lexicographically sorted list of those four messages, that their public key was the public key in one of those messages.
After each participant has confirmed in step 5 (and made sure the lists of messages match), use the public keys from step 4.

The potential problem is that a participant can trivially force an abort with zero chance of getting

caught. $\:$ Every way I can think of for this loses the property that the [honest participant]-[key pair] relations will be forever hidden from an attacker who doesn't break the cryptosystem before

the protocol ends (long-term security for all participants). $\:$ The best way I can think of is:

(With all messages signed),
Use generic multi-party computation to compute the lexicographically sorted list of a new public key from each party. $\:$ This requires oblivious transfer, and I have no idea how many of them it will need. $\:$ This does not need any anonymous posts, and works against any number of disruptive participants.  Depending on what oblivious transfer protocol is used, this might provide long-term security for one of the participants.


what problem happen if we always use IV Zero in CBC Mode? i have a question about CBC operating mode.
what problem happen if we always use IV Zero in CBC Mode?

It become a deterministic encryption key: Same message encrypted twice, produces the same ciphertext. This has negative consequences on the security of the cipher, because an adversary know if you encrypt the same message, which means she can distinguish encryptions.


How to use HKDF to combine two keys I have heard that to combine two keys HKDF is better than using XOR function. But if you look at the HKDF RFC I could not figure out how to use it for concatenating two keys. What I can see is HKDF can be used to derive a key from another key. So I want to know how to use HKDF to concatenate two keys.

If you have two keys of constant length, using HKDF is rather pointless.

You can simply combine them using a hash function like SHA-2:

$$combined\_key = \text{SHA-2}(k_1 || k_2)$$


How does the possible attack on passwords and salts mentioned in PKCS#5 v2.1 work? From PKCS#5 v2.1, 4.1 Salt (page 6, emphasis by me), also in v2.0, RFC 2898:

  In password-based encryption, the party encrypting a message can
  gain    assurance that these benefits are realized simply by selecting
  a    large and sufficiently random salt when deriving an encryption
  key    from a password. A party generating a message authentication
  code can    gain such assurance in a similar fashion.

  The party decrypting a message or verifying a message
  authentication    code, however, cannot be sure that a salt supplied
  by another party    has actually been generated at random. It is
  possible, for instance,    that the salt may have been copied from
  another password-based    operation, in an attempt to exploit
  interactions between multiple    uses of the same key. For instance,
  suppose two legitimate parties    exchange a encrypted message, where
  the encryption key is an 80-bit    key derived from a shared password
  with some salt. An opponent could    take the salt from that
  encryption and provide it to one of the    parties as though it were
  for a 40-bit key. If the party reveals the    result of decryption
  with the 40-bit key, the opponent may be able to    solve for the
  40-bit key. In the case that 40-bit key is the first    half of the
  80-bit key, the opponent can then readily solve for the    remaining
  40 bits of the 80-bit key.

The part I don't really understand is where it saids "If the party reveals the result of decryption with the 40-bit key, ..."

Could I get some clarification of this?

This appears to be describing an attack that allows an active attacker to defeat a seemingly-secure protocol.

In the normal setting where no one is attacking them, Alice and Bob share a password $W$; Alice derives a symmetric key $K$ from the password $W$ and encrypts her message with $K$, then sends it to Bob; now Bob can derive the same key (since he knows the password $W$), decrypt, and learn the message.  At least, that's how things work when there is no attacker.  If Alice derives a 80-bit key $K$, and if the password is sufficiently strong, then this scheme might be secure against eavesdroppers.

The part you quote is talking about an active attack that could defeat the security of that arrangement.  Recall that Alice (the sender) encrypted with a 80-bit key $K$ (derived from a password $W$).  In the attack, an active attacker modifies the ciphertext somehow so that the recipient Bob will decrypt it with a 40-bit key $K'$ (derived from the same password $W$).  Suppose the derivation procedure has the property that $K'$ is the first 40 bits of $K$.

When Bob decrypts the ciphertext under $K'$, he will get gibberish (since he is decrypting with a different key than Alice encrypted with).  Suppose that Bob replies to Bob with a complaint that decryption failed, quoting the gibberish he got back.  Now the attacker can learn $K'$. Notice that a 40-bit key $K'$ does not provide adequate security, and in this scenario, the attacker knows both the ciphertext and its decryption under key $K'$; thus, the attacker can use trial decryption to find the key $K'$.

At this point the attacker knows the first 40 bits of the key $K$ that Alice encrypted with.  Thus, by doing exhaustive keysearch (trial decryption) on the remaining unknown 40 bits of $K$, the attacker can recover the full key $K$ and decrypt the message.  In this way the attacker learns the resulting message.

This is a related-parameter/related-key attack, where the attacker desynchronizes the endpoints and causes them to use different, conflicting parameters (e.g., different keys, different key lengths).  In general, a well-designed key exchange scheme should be designed to prevent such attacks.  Without additional context, I'd guess that the part you are quoting is explaining the need to guard against such attacks.


Why use a timestamp and how can someone know it's the correct one? Let's say A wants to send a message, so everyone who gets the message, can be assured that it's from A. A then sends a message message|timestamp|E(A_private_key, Hash(message|timestamp))

What are the benefits of timestamp? How can a person who gets the message know that it's the correct timestamp? Why just not send message|E(A_private_key, Hash(message))?

Actually, I guess that you are talking about digital signatures and not about public key encryption (since you want to have message authenticity and not confidentiality).

Whether using time-stamps or not makes sense depends on your application. Basically, the idea is that the verifier can determine when the signature has been issued and in particular that the message existed before some particular point in time.

However, with your above mentioned approach, a verifier can not really be sure, since the signer ($A$) may include an arbitrary time-stamp (this does not necessarily be the correct one and could be "back dated"). Whether this is really a problem, again, depends on your application.

In order to tackle the above mentioned problem with "back dating" and thus to ensure that the message is correctly dated there are so called trusted time-stamping approaches.

If $A$ uses trusted time-stamping based on digital signatures then basically $A$ lets a trusted third party (TSA - time-stamping authority) sign the message along with a time-stamp ($A$ only needs to send the hash value of the message not the message itself, if $A$ does not want to reveal the message) and then $A$ signs the time-stamp+signature from TTP+message with $A$'s own private signing key. Now, everyone in possession of $A$'s authentic public key and trusts the TSA can be sure that the message existed before the time-stamp.

You may also look here for a more detailed discussion on time-stamping.


What is a hard-core predicate? I read this article on Wikipedia: Hard-core predicate.

Still I don't understand what exactly is a hard-core predicate. Is it possible to put this in simple English terminology, and perhaps with a simple example?

In the Lecture Notes on Cryptography of Goldwasser and Bellare, one can find (page 35) the following text:

Recall that f(x) does not necessarily hide everything about x even if f is a one-way function. E.g. if f is the RSA function then it preserves the Jacobi symbol of x, and if f is the discrete logarithm function EXP then it is easy to compute the least significant bit of x from f(x) by a simple Legendre symbol calculation. Yet, it seems likely that there is at least one bit about x which is hard to “guess” from f(x), given that x in its entirety is hard to compute. The question is: can we point to specific bits of x which are hard to compute, and how hard to compute are they. The answer is encouraging. A number of results are known which give a particular bit of x which is hard to guess given f(x) for some particular f’s such as RSA and the discrete logarithm function. We will survey these results in subsequent sections.
More generally, we call a predicate about x which is impossible to compute from f(x) better than guessing it at random a hard-core predicate for f.

So a predicate over $x$ is "a bit of $x$". Not necessarily a bit in the sense of "$x$ can be represented as a sequence of bits"; rather, a function which, from $x$, returns 0 or 1. The predicate is thus a function which "says something" about $x$ where the something is a binary choice.
For instance, over plain integers, "is multiple of 7" is a predicate (any integer is multiple of 7, or not).
A hard-core predicate of a function $f$ is a predicate of $x$ (an input to $f$) which can easily be computed from $x$ but not from $f(x)$. There are very trivial hard-core predicates when the information is simply lost (e.g. if $f(x)$ is defined as "SHA-256 of $y$ where $y$ is the bit sequence of $x$ with the first bit removed" then the predicate "first bit of $x$" cannot, by definition, be recomputed from $f(x)$); these are not interesting for cryptography. More interesting are predicates which do have a well-defined value for a given $f(x)$ (i.e. for a given value $z$, the predicate $b(x)$ has always the same value for all $x$ such that $f(x) = z$).
One example of hard-core predicate is in the BBS pseudo-random generator. Let $n = pq$ a big integer (like a RSA modulus), where both $p$ and $q$ are equal to $3$ modulo $4$. Consider the subset of integers modulo $n$ which are coprime to $n$ and are quadratic residues (a quadratic residue is a value $x$ such that there exists an integer $y$ such that $y^2 \equiv x \mod n$; in plain words, it is "a value which has at least one square root"). It can be shown that a quadratic residue (coprime to $n$) has 4 distinct square roots, and exactly one of them is itself a quadratic residue.
Thus, we can define the function $f(x) = x^2 \mod n$. It is a permutation of the quadratic residues modulo $n$. For a given quadratic residue $y$, there is a single quadratic residue $x$ such that $f(x) = y$.
Now, the predicate: I define $b(x)$ to be the XOR of all the bits of the binary representation of $x$. It returns 0 or 1 (it is a predicate). Given $x$, computing it is trivial. However, given $f(x)$ (i.e. $x^2 \mod n$), computing $b(x)$ appears to be as hard as factoring $n$. If you can factor $n$, you can compute $x$ from $x^2$ and thus computing $b(x)$ becomes easy; the strange part is that there is no known better way to compute $b(x)$ given $x^2$. The predicate $b$ is then said to capture the essence of the one-wayness of $f$: given the output of $f$, not only is it hard to find the matching input, but "only" finding the XOR of the bits of the input is already as hard as that.
Thus, we call the predicate "hard-core".
It is like saying that to invade the USA you have to defeat the whole of fighting-able US citizens, one of them being Chuck Norris. It is reasonable to assume that if you can beat Chuck Norris, then the rest of them should be a piece of cake. Chuck Norris is the hard-core predicate of US military supremacy.


Is there an algorithm that gives a reasonable chance of decoding the entire ciphertext of this encryption scheme? Suppose Alice and Bob share two $n$-bit shared keys, $k_1$ and $k_2$, and decide to send multiple $n$-bit messages to each other. The encryption scheme they use simply sends $c_i = (k_1 + i k_2) \oplus m_i$, where $m_i$ is the $i$th plaintext. Here, the addition and multiplication are both done modulo $2^n$.
Clearly, they can send at least two $n$-bit messages with perfect secrecy, since $k_1 + k_2$ and $k_1 + 2 k_2$ will be independent and have equal probability being each possible $n$-length bitstring. Once they send three, though, we can start learning some information about the plaintexts. For example, $k_1 + k_2$ and $k_1 + 3 k_2$ will always have the last bit, so $c_1$ and $c_3$ will share the same last bit if and only if $m_1$ and $m_3$ did. Still, though, even in this case we still wouldn't know what the last bit of the messages was.
My question is, at what point does it become feasible to figure out the entire message (i.e. how many messages do Alice and Bob need to send before an adversary with relative ease can figure out large portions of the message)? And at this point, what is an algorithm that would recover the plaintexts? We can assume that the messages are patterned, e.g. in the English language, so if we can reduce this problem to one where crib-dragging/frequency analysis/etc. can be applied, that would work!

For a frequency-style solution, we can guess the least significant bytes of $k_1, k_2$, decrypt the least significant byte of each block, and check the frequency (e.g. space should be the most often). Then repeat with the previous byte, etc.
The scheme is bad in that it reduces to schemes mod $2^N$ for any $N < n$.


What are zk-STARK's? The zk-STARK is a proof zero-knowledge proof system that, in contrast to the zk-SNARK, no longer relies on a trusted setup where the "toxic waste" parameters are initialized.

What are, in layman's terms, the basic building blocks of the zk-STARK, and how do they work?

The STARK is a Zero-Knowlege proof system that is transparent. In other words, the prover and verifier didn't need to use a third generated parameters to produce the proof and check the validity of the claim, respectively. Conversely, it would be a lack of security in zk-SNARK systems (these schemes are based on Common Reference Strings (CRSs)).

Let there is a data center to answer the users' queries. For instance, in the CODIS system which is addressed by the STARK whitepaper, verifiers want to know whether a specific DNA profile exists in the FBI data center or not (to prevent further crimes by quickly identifying recidivists). In this term, it is so important for this data center to not only decrease the complexity of executing the protocol for each query but also be secure under the attack of a third trusted party (revealing the information and compromising the privacy by using the Master Key).

Suppose there are 1 million DNA profiles and the data center as a prover wants to produce just a proof for all profiles to convince the verifier. A crazy solution would seem to be the data center produce a proof for each profile but it is not efficient (i.e. doubly efficient).
Regarding the Reed-Solomon (RS) error-correcting codes, the prover is able to obtain the encoded function corresponding to all DNA profiles. For each RS code, $RS[F, S, \rho]$ is the family of functions $f: S\to F$ which these functions are evaluations of polynomials of degree less than $\rho|S|$. Precisely, the output of encoding is a polynomial which the prover claims if the verifier put each DNA profile in this polynomial as input the output is equal to zero (i.e. is a root of a low-degree polynomial). The significant point is that the verifier never knows any information about the rest of the profiles.

But as you know, this is not enough for the verifier to check whether the claimed function is good or bad! I mean regarding the Schwartz-Zipple lemma two distinct polynomials with degree $d$ have at most d intersections so the function $f$ is not unique for 999.999 DNA profile. Moreover, the verifier needs to check all profiles to become sure about the validity of function (i.e is a low-degree polynomial).
The way that is addressed by the authors of the STARK whitepaper is the FRI (Fast Fourier Transform Reed Solomon Interactive Proximity of Testing) scheme. It is a solution for solving the low-degree proximity testing problem. This scheme tried to reduce the number of elements in the set of S step by step to convince the verifier just by checking the low degree polynomial for a smaller polynomial instead of the original structure. (The degree of polynomial chooses less than the number of profiles to provide better soundness, for instance, a polynomial with degree 10.000 for 1 million DNA profiles)

The FRI scheme is based on Interactive Oracle Proof (IOP) systems which the verifier selects some random numbers and the prover provides corresponding oracle access for him/her. Finally, after some rounds, the verifier can decide about the correctness of the prover claim. It is possible to provide non-interactive IOP, also.

The critical point is about the arithmetization in which the prover wants to produce a proximity testing problem corresponding to a circuit satisfiability problem. In other words, the prover and verifier agree for a circuit to prove and check the validity of the execution of it, respectively. This term is based on some techniques to make to solve the problem in logarithmic complexity instead of NP-complete (3SAT is an NP problem). I just mention these techniques here and if you need to know more send a comment.

The circuit satisfiability $\to$ algebraic constraint satisfaction problem (CSP) $\to$ 3SAT $\to$ 3-Coloring problem $\to$ de-Bruijn Graphs to solve 3 coloring problem and so on.

For more information:
https://www.starkware.co/

https://vitalik.ca/

https://drive.google.com/open?id=1zzgOry0ERwTJB3PR5HXGIhrcdH_LcenB

https://drive.google.com/open?id=12K363jIO0bhDSxM_AKYVxG8eNBn9qQ0K


Why can't you hijack someone's public key Sorry, this might be a stupid question but the more questions are here the easier you can use the Internet.
To sign your message in Bitcoin network, Alice uses his private key and message content. Bob verifies it with Alice's public key and message content.

Why can't a new user Fred just choose Alice's public key and generate his new private key? Then sign message with his new private key? So others who don't know Alice will think that Fred is Alice.

Short answer: Because the public key is derived from the private key.

Recall that when we are working with elliptic curves, we rely on the elliptic curve discrete logarithm problem (ECDLP). That is that we assume that if we have:

$$
Q = [k]P
$$

given the points $P, Q$ on our elliptic curve, it is hard to compute the scalar $k$.

Bitcoin uses ECDSA over the Secpk1 curve. In ECDSA, we have the public generator point $G$.
Alice's private key $d_a$ is randomly selected, as a large random number. With this $d_a$, her public key $Q_a$ is computed as follows:

$$
Q_a = [d_a]G
$$

This closely mirrors the equation above, about the discrete logarithm. Now your question is whether Fred can just use Alice's key $Q_a$, and generate his own private key $d_f$. He will only be able to choose a private key for which holds that $Q_a = [d_f]G$, but for this he would have to solve the ECDLP. In the case of for the Secpk1, this is practically infeasible (unless the scheme is broken).


RSA Protocol behind Yaksha Security System So I'm reading over the Yaksha Security System and see it is based on the RSA cryptosystem and a centralized server, easy enough. What I'm slightly confused on is the math behind the related keys.

It states

  nAlice - Alice(some user) modulus
      dAliceA - First private key only known to Alice
      dAliceY - Second Private key only known to Yaksha server
      eAlice - Alice's public key

The keys are related by the following:

  dAliceA*dAliceY mod phi(mod nAlice) = dAlice

It states that the server sends Alice:

  Calice = (Ksession) ^ dAliceY * eAlice mod nAlice

And Alice can determine the session key as:

  (Calice) ^ dAliceA mod nAlice = Ksession

My question is, Can Alice obtain the session key due to the multiplicative properties of the modulus function and the basis of which RSA is built on? Or am I missing something here?

Edit: Also, is dAlice just the combined private key of the server and Alice to verify that the keys are correct?

Can Alice obtain the session key due to the multiplicative properties of the modulus function and the basis of which RSA is built on?

Essentially, yes.  One way of looking why RSA works (that is, why the encryption and decryption are inverses of each other) is because of two mathematical identities:

$$(M^a \bmod N)^b \bmod N = M^{a \cdot b} \bmod N$$

$$\text{If}\  a \cdot b \equiv 1 \pmod{\phi(N)}\  \text{then}\  M^{a\cdot b} \equiv M \pmod{N}$$

(Note: in the second one, you can replace $\pmod{\phi(N)}$ with $lcm(p-1,q-1)$, which gives you a stronger identity; however what I have written is good enough for now).

For normal RSA, this is sufficient; however it is easy to extend these identities to three exponents:

$$((M^a \bmod N)^b \bmod N)^c \bmod N = M^{a \cdot b \cdot c} \bmod N$$

$$\text{If}\  a \cdot b \cdot c \equiv 1 \pmod{\phi(N)}\  \text{then}\  M^{a\cdot b \cdot c} \equiv M \pmod{N}$$

This is what Yaksha is relying on; the have $a$ = the public exponent (eAlice), $b$ = the private key known to the server (dAliceY), and $c$ = Alice's private key (dAliceA).

We can see that the relationship between eAlice, dAliceY and dAliceA holds, based on the fact that:

  $dAliceA \cdot dAliceY \equiv dAlice \pmod{ \phi(mod nAlice)} $

If we multiply both sides by eAlice (and rely on the fact that $dAlice \cdot eAlice \equiv 1 \pmod{ \phi(modnAlice)}$, we get:

$$dAliceA \cdot dAliceY \cdot eAlice \equiv 1 \pmod{ \phi(mod nAlice)} $$

which is precisely the relationship we needed to assume.


Data Switching and Information Leakage Hypothesis: Let $z,a$ be uniformly random elements of a field $\mathbb{F}_p$ where $p$ is a large prime number. Also, let $(-z)$ be additive inverse of $z$.

I have a fixed secret value $x$. I mask it as $I=x+z$ and send it to a semi-honest server.

Later on, I send $w$ and $c=(-z)\cdot w+a$ to the server, and ask it to do as follows:
$K=I\cdot w+c=(x+z)\cdot w+(-z)\cdot w+a=wx+a$.

Question: Given $I, w,c$ and $K$, can the server learn anything about $x$?

Note 1: $z,a$ are secret values, too. So if the server learns about them it may learn about $x$.

Note 2: The above scenario is a part of protocol and it may not make sense for the readers at first glance.

Server receives three messages:

$I=x+z$. This is the value $x$ encrypted with a one-time pad $z$. The server cannot find $x$ without knowing (something about) $z$.
$w$. This is (presumably) independent of anything secret.
$c=(-z)\cdot w+a$. This is the value $(-z)\cdot w$ encrypted with a one-time pad $a$. The server receives no information about $(-z)\cdot w$ and thus $z$ or $x$ without knowing something about $a$.

Therefore, assuming that $z$ and $a$ are generated randomly just for this instantiation and never reused or revealed, and that $w$ is independent of $x, z, a$, the server learns nothing about $x$.


How will be cipher selected when client is running on version TLS 1.3 and server is running on TLS 1.2? How will be cipher selected when a client is running on version TLS 1.3 and server is running on TLS 1.2?

The cipher list provided by TLS 1.3 client will be different than the version supported on the TLS 1.2 server.

If the client is only supporting TLS 1.3  or only TLS 1.3 ciphers the SSL handshake will fail. Otherwise the cipher will be selected as it is usually done with TLS 1.2: the client shows which ciphers it supports in the ClientHello and the server will pick the one which a) is supported by the server and b) fits the type of certificate of the server (i.e. authentication RSA or ECDSA). If there is no common cipher the handshake will fail.


Advantages/disadvantages of different message numbering schemes For a stream of packets, where each packet is individually encrypted with a block cipher, it's desirable to have each encrypted packet only valid for that position in the stream.

A message number would work, but there are many different ways of implementing it.

Given a construct using HMAC for integrity check (i.e. we send (HMAC || cipher-text) or (HMAC || IV || cipher-text), where HMAC is over cipher-text or (IV || cipher-text) respectively).

I can think of the following:

Encrypt (message || message-number), after decrypt check the message number.
HMAC instead (encrypted-message || IV || message-number), message number check is built into the HMAC.
Don't reseed the IV, so assuming CBC the IV of the current packet is the cipher-text of the last block of the previous packet.
Use a random initial IV, then for each packet, the actual IV used is HASH(IV || message number)
Use a random initial IV, then for each packet, the actual IV used is ENCRYPT(IV + message number)

What's the standard way of adding a message number, and are there any known security risks with the other methods I mention above?

If the receiver can wait for all the packets before decrypting:

This case is simple, since your final goal is to ensure that the plaintext you decrypt was the exact same plaintext you encrypted. (Trivially, this includes rejecting re-ordered plaintext.) Use an Authenticated Encryption (AE) scheme (eg, CCM, GCM, etc) across all the packets, treating the packet contents as concatenated parts of the same message. The receiver waits for all packets to arrive then authenticates and decrypts them. If the authentication fails, the message is different in some way, possibly because the contents are re-ordered, possibly something else.

If the receiver must decrypt packets as they arrive:

Encrypt each packet individually. Use an AE scheme that supports additional authenticated data, such as CCM or GCM. Such schemes are designed to encrypt a secret payload and authenticate the same secret payload alongside plaintext data, which is often times metadata relevant to the ciphertext. If the authentication passes, the receiver can be sure that the secret payload corresponds with the plaintext metadata and that both are unaltered.

This allows you to encrypt your plaintext $M$ as $C=E(M)$, authenticate the ciphertext $C$ along with a plaintext packet number/counter $ctr$, then send $(C,ctr)$ to the receiver. The receiver verifies that $(C,ctr)$ properly authenticates, meaning that $ctr$ belongs to that package.

Presumably the packet number isn't a secret since an attacker can probably watch the wire and count packets anyway. Nonetheless, the packet number $ctr$ can be omitted from the data the sender transmits and the receiver can just substitute the $ctr$ value that they are expecting when they receive the packet and perform the authenticate.

The Proposed Schemes

This assumes you're using CBC for encryption and HMAC for authentication.

This is a good option. In concept, you've created a very simple self-contained protocol for your data that encapsulates ordering of the packets. Then the packets are simply encrypted and authenticated. It's the simplest scheme, and the least likely to be screwed up.
This is essentially building an AE scheme for ciphertext and additional associated data (message-number is the associated data). Likely encrypted-message is variable length, but message-number is presumably fixed length. If it is fixed length this should work, if it's variable length this would require modification.
This is potentially risky. The IV for a CBC-encrypted message should be unpredictable and you're working in discrete packets. If the attacker can control what data is in a packet and has seen the previous packet, they will know the IV for the packet they are about to generate and can use that to launch attacks. There was a popular TLS/SSL attack that exploited this type of CBC IV chaining.
This option is actually kind of pointless. It requires that the original random IV be sent along with the derived (aka, "actual") IV, both MAC'd alongside the ciphertext. Verifying message-number would consist of re-deriving the real IV using the random IV and the expected message-number. It's essentially option (2): they both have an IV, message-number-based value, and the ciphertext.

(To see why both IVs must be sent: If just the original random IV is sent, we can't validate that the derived IV is correct. The HMAC covers only the ciphertext and random IV, so after that the HMAC does the check the packet receiver will derive the real IV and have nothing to check it against. If message-number is wrong then the derived IV is wrong, and the first block of plaintext is trashed, but a trashed first block of plaintext is not always detectable.

If just the derived IV is sent, the recipient can't validate what message-number the derived IV is for. The HMAC will validate the derived IV and the ciphertext, but the receiver will just decrypt using the IV, knowing nothing about what message-number should have been used to generate it.)
This would work, but it is pretty much the same as option (1) if you send the "actual" IV, since the receiver needs to check the message-number by decrypting the IV (option (1) would require decrypting the plaintext).

Of those listed, option (1) is probably the best. It isn't the cryptography itself enforcing the message ordering, rather the "protocol" encapsulated within the packets. Option (2) seems perfectly reasonable as well.


Multikeyed Hash: known algorithms? A MAC (or HMAC) can be represented by the general formula:

MAC = H(key, message)

I am calling "Multikeyed Hash" the operation (probably there exists already a name for this concept, which I don't know) below:

MkHash = H(key1, key2, key3, ...., keyN,  message)

Are there known algorithms to compute that? Note that I can't simply concatenate the keys myself, because an attack could be built using the fact that:

MkHash = H((key1, key2), key3, ...., keyN,  message)

would result in the same MkHash.

Are there known algorithms to compute that? Note that I can't simply concatenate the keys

No, you can't just concatenate them, but there are simple modifications to simple concatenation which does make it safe.

The easiest may be to simply prepend the length of every key in the concatination.  That is, if we have:

key1, key2, ..., keyN

we form the string

len(key1) || key1 || len(key2) || key2 || ... || len(keyN) || keyN

Where len(X) is a simple encoding of the length; it might be just an n byte encoding of the length (if you know that no key will be longer than $256^n$ bytes long), or you could go fancier and (say) reuse the variable length encoding from DER.

That way, if you introduce any other sequence of keys, you'll generate a distinct string, and so don't run into collision problems.

This is well known, but not greatly discussed (probably because it is assumed to be fairly obvious/trivial).

The only other thing is that you'd need a MAC that takes a variable length key.  Most don't; however one that does is HMAC.  The other possibility is to just use a collision-resistant hash function on the string (and use the result as the real fixed-length MAC key).


In Result = F (4 - Format of the EM is incorrect - hash moved to left ), the first F says that a correct signature verification implementation must Fail to verify the test vector (for known-good vectors, there is Result = P for Pass). What's in parenthesis following F documents the intention in making the test vector, but that's purely informative.

My guess is that this particular one means that the test vector is believed having been generated with the hash field too much on the left, eating some padding. But looking at EM with hash moved value, this clearly contains an EM for RSAES-PKCS1-v1_5 except the PS field is too short and garbage is inserted on the right, and I can't make sense of that in an RSASSA-PSS test suite. But who cares that a test vector expected to fail is nonsense? The point is that it is rejected; test vectors have poor coverage of possible errors in signature verification code anyway.

Update following comment: There are valid Pass test vectors for 3072-bit RSASSA-PSS in the FIPS 186-3 test vectors, file SigVerPSS_186-3.rsp, from which the question seems to be extracted. The mildly hard thing is extracting them out of the ocean of Fail vectors. Towards this, find immediately above some Result = P the values of SaltVal, S (3072-bit), Msg, d, e, SHAAlg; then somewhere above a value of n (3072-bit); check that d, e, n match by verifying that $2^{ed}\bmod n=2$, then forget about d; you have your test vector! Here is one:

n = ce4924ff470fb99d17f66595561a74ded22092d1dc27122ae15ca8cac4bfae11daa9e37a941430dd1b81aaf472f320835ee2fe744c83f1320882a8a02316ceb375f5c4909232bb2c6520b249c88be4f47b8b86fdd93678c69e64f50089e907a5504fdd43f0cad24aaa9e317ef2ecade3b5c1fd31f3c327d70a0e2d4867e6fe3f26272e8b6a3cce17843e359b82eb7a4cad8c42460179cb6c07fa252efaec428fd5cae5208b298b255109026e21272424ec0c52e1e5f72c5ab06f5d2a05e77c193b647ec948bb844e0c2ef1307f53cb800d4f55523d86038bb9e21099a861b6b9bcc969e5dddbdf7171b37d616381b78c3b22ef66510b2765d9617556b175599879d8558100ad90b830e87ad460a22108baa5ed0f2ba9dfc05167f8ab61fc9f8ae01603f9dd5e66ce1e642b604bca9294b57fb7c0d83f054bacf4454c298a272c44bc718f54605b91e0bfafd772aebaf3828846c93018f98e315708d50be8401eb9a8778dcbd0d6db9370860411b004cd37fbb8b5df87edee7aae949fff34607b
SHAAlg = SHA256
e = 00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000073b193
Msg = 0897d40e7c0f2dfc07b0c7fddaf5fd8fcc6af9c1fdc17bebb923d59c9fc43bd402ba39738f0f85f23015f75131f9d650a29b55e2fc9d5ddf07bb8df9fa5a80f1e4634e0b4c5155bf148939b1a4ea29e344a66429c850fcde7336dad616f0039378391abcfafe25ca7bb594057af07faf7a322f7fab01e051c63cc51b39af4d23
S = 8ebed002d4f54de5898a5f2e69d770ed5a5ce1d45ad6dd9ce5f1179d1c46daa4d0394e21a99d803358d9abfd23bb53166394f997b909e675662066324ca1f2b731deba170525c4ee8fa752d2d7f201b10219489f5784e399d916302fd4b7adf88490df876501c46742a93cfb3aaab9602e65d7e60d7c4ceadb7eb67e421d180323a6d38f38b9f999213ebfccc7e04f060fbdb7c210206522b494e199e98c6c24e457f8696644fdcaebc1b9031c818322c29d135e1172fa0fdf7be1007dabcaab4966332e7ea1456b6ce879cd910c9110104fc7d3dcab076f2bd182bb8327a863254570cdf2ab38e0cda31779deaad616e3437ed659d74e5a4e045a70133890b81bc4f24ab6da67a2ee0ce15baba337d091cb5a1c44da690f81145b0252a6549bbb20cd5cc47afec755eb37fed55a9a33d36557424503d805a0a120b76941f4150d89342d7a7fa3a2b08c515e6f68429cf7afd1a3fce0f428351a6f9eda3ab24a7ef591994c21fbf1001f99239e88340f9b359ec72e8a212a1920e6cf993ff848
SaltVal = 00
Result = P

If you find some reference telling if the MGF1 function shall use the hash designated by SHAAlg, or SHA-1, please share it!


Zero knowledge proof of shared secret Alice holds a secret $a \in X$. Bob holds a secret $b \in X$. Is there a protocol that lets them compute

$f(a, b) = \begin{cases}
1 & \textrm{if } a = b \\
0 & \textrm{else}
\end{cases}$

If $a = b$ the protocol must always succeed.

If $a \neq b$ they should not learn anything else about each others secret.

Of course an adversary could always just pick a random value and succeed with probability $\frac{1}{|X|}$. So an error rate $\frac{1}{|X|} + \epsilon$ is accaptable.

If $|X|$ is sufficiently large, then they could just exchange hashes and compare.

Is there also also a protocol for very small $|X|$?

There are many ways of doing this. A very nice read (but with informal presentation) is this paper by Fagin, Naor and Winkler on Comparing Information without Leaking It. A very fast protocol exists which requires a single oblivious transfer for every bit. Let $n$ be a security parameter; say $n=128$, and let $\ell$ be the bit-length of the inputs.

For $i=1,\ldots,\ell$, Party 1 chooses a pair of random values of length $n$, denoted $x_i^0,x_i^1$.
For $i=1,\ldots,\ell$, the parties run an oblivious transfer where Party 1 inputs $x_i^0,x_i^1$ and party 2 inputs $b_i$ (the $i$th bit of its input)
Party 1 sends Party 2 the value $A=\sum_{i=1}^\ell x_i^{a_i}$ (where $a_i$ is the $i$th bit of its input)
Party 2 outputs 1 if and only if the sum of the values it received equals $A$.

The nice think about this protocol is that it is secure even for malicious adversaries if an oblivious transfer protocols that is secure for malicious adversaries is used.

Note that if party 1 also needs to get output then more needs to be done.


Best way to attack a small e and small m RSA problem? I am working through a series of crypto exercises to learn a bit more about RSA and crypto in general. In the case where one has a small $e$ AND a small m, would it be correct to say that if $m<N^{1/e}$ then we can attack by calculating the $e$-th square of $m^{e}$?

If that is a correct statement, then what would be the best way to approach such an attack practically? Is there a tool that exists? Or would it be better to code a brute force solution in Python?

Apologize for the basic questions - just beginning to dip into crypto. Any advice is much appreciated. Thank you!

In the case where one has a small $e$ AND a small $m$, would it be correct to say that if $m<N^{1/e}$ then we can attack by calculating the $e$-th square of $m^{e}$?

Yes, in a textbook RSA context, where ciphertext $c$ for the small $m$ is computed as $c=m^e\bmod N$, that is $c=m^e$ if $m<N^{1/e}$. But in RSA as practiced, either $m$ is large and mostly random (RSA-KEM), or a padding step is used (RSAES-OAEP or RSAES-PKCS1-v1_5), so that won't work.

  best way to approach such an attack practically?

We want to determine if the $e$-th root of $c$ is an integer, and in the affirmative calculate it, which will be $m$.

It is needed a tool that can compute exactly with large integers. Python, GP/Pari, Mathematica, GMP… have appropriate built-in types, Java comes with a BigInteger package, and it is possible to create one in any Turing-complete language. Some tools have built-in functions to check/compute exact $e^\text{th}$ root. For others an option is to obtain an approximation using floating point, then Newton-Raphson or the less efficient dichotomic search.


Cryptographically strong pseudo-random seq. generators If a pseudo-random sequence generator is built so that it uses an n-bit seed and outputs a string that is of length x. Let's say one wants to generate a bit string of length y and uses the previous PRSG over and over to obtain y bits out of the x bits produced per run. In order to stop repetitions the last n bits of each x bit output is used as a seed for the next output. Why is this not cryptographically strong?

With the problem as initially stated (that is x = 1000, y = 100000, n = 128), the main weakness is that knowledge of the 873th to 1000th bits of the sequence is enough to trivially determine its 1001th to 100000th bits. That's because these 873th to 1000th bits are both part of the output and used as seed for the rest of the sequence.

Update: In order to test if a sequence is produced by the stated generator, or uniformly random, a judge/adversary/distinguisher

asks for one sample sequence R;
extracts the first 1000 bits, giving S;
repeat 99 times: seed PRSG with the last 128 bits of S, generate 1000 bits, and append them to S;
announce that R was produced by the stated generator if S equals R (otherwise announces that R was random).

In theory, the judge has odds $2^{-99000}$ of announcing that a sequence was produced by the stated generator when it was uniformly random (and never errs in the other direction). If the judge had enough computing power for an average $2^{127}$ PRSG, he could further reduce these ridiculously low odds to about $2^{-99872}$ (or even lower if the PRSG is extremely poor) by brute-forcing the initial 128-bit seed.


Which one of the Block Cipher modes is the best? I have two questions regarding the Block Cipher Modes:

Which one of the modes is considered the best?
I know CBC has a problem of IV since the next block of the plain text is XORed with the result of cipher text of the last block and the same with OFB. Is CTR the best one or not?
In "SSL with blockciphers in CBC-mode", does TLS 1.2 use CBC or is there any other modes that is used with TLS 1.2 (SSL 3.0)?

Personally I like the modes that support integrity checking and authentication, e.g. GCM, as they only require one key, and are not vulnerable to changes in the cipher text. One particular important problem area is padding oracle attacks, which are much more common than people seem to admit.

Note that GCM/AES is - just like CTR - a block cipher in stream cipher mode; Basically GCM consists of a GMAC and CTR combination.

GCM is supported by XML encryption v1.1 (XML encryption by itself is very vulnerable to padding oracle attacks). There is also http://tools.ietf.org/html/rfc5288 which describes the use in TLS and http://tools.ietf.org/html/rfc5084 which describes the use in CMS.

GCM seems to have some support, e.g. Java 8 introduces GCM in the standard Java Runtime. For Java 7 and below it is required to use an external provider such as Bouncy Castle.


Is there a way to do fair exchange between two parties who don't trust each other? Let's suppose we have an Alice who knows a secret key A, and Bob who knows key B. Using their own keys, they each encrypt a message (Alice encrypts $m_A$, Bob encrypts $m_B$) with their own key, and send the encrypted messages to one another.

Now is there some cryptographic scheme thinkable that lets Alice only decrypt her message (using key B) when Bob is able to decrypt his (via key A)? To guarantee that Alice will tell Bob her key after Bob told his?

The simplest solution would be a third-party which releases both keys at exactly the same time, but maybe there is also a cryptographic way to do this?

I think what you want to look at is "fair exchange".  There's a giant catalog of protocols for fair exchange.  They've been designed for doing exactly what (I think) you want.

See, e.g.,

https://en.wikipedia.org/wiki/Multi_party_fair_exchange_protocol
Alice trusts Bob only when Bob trusts Alice

Some fair exchange protocols require a third party who Alice and Bob trust, and involve the third party in the protocol.  Others (called optimistic fair exchange) require that there be a trusted third party, but normally the third party does not have to be involved in any way -- the third party only gets involved to settle disputes, if something goes wrong.  Still others try to avoid any third party (e.g., gradual fair exchange); they're not perfect, but they try to ensure that if Alice can learn Bob's message with some amount of effort, then Bob can learn Alice's messages with not too much more effort.

To learn more about fair exchange, do a literature search on fair exchange.  There are lots of research papers on this topic.