How does LUKS encrypt the master key? I'm studying how LUKS/dm-crypt works, and I've learnt that:

the user supplies a (possibly weak) passphrase
the passphrase is turned into a Key Encryption Key (KEK) by a Key Derivative Function (KFD), making it harder to crack via a brute-force attack
the KEK is used to encrypt and decrypt the Master Key
the encrypted Master Key is stored in plaintext in the LUKS header, and the decrypted Master Key is used to encrypt and decrypt the disk sectors using a cipher (e.g. AES)

However, I couldn't find how the Master Key is actually encrypted using the KEK. Is it encrypted using the same cipher that is used to encrypt the disk sectors?

G'day. LUKS stores multiple copies of the master key in what it terms key slots. Each key-slot contains an encrypted copy of the master key, and it can vary in its password-based KDF parameters (and even algorithms). The parameters and algorithms can sometimes be wildly different, giving rise to the circumstance where forcing one key-slot may be infeasible, while another is fundamentally weak. (Both will yield the master key.)
For LUKS1, the best option for the password-based KDF is PBKDF2. For LUKS2, an additional option exists to use Argon2, which gives you the potential to make it even harder to force a corresponding key-slot... but in all cases this will depend on the hardness parameters chosen, as well as the relative strength of the password. (In LUKS2 both options can exist in parallel.)
First, create a file to play with: fallocate -l 32M testing.encrypted.iso and xxd -c32 -l256 testing.encrypted.iso
Now turn it into a LUKS container, noting our two key-slots, both wildly different in terms of relative strength of the password-based KDF:
cryptsetup --type=luks2 --pbkdf=pbkdf2 --pbkdf-force-iterations=1000 --hash=sha384 --luks2-metadata-size=16k --luks2-keyslots-size=$((512*1024)) luksFormat testing.encrypted.iso
cryptsetup --type=luks2 --pbkdf=argon2id --pbkdf-memory=1048576 --pbkdf-parallel=4 --pbkdf-force-iterations=8 --key-slot=5 luksAddKey testing.encrypted.iso

(In fact, our Argon2 key-slot might be derived from pwd awesomedud, while our PBKDF2 one might be 'rp6eq25dgt2orn/mnf. d4r6tj'n2uhpsqsbv.b!)
xxd -c32 -l256 testing.encrypted.iso
cryptsetup luksDump testing.encrypted.iso
cryptsetup luksDump --key-slot=5 --key-file=- --dump-master-key testing.encrypted.iso

Now clean up: shred -z testing.encrypted.iso and rm testing.encrypted.iso.
MASTER KEY RECOVERY
Once the slot key is derived from the password, the alogorithm must then retrieve the encrypted master key from the key-slot area in the header. From https://gitlab.com/cryptsetup/cryptsetup/-/wikis/LUKS-standard/on-disk-format.pdf, figure 5, p11, Fruhwirth '18:

(Apologies for the screenshot, feel free to transcribe this text and replace...)
ANTI-FORENSIC SPLITTING
You may have noticed a function in the previous pseudo-code, AFmerge? My crude understanding is as follows: in the LUKS header, the individual bytes that make up each key-slot are interspersed (intermingled, interleaved) throughout the key-slot area of the header at a particular interval. Cumulatively, the key-slot area will contain n key slots, which are all interleaved. To recover the master key from any given key-slot, you need access to all of the blocks that contribute, otherwise the key won't be recovered.
The reason for this is to reduce the likelihood that any part of the key will be recovered after the user chooses to destroy the header. It is also the reason why you should consider more than one key-slot (ie. a high-entropy recovery key), but regardless, it's critical to keep a reliable backup(s) of the header (edit if you value the data within the container):
cryptsetup luksHeaderBackup --header-backup-file=testing.enciso.header testing.encrypted.iso

More detail on this here - https://clemens.endorphin.org/nmihde/nmihde-A4-ds.pdf, s5.2 p75+, Fruhwirth '05 - but fundamentally:

If the probability to destroy a certain block of data is 0 ≤ p ≤ 1, then the probability that the block survives is 1−p. Given a set of data consisting of n data items, the probability to erase the whole data set becomes worse since p^n becomes smaller as n becomes larger.

... the remaining task is to construct a data vector from an original data item and to make the destruction of a single vector part crucial for the survival of the whole information contained in the data vector.


Cracking Stream Cipher I need to crack a stream cipher. I have a set of plain text and encrypted text pairs.

The hint to the question asks me to use entropy analysis and look at the hex dump of the encrypted text. However, I couldn't find anything useful in either of them.

What should be the approach to solve this cipher?

If the key is always the same and there is no IV (or fixed IV), then

$$plaintext1 \oplus ciphertext1 \oplus ciphertext2 = plaintext2$$


I've got my private key compromised. How does CRL work? How does certificate revocation list (CRL) work? How can I send a request to the CA to add my current private key to the CRL, so no one except me can add my certificate to the CRL?

Related:
- How can we get CA's public key?
- I've got my private key compromised. How does CRL work?
- What happens when a root CA has its private key compromised?

That depends on the concrete CRL.

As long as you have access to your private key, you can sign the revocation request. This prevents anyone without access to the private key from issuing a faked revocation request.

With access to the private key, a faked revocation request can be sent. But in this case the damage is already done, and a revocation is actually helping the victim.


Definition related to homomorphic encryption In the definition of leveled FHE scheme, what is the mining of same decryption circuit?
I have read several papers about this, but I don't understand this notion.

In addition, if the scheme {$E^d$} is leveled FHE (notation based on Gentry thesis), why the scheme $E$ works correctly for circuits of some depth?

I believe you are talking about the accumulative noise associated with performing gate operations on encrypted bits.

When looking at FHE over the integers (without modular reduction), it is easy to track the noise associated with operations.

In the 'AND' operation :
$$\begin{align*}
    c_i\cdot c_j =&\left(p\cdot q_i + 2\cdot n_i + b_i\right)\cdot\left(p\cdot q_j + 2\cdot n_j + b_j\right)\\
    =&p\cdot\hat{q} + 2\cdot\hat{n} + \left(b_i\cdot b_j\right)\\\\
{\#bits(\hat{n})} < & \#bits(\frac{p}{2})
  \end{align*} \\
$$

If this noise constraint isn't preserved, then the decrypt operation no longer holds.
$$Dec(c_k) = b_k = \left[p\cdot q_k + 2\cdot n_k + b_k\right]_p(mod\;2)$$

The introduction of different 'Recrypt' strategies are used to increase the depth of a circuit by reducing accumulated noise.


Integrity with anti-confidentiality The Republic of Brutopia are updating the design of their library cards with a new security feature: a 2D barcode containing a cryptographically signed copy of the human-readable fields on the card. This will allow anyone to verify that a card is genuine and has not been tampered with.

Unfortunately, the library card is the principal form of government-issued ID in Brutopia. You'll probably show yours to almost-random strangers several times a day, whether you want to buy beer, open a bank account, or pick up a package at the post office. And now civil rights advocates and conspiracy theorists alike are up in arms about the privacy implications of using the new barcoded cards for that. Who can really know if the barcode only contains the data about you that you can see for yourself on the face of the card?

It didn't help the government that they published full specifications for the barcode content, including a DSA signature at the end. The critics pointed out that a DSA signature contains an ostensibly-random nonce, and there is no way you can check that it is really all random and doesn't secretly code for personally identifiable data.

It appears that what the government needs is to use something else than DSA for signing the cards. As far as I can make out, what we would ideally want here is a public-key signature scheme with the additional property that

  It should be infeasible to construct a valid public key $K_p$, a message $M$, and two different signatures $S_1$ and $S_2$ such that $S_1$ and $S_2$ are both valid signatures for $M$ under key $K_p$.

Does this property (or something like it) have a name?

And are there generally accepted signature schemes that provide this?

Naively I would expect that RSA, with the input being a hash of the message, padded to the modulus length in some deterministic way, might work -- but apparently best practice is always to use some random padding when using RSA for anything, so I'm not sure whether that would be vulnerable somehow.

Sending information covertly when using legitimate systems is a well-studied field. As another question mentions, key words are covert channel and subliminal channel.

Designing systems with no covert channels is difficult, but not impossible. The main difficulty is to ensure that if any randomness is sampled incorrectly, the legitimate recipient must detect and reject.

For your case, deterministic signatures (as you had almost arrived at yourself) would be sufficient. The main interesting system is RSA-FDH (full-domain hash) which is trivially deterministic. There are also systems that have deterministic signature generation (if you sign the same message twice, you get the same signature), but where someone with the signing key could generate different signatures without the verification algorithm noticing.

For more complicated systems, this becomes much more difficult. For some symmetric cryptosystems, you can use counters instead of random nonces.


Bulletproof and random oracle model I am trying to deal with Bulletproof. I can not find confirmation or refutation of the following assumption:

  Bulletproof cannot work without the random oracle, which is a
  necessary part of the protocol.

Thanks in advance for your answers.

A core component of Bulletproof is a "range proof". Since Bulletproofs are designed to be used in the blockchain setting, it is important for the range proof to be non-interactive. The one used in Bulletproof is obtained by taking an interactive range proof and then compiling it into a non-interactive one using the Fiat-Shamir transform. The random oracle is used to establish the soundness of this transformed protocol. In practice one would instantiate this random oracle with a concrete hash function (say SHA-$3$).

Now, to answer your question whether a random oracle is necessary, it is not clear and is an active line of research. It has been shown that in some cases it is possible to instantiate the Fiat-Shamir transform with concrete hash functions (e.g., the recent construction of NIZK from LWE relies on such an instantiation of the Fiat-Shamir transform [PS19]).

[PS19]: Peikert and Sheihan Non-Interactive Zero Knowledge for NP from (Plain) LWE.


Can one tell private key entropy from a public key? Given a weak entropy private key and its associated public key. Can we predict low entropy from the private key by examining the public key?
In other words, is the low entropy from the private key in some ways 'reflected'
in the public key?
What signals a public key can give in case of a weak private key?

Since the private key is a value, it's entropy is undefined. We could define the entropy (per key) of a process generating the private key, but we'll stick (except in 3) to the usual modeling of asymmetric key generation as a process producing both the public key and the private key from a random generator. We thus reformulate the question as:
Can we detect low entropy at the output of the random generator from the public key alone?
Sometime, depending on the nature and profoundness of the random generator defect, on the cryptosystem, and one how many public keys was examine. Situations where that's possible include:

When the generator twice outputs the same value, and we can see that it twice generated the same public key.
The generator's output during a key generation is, with sizable probability, among a known set small enough to be predicted, and we know the key generation algorithm (part of the standard theoretical hypothesis in crypto). We can apply the key generation algorithm to this set, and test if the public key is among the results. That can also yield the private key.
As a variant of the above, in cases where defects of the generator conspire to make the private key similarly restricted to a small set, and the public key can be efficiently computed from the private key. The later applies to many cryptosystems based of the Discrete Logarithm problem in some public group (ElGamal encryption, Schnorr signature, DSA, ECDSA, EdDSA). It also applies to RSA when the private key contain $e$, or/and $e$ is small enough to be guessable.

For many cryptosystems, these methods are the best known to detect a low-entropy source from the public key. For others including RSA (and more generally most cryptosystem relying on the difficulty of integer factorization), there are better ways. For example, if the prime number generator used to generate $p$ and $q$ of an RSA key returns values in a list of $2^{40}$ unknown (and un‑guessable) primes, that's detectable with good probability from about $2^{20}$ public keys (it also recovers matching private keys for some of the public keys). That's the GCD attack, and it happened, more than once.


adaptation of NIST sp800-22 for short sequences I would like to ask about the NIST test suite for randomness evaluation. The test suite consists of 15 subtests which evaluate the particular property of the sequence.
In fact, each test has an individual of the minimum number of the bitstream (e.g., $10^6$ bits for Random Excursions test or $100$ for Frequency test). What if I want to test the randomness of short sequences like 128 bitstreams. Is there any reference or suggestion about how to modify the NIST test for this task?

Or what if I just neglect those test which requires a huge number of the bitstream. In that case, is the result still reliable?

You will simply not be testing those properties and thus structured nonrandom sequences may pass with respect to tested properties.

For a simplistic example random excursion test fails if the maximum magnitude of the cumulative sums defined by the -1,+1 version of the sequence is too large (much larger than say  $2 \sqrt{n}$ where $n$ is the sequence length.

So you can have long runs and fail random excursions but still pass other tests, e.g., the frequency test.

The paper https://arxiv.org/pdf/1208.5740.pdf has some intuitive discussion of what some of the tests are aimed at.


How to sell a piece of data through blockchain? User A attempts to sell a piece of data D (byte level) to user B at price C through the blockchain. A and B do not trust each other. A worry: After the data D is delivered, B does not complete the transfer; B worry: After completing the transfer, A does not send data D, or sends invalid data D. How to design a reasonable mechanism to protect the interests of both parties?

Etherium handles this. You need a trusted Escrow, If you don't trust a single third party you can use smart contracts to use the network as a distributed trusted third party.
You don't trust any single member of the network or even small conspiring groups you trust the network as whole.

With a smart contract you will provide a commitment on the data you wish to send(possibly a key allowing decrypting other data). You will supply a zero knowledge proof you hold a value matching the commitment as well as other proprerties(matches what you want to send).
Notice this assumes the buyer can verify the data he is buying.

The smart contract goes on the blockchain, and enforces the contract when one side provides publicly a value matching the commitment it can be verified by the contract and funds will be "transferred" on the ledger.

The contract is a program executed by multiple parties on the network, you pay them for their services. In etherium this is the cost of fuel.


Can $y^2=x^3-x+1$ elliptic curve with $GF(3^m)$ where $m=97$ be used for Diffie Hellman key exchange? I am new to ECC. I have just read about the elliptic curve $y^2=x^3-x+1$. I am copying the exact line

The elliptic curve is super-singular $E:y^2=x^3-x+1$ in affine coordinates defined over a Galois field $GF(3^m)$, $m=97$, whose irreducible polynomial is $x^{97}+x^{12}+2$.

Now I have three questions.

How is this curve different from than ordinary elliptic curve $(GF (2^m))$?
Can this graph be used to implement ECDH?
How secure is this curve compared to NIST's recommended curve parameters?

Thank you in advance for your help.

This curve is thoroughly insecure. These researchers performed a computation to break discrete log on this exact curve.
All small characteristic pairing-friendly curves are insecure under modern knowledge. Here is another paper breaking discrete log on a curve over $\operatorname{GF}(3^{6\cdot 509})$ -- note that this field size is much bigger than your curve.


Choosing encryption algorithms and encryption protocols in military systems Militaries use their own cryptographic algorithms, those of a private third party, or ones that are openly available.

But fear of a backdoor having been planted in publicly-available encryption protocols scares them--even though it is technically possible to analyze cryptographic primitives and establish whether or not they are dorked.

Is there any other advantage in hiding the algorithms and protocols a military uses for its systems?

Militaries have some options on choosing Encryption algorithms, schemes, and protocols;

They can use open community encryption algorithms, schemes, and protocols that are designed and analyzed by many brilliant cryptographers.
They can ask to 3rd parties to built for them if they have no Cryptographic expert in their army.
They can create their own Cryptographic Algorithms and Schemes and keep the designs and analyzes to themselves.

They fear from the first option since they don't want to use the open algorithms.
 They think that there can be always a back door.

They use the second option if they don't have the talent and even they buy from a another country's companies. Many examples are exist in history.

For the last two option, we can see it like security by obscurity but not exactly. Oscar (the eavesdropper of the signal) has to deal many problems:

The communication can be online encryption that is the network traffic is always encrypted and there is always a dummy message to encrypt to keep the traffic always on even to prevent signal intelligence.
The even the Error Correcting Codes (ECC) can give huge disadvantage to Oscar. Which ECC is used is a problem especially if the ECC applied data is an encrypted data.
Below this online encryption, the officials of the army can encrypt the messages with the usual symmetric and asymmetric encryption schemes. This turn the data into double encryption.

The above list may no be complete, anyway, jump to history;

The history shows us that, obscurity is not the correct way. Remember how the Enigma was stolen and finally broken. Even when the 4th rotor was introduced, only the knowledge of the 4th hole was enough to break again. Ironically, the M-209 much easier to break which was mechanical marvel.

Today, information espionage much easier than the older times. So, in reality, the militaries also plays with the Kerckhoffs's principles. They assumes that even the designs falls into the hands of the enemy rule, too. They only use the secrecy of the design and analyze as a frontal counter measure with the deep question;

What if our algorithms, schemes, and protocols are not really secure as we think.


Are non bijective sboxes weaker (on feistel networks)? I have heard it anecdotically that non-bijective sboxes are potentially weaker to be used in designs like feistel networks. (since by design, it is allowed for the sbox to be non-reversible)

Is that a fact?

The first thought I had on this was that it may related to the fact that the probabilities of S are not uniformly distributed and so, if you choose the most favorable outcomes you may have an edge over the bijective counterpart in e.g. bruteforcing.

But again I new to the field, so any insights on the matter would be greatly appreciated.

No.

It is one of the main features of a Feistel network that both decryption and encryption just need to evaluate the S-box in the same direction. It could potentially be a weakness if you used invertible functions in the S-boxes: First, you are limited to a much smaller set of functions to choose from. And then you might not be able to find a function which has the other important properties, which are actually needed for security, e.g. non-linearity, diffusion and confusion, a balanced output, etc.


Cryptographic notation in X3DH Key Agreement Protocol Can someone please explain the below paragraphs from section 2.2 in The X3DH Key Agreement Protocol? Please try to explain the whole paragraphs.

1st paragraph:
I want to understand how the DH function is working? How is it calculating the shared secret key using public keys?

  DH(PK1, PK2) represents a byte sequence which is the shared secret
  output from an Elliptic Curve Diffie-Hellman function involving the
  key pairs represented by public keys PK1 and PK2. The Elliptic Curve
  Diffie-Hellman function will be either the X25519 or X448 function
  from [1], depending on the curve parameter.

2nd paragraph: In the first point $F$ is used to identify the type of curve, right? What is the secret key material here? What is the use of HKDF info?

  KDF(KM) represents 32 bytes of output from the HKDF algorithm [3] with
  inputs:

  1) HKDF input key material = F || KM, where KM is an input byte sequence containing secret key material, and F is a byte sequence
  containing 32 0xFF bytes if curve is X25519, and 57 0xFF bytes if
  curve is X448. F is used for cryptographic domain separation with
  XEdDSA [2].

  2) HKDF salt = A zero-filled byte sequence with length equal to the hash output length.

  3) HKDF info = The info parameter from Section 2.1.

The $DH(PK_1, PK_2)$ function is doing the usual elliptic curve Diffie-Hellman algorithm. The secret keys involved are implicit here; of course you cannot compute the shared secret key without them!  Notice that they omit the explicit use of the secret key in the $Sig(PK,M)$ function even though it too requires a secret key.
Yes, the $F$ value is used for domain separation. The input key material is the shared secret key from the ECDH function. Part of the point of an HKDF is to make the output key material appropriately pseudorandom for cryptographic use, and the ECDH shared secret needs this transformation. Finally, the HKDF info allows you to generate multiple keys with the same key material; see the comments here for more.


Key equivalence across different elliptic curves Is it possible to prove key-equivalence across elliptic curves of different order? Specifically:

Suppose I have a key $x$ valid for both curves listed below
On curve $g$ (for example, Curve25519) it maps to $X_1 = x*G$, where $G$ is the generator point for $g$
On curve $h$ (for example, Curve1174) it maps to $X_2 = x*H$, where $H$ is the generator point for $h$

Is it possible for me to submit some public proof that $X_1$ and $X_2$ are generated using the same key $x$, but without revealing the value of $x$?

Yes you can. It is a proof of equality of discrete logarithms. Let's say the order of curve $g$ is $q$ and $h$ is $q'$, the tricky part is how to sample one challenge value that is uniform in both groups $Z_q$ and $Z_{q'}$. You cannot do it in either of the group because the value is not uniformly distributed in the other group. The trick is to sample the value uniformly random from $Z_{q\cdot q'}$, which would solve this problem.

The NIZK version of the proof thus requires a hash function $H:\{0,1\}^*\rightarrow Z_{q\cdot q'}$.

The prover chooses $r\in_R Z_{q\cdot q'}$, computes the following: $t=r\cdot G$, $s = r\cdot H$, $u = H(G, H, X_1, X_2, t,s)$, $v=r+x\cdot u$. The proof is $(t,s,v)$.
The verifier computes $u$ and verifies $v\cdot G=t + u\cdot X_1$ and $v\cdot H = s+ u\cdot X_2$.


Hill cipher cryptanalysis - known plaintext known key size Hello I want to know how to go about this problem
I know the plaintext "abcdef" and the ciphertext. The key size is 2.
I really can't figure out how to find the key for decrypting and encrypting.

Let $k=\left(\begin{array}{cc}k_0 & k_1\\k_2 & k_3\end{array}\right)$ be the key. And I'll assume the transformation $a=0$, $b=1$, and so on.

So you know $k\left(\begin{array}{c}0\\1\end{array}\right)=\left(\begin{array}{c}c_0\\c_1\end{array}\right)$ where you know $c_0$ and $c_1$.

Thus $c_0=0k_0+1k_1$ and $c_1=0k_2+1k_3$. So that is two equations, 4 unknowns. Can't be solved yet. But you have more data which gives you $c_2=2k_0+3k_1$, $c_3=2k_2+3k_3$, $c_4=4k_0+5k_1$ and $c_5=4k_2+5k_3$. Now you have 6 equations and 4 unknowns. Setup a system of linear equations and solve. That will give you the $k_i$ values for your key. The decryption key is just the inverse.

Remember that the math is done modulo 26.

You won't always be able to solve the system of linear equations, but you likely have enough plaintext ciphertext pairs to get it done. Using the PT/CT pairs in the comments, for example, you would end up with the following equations for $k_0,k_1$.

$$
\begin{align*}
2k_0+17k_1&=11\\
24k_0+15k_1&=3\\
19k_0+14k_1&=3
\end{align*}
$$

From there, my preferred method is to take two of the equations, build an augmented matrix and put it in reduced row echelon form. So you'd first have

$$\left(\begin{array}{cc|c}19&14&3\\2&17&11\end{array}\right)$$

Instead of doing all the math, I'll just get you started. Start by multiplying the first row by $19^{-1}=11$. Then you would have

$$\left(\begin{array}{cc|c}1&24&7\\2&17&11\end{array}\right)$$

Then you want to get rid of the $2$ on the second row, so do $row_2=row_2-2row_1$. Eventually you'll be in the right form and have $k_0$ and $k_1$. Repeat this process for $k_2$ and $k_3$. For this one it will work out. If you had started with the $3=24k_0+15k_1$ row on top, you may have gotten stuck since $24$ has no inverse. So if you get stuck (needing to invert something that is non-invertible), try a different equation or a different set of elementary row operations.


Client Puzzles and HMAC I'm learning about client puzzles for DoS (Denial of Services) Protection, and I came across this question.

  For each request, the server sends the client a freshly generated random challenge r and and a difficulty parameter n, and the client has to produce a solution s such that HMAC(s) with key r ends in n zero bits."

What is the expected number of HMAC computations for the client to compute the solution, and the server to check the solution?

I know that the server only needs to compute 1 HMAC, as it has s, r and n. So it would just take the clients solution s, and compute the required HMAC, and see if it has the required number of zero bits at the end.

How would I calculate the answer for the client? I assume the client has to brute force it, so he would keep calculating an HMAC until he gets the required n zero bits at the end. How do I do this computation?

Here is a small scheme how this works :

 Server         Client
   |              |
   |     r,n      |  S: Find s such as HMAC(s,r) = xxxx0000
   |  ==========> |
   |              |  C: *compute HMAC(0,r) = 123456789*
   |              |  C: *compute HMAC(1,r) = 124687946*
   |              |  C: *compute HMAC(2,r) = 164946518*
   |              |  C: *compute HMAC(3,r) = 165498451*
   |              |  ...
   |              |  C: *compute HMAC(42,r) = 16540000*
   |              |
   |    s = 42    |  C: Found it ! s is 42
   | <=========== |
   |              |  S: *compute HMAC(42,r) = 16540000*
   |      OK      |  S: Ok, access granted for you !
   |  ==========> |
   V              V

As an example, lets assume you want only the last digit to be 0.
What are the chances if you were to compute the HMAC for a random number ? well $\frac{1}{10}$. So if you try 10 random numbers, the chances that you got at least one HMAC ending with 0 is pretty decent:

$P = 1 - ((1-\frac{1}{10})^{10}) \approx 65\%$.

However, the more 0 you ask at the end the harder it will be to find a solution. e.g. if you were to ask for 4 zeroes at then end, the chances that you would find $s$ after 1000 trials are :

$P = 1 - ((1-\frac{1}{10000})^{1000}) \approx 9,5\%$.

And after 10000 trials :

$P = 1 - ((1-\frac{1}{10000})^{10000}) \approx 63\%$.

Thus simply by increasing the number of zeros demanded, you increase a lot the time required to find the solution.

Why it is "secure", because you change the $r$ at each tentative. Therefore the client cannot pre-compute the solution.


Hitting a counter example in homomorphic encryption over the integers The paper Fully Homomorphic Encryption over the Integers talks about a super simple symmetric key implementation on page 1 and 2.

It says that to generate a key, you pick a random odd number between $[2^{N-1} ,2^N)$ where N is the size of your key in bits.

To encrypt a bit (a 0 or a 1), you do this:
$c = pq +2r + m$
In other words:
$CipherBit = Key * RandomIntegerA + 2 * RandomIntegerB + PlainTextBit$

RandomIntegerA is there to hide the key better and RandomIntegerB is a small number to add noise to the encrypted value (to make it a "learning with error" problem).

To recover an encrypted bit you do this:
$PlainTextBit = (CipherBit \% Key) \% 2$

You can do an XOR by adding two cipher bits together, and you can do an AND by multiplying them together.

I've simplified my implementation a bit to make it easier to explain in a presentation, so i have RandomIntegerA hard coded as 1, and RandomIntegerB hard coded at 0.

This simplifies encryption (yes, making it insecure, but more easily explained) to this operation:
$CipherBit = Key + PlainTextBit$

The decryption, AND and XOR operations remain the same.

Now that the explanation is out of the way, here is my issue...

When Key is 9 (1001 in binary), let's say i have 3 cipherbits A,B and C that are valued at 10, 10 and 114100 respectively.

A quick check when decrypting them shows that they are all true bits:
$(10 \% 9) \%2 == 1$
$(114100 \% 9) \% 2 == 1$

I hit a problem though when I calculate A xor B xor C.  To do this, I add them all up and get 114120, which decrypts to a zero bit:
$(114120 \% 9) \% 2 == 0$

However, 1 xor 1 xor 1 is 1!

Something I've noticed is that before doing the % 2 on A,B,C their remainders are 1, 1, 7 respectively.

When adding them together, it effectively adds (and mods) their remainders, so it makes sense that (1+1+7)%9 would be 0.

Can anyone see where I've gone wrong?

Thanks!

EDIT: Here is an even simpler counter example
With a key of 9, say we have two encrypted bits: 1 and 8, which decrypt to 1 and 0 respective.

To do an XOR, we should be able to add them.  When we add them, we get 9.

If we then decrypt 9, 9%9 is 0, so it says that 1 xor 0 is 0, which is wrong!

It seems like this scheme doesn't work if you hit these perfect "roll over" points.

Like if your key is 533 and you want to xor two encrypted bits: 532 (0) and 1 (1), you get 533, which decrypts to zero.

Or if your key is 5 and you want to xor 4 (0) and 1 (1), you add and get 5, which decrypts again to zero!

I've seen plenty of other papers extending the homomorphic encryption over integers... surely they can't all be wrong :P  Not sure what I'm messing up though...

The problem is that you're getting an "overflow" of the errors relative to the secret key.

We have $10 \bmod 9 = 1$, and $114100 \bmod 9 = 7$, so the "errors" in your ciphertexts are $1$, $1$, and $7$, which are all odd, hence the plaintext bits are $1$ (as desired).  When you add the ciphertexts, the errors add correspondingly, so you get a ciphertext with error $9$, which normally would decrypt to $1$.  However, in this case your secret key is also $9$, so in fact decryption "sees" an error of $0$, i.e., the "intended" error overflows back to zero.  This is why your final ciphertext decrypts to $0$ instead of $1$.

As the paper explains, the accumulated errors must stay smaller than the secret key in order for decryption to work.  (For simplicity, throughout this answer I'm assuming only non-negative errors, and that the modular reduction returns a non-negative representative.)


Textbook-RSA meet-in-the-middle attack against other RSA based schemes? A “meet-in-the-middle” (not “man-in-the-middle”!) attack on textbook-RSA was presented to me. The only requirements for it was that the attacker gets the output of RSA and the public key, and that the message be the product of 2 numbers of the same magnitude, which apparently happens with 20% probability. (ie: only eavesdropping).

This attack can reduce the attack of a 64-bit message to O(2^34) instead of O(2^64) for exhaustive search. (ie: almost square root of attack time)

The ISO public key encryption scheme has RSA(pk,x) sent "in the clear" as header. So it seems to me that textbook-RSA can be used to recover x, from which Hash(x) gives the symmetric key…

What am I missing here? Could someone clarify please?

Or maybe I do understand correctly, but that meet-in-the-middle attack on textbook-RSA is not that significant (20% chance of achieving sqrt the time of exhaustive search).

edit: Sorry, I made a mistake: the attack can reduce a O(2^64) exhaustive search into O(2^34) attack which is not almost half the time, but almost square root of the exhaustive search time.

meta: I would like to accept answer but I cannot, neither can I add comments

I suspect that the meet-in-the-middle attack you have in mind is what is presented in this answer (or something similar).

If so, then it's not actually correct to say "the only requirement is that the message be a product of 2 numbers of the same magnitude"; the message needs to be a product of two numbers of the same small magnitude.

For example, the attack can work if the message were a product of two 64 bit numbers; however this would imply that the message itself was no longer than 128 bits.

This is a credible attack against textbook RSA used to pass 128 bit messages; however any sane public key encryption method (such as ISO 18033-2) would include padding to make the message presented to the RSA primitive much larger; this completely invalidates this attack.


In RSA, do I calculate d from e or e from d? In the original paper introducing RSA, it is implied that one should first choose $d$ and then calulate $e$ from $p$, $q$, and $d$. However, I have found in other places (such as the wikipedia article on RSA) that one should first calculate $e$, and only then calclulate $d$ from it.

Which of these two methods are preferred, and why?

Well, as far as the mathematics of RSA are concerned, $d$ and $e$ are symmetric; they are related by the relationship:

$$ e·d \equiv 1 \pmod{\operatorname{lcm}(p-1, q-1)}$$

So, from the perspective of making it work, it doesn't matter which you choose first.

Now, it is not sufficient that the RSA encrypts and decrypts properly, it also has to be secure.  From a security perspective, these values are not symmetric; $e$ (the encryption or verifying exponent)  is public and $d$ (the decryption or signing exponent) is private.  This means that $d$ must be a hard to guess value.  On the other hand, we couldn't care less if someone could guess $e$; we're going to tell him that value anyways.

That means that if we choose $e$ (and then compute $d$), we can choose $e$ to be a small value. This has a real advantage; it makes the public operation (public key encryption, signature verification) go much faster, without any loss of security.

In contrast, if we choose $d$ and then compute $e$, we have to select a large value for $d$ (both so that it is not guessable, and to avoid subtler attacks that can factor $n$ given an $e$ that corresponds to a small $d$), and so we end up with $d$ and $e$ both being large.  This slows down the operation without any corresponding advantage.

Because of this, common practice is to select a small $e$ (65537 is the most common value), select primes $p$ and $q$ such that $p\not\equiv 1 \pmod e$ and $q \not\equiv 1 \pmod e$ (so that $d$ exists), and then compute the corresponding $d$ value.


How feasible is word-level frequency analysis over English (or any language)? Say I have some black box which, given any English word, deterministically outputs a token for that word. Assume our black box is implemented using strong cryptography, i.e. the hardness of reversing a token to its word is reducible to some known assumption.

Now, assume I have a document corpus where a document is some list of English words. I run every word in every document through my black box and create a new document set of tokenized documents. I then give the documents to some attacker who then carries out a ciphertext-only attack to try to guess what the documents say.

I'm curious as to how successful this attacker will be in recovering partial information about the documents. He'll try to use statistical attacks to fit the frequency curve of the tokens to the frequency curve of English words. This will allow him to guess the preimages of more frequent words with high confidence, but will he be able to guess less frequently-used words? Are there more advanced attacks he could use?

The feasibility depends a lot on the length of the corpus. The more statistics, the better guesses an attacker would be able to make.

  He'll try to use statistical attacks to fit the frequency curve of the tokens to the frequency curve of English words. This will allow him to guess the preimages of more frequent words with high confidence, but will he be able to guess less frequently-used words? Are there more advanced attacks he could use?

Once you knew/guessed the most common words, like prepositions, you could try n-grams. For example, if a particular token frequently appeared immediately after those for "in the", you could make some reasonable guesses. Find other instances where that token appears and you may be able to cross reference.

In reality, you'd do it programmatically, optimizing a quality function where each word pair/triplet/etc. would add or subtract from the score depending on whether that is a common combination in English.

Knowing exact word lengths would reduce the search space significantly, but with AES block length you'd get almost no extra information, since very few words are longer than the 16 – or 15 with padding – bytes you'd fit in one block, and those will probably not appear often. At least if you use ASCII/UTF-8 for English. UTF-16 would help the attacker some, and e.g. UTF-8 German might (multi-byte characters and longer words).

Trying to apply grammar to the text would be the next step, but I'm not sure it would help. N-grams already tell you what kind of words can follow e.g. an adjective.


Differences between HMAC and HKDF in a specific case I want to use a key derivation function to derive a key from another one.
I think HKDF is the easiest solution in my case.
This explanation gives a clear definition of HKDF.
In the case where the number of key bits requested from the KDF is equal to the hash output length (i.e. L = k in the definition), do I have to compute 2 HMACs:
PRK = HMAC(XTS, SKM) and K(1) = HMAC(PRK, CTXinfo)
or can I directly compute:
K(1) = HMAC(SKM, CTXinfo) ?

HKDF stage 1 is useful for when the SKM value is derived using some deterministic method, such as a key exchange, or from a source that may not be fully trusted. SKM may be substantially larger than the keys you want, but may have the entropy not evenly distributed. Stage 1 compacts and distributes the entropy into a key that is correctly sized for the hash function in stage 2.

If you have a source key from a true random number generator, or that has already gone through a strong KDF, you can substitute PRK with SKM, and skip the first HMAC operation.


Why only one secret value with Shamir's secret sharing? Shamir's Secret Sharing works by sharing data points on a curve, whereby when you have the required number of data points, you can find the function of the curve and find out the secret, which is effectively f(0).

In the polynomial form of the function, the constant (the coefficient of $x^0$) is the secret information.

Could you treat the coefficients of the other powers of $x$ as secret values as well?

If so, are they just as secure / secret? Or is there some subtlety going on where you need fewer values to get the other coefficients?

It seems that if you had a cubic curve that you could have 4 secrets $S_i$, instead of 3 random numbers and one secret:

$$f(x) = S_1x^3 + S_2x^2+S_3x+S_4$$

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

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

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

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


Efficient and stateless anti-forgery method One use of an anti-forgery token is to prevent Cross-Site Request Forgery (CSRF) attacks.    The attacker doesn't need to sniff the wire in order to carry out a CSRF attack.  This attack relays on the fact that the HTTP request is predictable, and the defense is to add a secret value such that an attacker cannot forge this request.

In order for each request to be validated the server must keep track of each client's secret.  This requires the server to use significant resources to keep track of this state for a large number of clients.

Is there a cryptographic method that can prevent forging of requests that also very efficient?

If you don't want to store the anti-CSRF tokens on the server, for most purposes it is sufficient to simply store the token as an HTTP cookie on the client.  The OWASP wiki calls this technique "Double Submit Cookies".

The reason this works is that, in the standard CSRF attack scenarios, the attacker cannot directly read or modify the user's cookies.  Indeed, if the user's authentication credentials are also stored in cookies (as is very commonly done in modern web applications), any leak of cookie data already implies a much more fundamental security failure than a mere CSRF attack.

Of course, an attacker might be able to gain (full or partial) access to the user's cookies via an XSS or other injection attack or through session fixation, but this is mostly outside the scope of CSRF prevention and must be addressed by other means.  (One exception to this are login CSRF attacks, which can be used to carry out session fixation; the solution there is to ensure that authentication entry points are also protected with anti-CSRF tokens.)

One possible improvement on the basic Double Submit Cookie technique I might suggest would be to let the anti-CSRF token included in the submitted form data be derived from the cookie value using a secure MAC (such as HMAC) with a secret key stored on the server.  This has a few advantages over simply using the plain cookie value as the token:

Merely learning (or guessing) the cookie will not allow an attacker to mount a CSRF attack, since they won't be able to derive the token from the cookie without knowing the key.
Conversely, leaking the token will not allow an attacker to reconstruct the cookie; in particular, this means that the user's normal authentication credentials may be safely used to derive the anti-CSRF token, without need for a separate cookie.
By including additional data, such as a form identifier and/or a timestamp, in the MAC input, the token can be made specific to that additional data.  This can compartmentalize the attack surface e.g. by ensuring that an attacker who learns the token for one form will not be able to attack another form in the same application, and that they will be able to carry out attacks only for a limited time.

Edit: Something I forgot to clearly mention in my original answer is that, if you derive the anti-CSRF token using a MAC, you don't necessarily need a cookie at all — all you need is something that is unique to the user.  If you're using cookie-based authentication, using the user's session ID / auth token as the MAC input is a natural choice, but in principle you might as well use e.g. the username instead.

Of course, it's desirable for anti-CSRF tokens to be short-lived, so if you're using a long-term stable value, such as the user name or ID, as the MAC input, I'd very much recommend combining it with a timestamp.  Otherwise each user would be tied to a single token value, such that leaking the token would make the account permanently insecure.  A convenient trick, if you don't want to include explicit timestamps in your forms, is to take some value that changes, say, hourly (e.g. the Unix timestamp divided by 3600), include that in the MAC calculation, and accept any tokens that match the MAC for the current or the previous value.

OK, I guess I should describe the MAC-based scheme explicitly, since it really doesn't bear very much resemblance to the original Double Submit Cookie scheme any more.

Let:

$K$ be a secret key known only to the server (guard this well, and change it if you have any reason to suspect it might have leaked),
$\operatorname{MAC}_K$ be a secure Message Authentication Code (e.g. HMAC) with the key $K$,
$U$ be a unique per-user (or per-session) value which may or may not be public, such as a session ID, a username, etc.,
$S$ be a timestamp of appropriate granularity (either explicitly included in the form data, or implicitly included using the trick described above),
$F$ be an (optional) form / action identifier, and
$D$ be some (optional) extra data included in the form (or used to constrain the form and reconstructible on submission, such as a list of allowed choices in a menu) that you want to protect against modification.

When creating a form, calculate the anti-CSRF token $T$ as $$T = \operatorname{MAC}_K([U, S, F, D])$$ where $[U, S, F, D]$ denotes a string uniquely encoding the tuple $U$, $S$, $F$, $D$.  Include $T$ (and $S$, if not using the timestamp trick described above) as a hidden field in the form.  (If you have plain links that need CSRF protection, you can use the same method; in that case, it's often perfectly reasonable to use the entire URL — excluding the token, of course — as $D$.)

When you receive a form submission, first check that the user is properly authenticated and that the timestamp in the form (if any) is not too old.  If those checks pass, recalculate $$T' = \operatorname{MAC}_K([U, S, F, D])$$ and compare it to the token $T$ included in the submitted form, accepting the submission only if they match.  (If using the implicit timestamp trick, you should also calculate $$T'' = \operatorname{MAC}_K([U, S-1, F, D])$$ and accept the form if either $T = T'$ or $T = T''$.)

Of course, a clever user will notice that there's nothing special about the $F$ and $D$ values in the MAC calculation — they're just arbitrary inputs that, if changed, change the MAC value in a way which, as long as the MAC is secure, an attacker cannot predict without knowing $K$.  You may also notice that the optional inclusion of the extra data $D$ in the MAC calculation makes this technique more powerful than just a classic anti-CSRF token, since it can prevent certain attacks (namely, those involving modification of $D$) even if the attacker has access to the entire form, including the token $T$.  I included this feature in the spec above since it can sometimes be useful, and since we get it essentially for free, at no extra cost in complexity.  Of course, you don't have to use it if you don't want to.

Note: Ensuring that an attacker cannot recover $U$ even if they learn $T$ requires the MAC function to satisfy some additional security properties beyond the standard ones (resistance to existential forgery) demanded of such functions.  However, in practice, most secure MACs (such as HMAC instantiated with a preimage resistant hash function) do have the necessary properties, and in any case, the standard CSRF attack model assumes that the attacker cannot learn $T$.  Still, if you're really paranoid, you may want to choose $U$ such that leaking it will not compromise security.


Base64 encoding of strings I have read everywhere that base64 encoding of unique binary/hex values results in unique output.  The following two string encode to virtually the same output.

{"alg":"SHA1","typ":"JWT","iat": "Sep  8 2018  8:51AM", "exp": "Sep  8 2018  9:11AM"}

gives output:

eyJhbGciOiJTSEExIiwidHlwIjoiSldUIiwiaWF0IjogIlNlcCAgOCAyMDE4ICA4OjUxQU0iLCAiZXhwIjogIlNlcCAgOCAyMDE4ICA5OjExQU0ifQ==

while

{"alg":"SHA1","typ":"JWT","iat": "Sep  8 2018  9:10AM", "exp": "Sep  8 2018  9:30AM"}

gives output:

eyJhbGciOiJTSEExIiwidHlwIjoiSldUIiwiaWF0IjogIlNlcCAgOCAyMDE4ICA5OjEwQU0iLCAiZXhwIjogIlNlcCAgOCAyMDE4ICA5OjMwQU0ifQ==

The only the difference between the two is: ExQU0ifQ== and MwQU0ifQ== at the end of the output.

Only the times are different in the two strings; is that why the difference is so minute?

The whole purpose of base64 encoding is to take arbitary byte values and transform them into a limited subset of ASCII characters so that they can be "safely" sent (older transmission protocols could garble some byte values because e.g. some raw bytes had special meanings to those protocols; the only data that would be expected to not be changed was plain ASCII text.)

It does this by encoding three bytes (24 bits) into 4 characters (each of which has 64 values, so encodes 6 bits as $2^6 =64$) in a pretty simple fashion (some extra rules for incomplete groups). So every aligned identical three bytes in two messages get encoded into the same 4 characters every time. So changing 1 byte only will change at most 2 adjacent characters in the result, if you study the transformation this is obvious.

There is no expectation of more changes: it's just another representation of the same bits in the same order, and easily reversed on the receiving end.

In fact (IMO) in any sensible protocol your JSON-formatted data should be sent as is, as it's already all ASCII, and base64 encoding adds nothing but using more bandwidth. When encrypted it should be random-like binary data and could be sent in base64 format (and this is in fact customary: PEM and PGP send their messages base64 encoded, and very often binary mail-attachments as well.)


Given only RSA public key parameters, what security issues might I be able to detect? I'm attempting to automate some checks against a large list of .NET assemblies, and want to include a test to see if the RSA parameters used to sign the assemblies are sensible. However, since I don't have access to their private keys, I'm wondering how far I can go.

At the moment I'm reporting if:

The modulus $n$ is smaller than 1024 bits (issue)
The exponent $e$ is not 65537 (informational)

The latter is reported due to it being unusual, rather than a flaw in the cryptography, as I've never come across a case where a signed .NET binary uses anything other than 65537.

Are there any other checks I can perform, given only this limited data?

The tests you can do depend on how much time you want to spend for checking each certificate and the "stupidity" you assume for the given key-owner.

You already mentioned the basic checks:

Modulus is too small, only interesting if it's smaller than 1024 bits
Exponent is unusual, not exactly a vulnerability in most cases

The following attacks may take more or less time but applying each of them will give you high assurances that the parameters are indeed not vulnerable. This can be read as a list of techniques for factoring given moduli.

The following techniques are rather fast and may be applied to each modulus.

Check for GCD > 1 with a given database. For example get a database of many certificates and apply the GCD algorithm to each pair, if the GCD is larger than 1 you've found a non-trivial factor.
Check for the Debian RNG vulnerability. Although the vulnerability is quite old you might get "lucky" and find a vulnerable key.
Check if the modulus is a perfect power. This is highly unlikely but can be verified extremely fast, as proposed by Ricky Demer in the comments.
Check if the modulus is a prime, for example using the Miller-Rabin test. If it is a prime it's obviously an invalid modulus, making it possible although unlikely.
Check if $|p-q|$ is small. If so the Fermat factoring (or more advanced version) will quickly factor the modulus. This is highly unlikely as well.

The last few techniques are rather slow and may not be applicable in the given setting due to time constraints.

If you suspect the modulus to contain a few large (128-bit) primes you can try and apply the elliptic curve method. This is rather unusual for RSA moduli.
If you suspect that the modulus isn't composed of safe primes you may want to give Pollard's p-1 and Williams p+1 algorithm a try.
If you suspect the private exponent to be small you can try to apply Wiener's attack.


Can we design a public-key infrastructure without certificate authorities? In a recent essay, Bruce Schneier tasks the engineering community with redesigning and rebuilding the vulnerable parts of the Internet's backbone.

  We need to figure out how to re-engineer the Internet to prevent this kind of wholesale spying. We need new techniques to prevent communications intermediaries from leaking private information.

In my mind, one of the most glaringly vulnerable parts of the Internet's security infrastructure is the certificate authorities. They're big, private companies, vulnerable to legal and extralegal attacks from governments and hackers alike. They nevertheless hold the keys (no pun intended) to the kingdom, cryptographically speaking.

Are these kinds of central trust authorities the sine qua non of a practical public-key infrastructure? If so, why?

If not, what alternatives exist? What would it take to use one of these alternatives in a new, less vulnerable public-key infrastructure? What is the cryptography community's role in this discussion?

There was a post on security.stackexchange last week about this. SSL/TLS with Certificate Authorities for all intents and purposes is now completely insecure from governments and any organisation who has a CA pre-trusted inside the standard web browsers.

DNSSEC will also fall under the same scenario because at the top level you have a particular government in control of the DNS root.

There is one design that may help solve the issue. There's also an excellent talk explaining the issue with Certificate Authorities. At about 35 mins he discusses the problems with the Perspectives Project and recommends another solution called Convergence. I would recommend everyone moves to something like that as a matter of urgency.


Construction of a "simple", nothing-up-my-sleeves, provably KPA resistant symmetric cipher Why is AES secure? Apparently there is no answer - Why is AES resistant to known-plaintext attacks?.
With this in mind, one would obviously want a cipher that is mathematically provable to be resistant to KPA. How would one go about constructing such a cipher? Has it been done? Can it be done? Is someone doing it? Why hasn't it been done? Can you blame mathematics atleast?
When I look at AES, I see a bunch of random up-the-sleeves operations, with, as aforementioned, mostly no explanation. Why can't there be a simple, efficient and secure algorithm to encrypt things?
Imagine a simple (e.g. xor) cipher with a 256-bit key that is applied to each 256 bit aligned block of the plaintext. Suppose it wasn't vulnerable to KPA and other attacks. Then it would be equally secure as AES-256, if not better, given the potential flaws of AES. Problem solved? Unfortunately not; contradiction.

With this in mind, one would obviously want a cipher that is mathematically provable to be resistant to KPA.

Any scheme that has a message space larger than the key space and is unconditionally provably resistant against known-plaintext attacks while being efficiently computable immediately implies $P\neq NP$. As we don't know for sure whether $P\neq NP$ holds and this having been a famously tricky question to answer it seems like it is really hard to build such a cipher.
However if you're willing to make assumptions, we know provably secure constructions. The issue with that is though that most of these assumptions and constructions lead to ciphers that offer no real security advantage over a heuristically well-designed cipher like AES while being much much slower.

When I look at AES, I see a bunch of random up-the-sleeves operations, with, as aforementioned, mostly no explanation.

While this may look to be the case at first glance, the design of AES was very considerate. If you wish to learn more about this topic I suggest you read the book on why AES looks the way it does: "The Design of Rijndael" by Rijndael and Daemen.


Why does Encrypt-Then-Sign not yield a CCA-secure public-key encryption scheme? In symmetric cryptography, combining an IND-CPA secure symmetric encryption scheme with a secure MAC with the encrypt-then-MAC method yields a IND-CCA secure symmetric encryption scheme.
I am trying to understand why this does not hold in the asymmetric case. Suppose you have an IND-CPA secure public-key encryption scheme and a EUF-CMA (or sEUF-CMA) secure signature scheme. When you combine them via encrypt-then-sign the resulting scheme is not CCA-secure.
I know that there are some related questions on this site (e.g. this one or this one). So I understand that the problem is that, when Alice sends a message to Bob, Mallory can intercept it, remove the signatue, sign it again with her own signature and forward it to Bob. Bob then successfully verifies and decrypts the ciphertext and gets the message, thinking that it came from Mallory (since it has a valid signature from Mallory).
But why does this imply that it is not IND-CCA secure? How can an adversary use this property to win the IND-CCA security experiment?
My own thoughts up to now: I am not sure how the IND-CCA experiment in this case works. I would assume that all keys are fixed by the challenger and the adversary only gets the public encryption key and the public verifikation key. Is this assumption correct? Because in this case I do not see how the above attack by Mallory helps the adversary - since all the keys are fixed.
Appendix: How encrypt-then-sign works (or at least how I understood it works):

Suppose everyone has an encryption key pair and a signing key pair
To encrypt a message, you first take the public encryption key of the recipient and encrypt your message with it. Then you use your own secret signing key and sign the ciphertext.
Then you send the final ciphertext (consisting of the signature and the actual ciphertext) to a recipient.
The recipient decrypts the ciphertext, using his secret decryption key and the senders public verification key. First the signature is verified and then the ciphertext is decrypted.

I am not sure how the IND-CCA experiment in this case works.

Well, it doesn't really. There are no verification keys designated as such in the CCA experiment and there is no designated sender in the definition of a public key encryption scheme at all.
So, the only way to communicate to the receiver who supposedly encrypted a ciphertext would be to put it in the ciphertext itself. However, the encryption process takes as input only the encryption key and the message. So where is the signing key going to come from?
The answer is: Either it needs to be an input, in which case what you have is no longer even syntactically an encryption scheme, or you could generate a fresh keypair every time you encrypt. But since those would not be bound to anything this would be useless.

How can an adversary use this property to win the IND-CCA security experiment?

Choose two arbitrary messages $m_0\neq m_1$ and output them as a challenge. Receive the challenge ciphertext $C^* = (c^*,\sigma)$ where $\sigma$ is a signature on $c^*$ under some key which we will have to assume that the receipient magically knows.
Generate a new keypair, sign $c^*$ again, resulting in $\sigma'$ and ask the challenger to decrypt $C'=(c^*,\sigma')$. Since $\sigma'$ is valid, and therefore $C' \neq C^*$ is distributed identically to a ciphertext honestly generated by the attacker we will receive back $m_b$, thus breaking CCA security.


Probability of guessing random 128-bit AES key Consider the following five events:

Correctly guessing a random 128-bit AES key on the first try
Winning a lottery with 1 million contestants
Winning a lottery with 1 million contestants 5 times in a row.
Winning a lottery with 1 million contestants 6 times in a row
Winning a lottery with 1 million contestants 7 times in a row

What is the order of these events from most likely to least likely?

To randomly guess a single key from a 128-bit key space has a chance of 1 divided by the number of elements or $\frac{1} {2^{128}}$ where $2^{128}$ is the number of keys possible.

To get ballpark figures to convert between base 2 exponents and base 10 exponents you can use the following trick:

Because $2^{10} = 1024 \approx 10^3$ you can easily count the number of decimal digits, then divide by 3 and multiply with 10. To go from the number of bits to the number of decimal digits multiply by 3 and divide by 10.

If you want to be more precise: you can divide or multiply with the constant value $\log_2(10) = \frac1{\log_{10}(2)} = \ln(10) / \ln(2) = 3.321928094\ldots$

(easy to remember in your pocket calculator or phone).

So as an AES key is 128 bits you can easily see that it represents about $10^{\frac {128 * 3}  {10}} = 10^{38.4}$ possible values. The bigger the possible value the less likely it is to guess (or brute force) one.

To get to the possibility of winning the lottery you have to calculate $\frac1n$ where $n$ is the number of contestants. To calculate the chance of winning it x times in a row you have to calculate $(\frac1n)^{x}$ which is equal to $\frac1{n^x}$.

As you can see that one million is $10^6$ you can then see that winning it 5 times in a row would be identical to pick one value out of $10^{6^5} = 10^{30}$ values. So you have a significantly better chance of winning the lottery 5 times: $\frac1{10^{30}}$ than picking a random 128 bit AES key: $\approx \frac1{10^{38.4}}$


Find the minimum Adversary's Advantage I am wondering how to solve the problem below:

Suppose we have a $MAC$ scheme $I=(S,V)$. There is another algorithm that can find a pair of texts $(m0,m1)$, with $m0≠m1$ such that $S(k,m0)=S(k,m1)$ for $1/10$ of the Keys $K$.What is the minimum $Adv$$MAC$$[A,I]$ for every adversary $A$?

MAC defined over $(K,M,T)$ is a pair of efficient algorithms $(S,V)$:

$S(k,m):$ returns a message athentication code $t$ which belongs to a set $T$
$V(k,m,t):$ returns a value $true$ or $false$ depending on the correctness of the received authentication code

$M$ is a set of all possible messages $m$
$K$ is a set of all possible keys $k$
$T$ is a set of all possible authentication codes $t$

Thanks in advance!

It seems to me that the answer to the question, as literally asked, is $0$.  This is because you're asking for the minimum advantage "for every adversary", and the set of possible adversaries includes e.g. the trivial adversary that simply always outputs an empty message and a random tag $t \in T$, and thus has a probability of exactly $1/|T|$ of successful forgery.

However, that's almost certainly not what the question is trying to ask, if only because the answer above doesn't actually make any use of the extra collision-finding algorithm.  What I suspect the question should ask is something like:

  Let $(S,V)$ be a MAC scheme (as defined above), and let $C$ be an efficient algorithm that will output a pair of distinct messages $m_1 \ne m_2$ such that $S(k, m_1) = S(k, m_2)$ for a randomly chosen key $k \in K$ with probability $1/10$.  Show that for any such triple $(S,V,C)$ there exists an adversary $A$ (with oracle access to $S(k,\cdot)$ and $C$) that can forge a message with advantage at least $a > 0$ independently of the security parameter, and determine the maximum value of $a$ for which this claim holds (assuming that secure MAC schemes exist).

As for solving this problem, consider an adversary $A$ that uses $C$ to generate a message pair $m_1, m_2$, queries the oracle for $t_1 = S(k,m_1)$ and outputs $(m_2, t_1)$.  What is the advantage of such an adversary?

For bonus points, show that, given a secure MAC scheme $(S^*,V^*)$ (i.e. one against which no adversary has more than a negligible advantage), we can construct a triple of efficient algorithms $(S,V,C)$ that has the property described in the question, and against which no adversary can have more than a negligibly higher advantage than the adversary $A$ described in the previous paragraph.


Why are HOTP and TOTP implementations all using 6 digits and not more? I was checking the RFC's after wondering for some time. In RFC 4226 - HOTP: An HMAC-Based One-Time Password Algorithm, it states on the appendix:

  A simple enhancement in terms of security would be to extract more
  digits from the HMAC-SHA-1 value.

  For instance, calculating the HOTP value modulo 10^8 to build an 8-
  digit HOTP value would reduce the probability of success of the
  adversary from sv/10^6 to sv/10^8.

  This could give the opportunity to improve usability, e.g., by
  increasing T and/or s, while still achieving a better security
  overall.  For instance, s = 10 and 10v/10^8 = v/10^7 < v/10^6 which is
  the theoretical optimum for 6-digit code when s = 1.

While checking implementations, I don't realize what's the problem with extracting 8 (or more) digits from the HMAC-SHA1 result.

Is this merely a matter of improving the user experience by saving the user from writing 10 digits instead of 4? or is there a mathematical reason that I'm missing?

It is for user experience reasons, as you surmise, but the security is not compromised as much as you may think.

Most implementations use 6 digit HOTP/TOTP schemes and design their implementation of the scheme to give them a security level they are comfortable with.

For HOTP, the key parameter that allows 6 digits to be secure enough is the throttling behavior. When combined with a sensible look-ahead window size $s$, the probability of a brute force attack succeeding is low enough as the account or client will be unable to attempt a large number of guesses.

The throttling argument for TOTP is the same, as it is based on HOTP. The security calculation differs but the same principles apply.

The converse of course is that inappropriate selection of look-ahead/behind or throttling behavior does indeed open up a 6 digit decimal OTP to brute force attacks with high probability of success.


Webcam random number generator I have a question about random number generators.

I have read from a real random number generator, based on a webcam ("randcam"). My problem is, that I do not really understand how the generation of the random numbers works. Has anyone heard of this principle before and can give some hints how it could be implemented? And how randomly is this method, I've read it should give real random numbers, but is this true? I've found an implementation in C++, but I did not really understand how this implementation works, I am not that familiar with C++.

A video camera can obtain entropy, but only at a fairly low rate and only if allowed to see "unusual" scenes… like someone making funny faces, unusual movements, etc. Of course, this only works in a room with no video bugs.

Theoretical explanations…

Depending on your knowledge-range, the following sources may be able to explain ways webcams can be used for random number generation:

Patent US 5732138 A — "Method for seeding a pseudo-random number generator with a cryptographic hash of a digitization of a chaotic system."
Inventors: Robert G. Mende, Landon Curt Noll, Sanjeev Sisodiya
Original Assignee: Silicon Graphics, Inc., Filing date: 1996-01-29, Publication date: 1998-03-24
Random Numbers Generated from Audio and Video Sources
2013, I-Te Chen, Department of Healthcare Administration & Medical Informatics,  Taiwan
Random Number Generated from White Noise of Webcam
Jer-Min Tsai, I-Te Chen, Jengnan Tzeng
2009 Fifth International Conference on Intelligent Information Hiding and Multimedia Signal Processing
ISBN: 978-0-7695-3762-7

Getting more practical…

If the above is too theoretical for you and you want a more practical explanation of how it can be done, there's a cool "how-to" article at inventgeek.com that shows how to create an "alpha radiation visualizer" from scratch within an hour… using a webcam and a regular smoke-alarm device as radiation source.

EDIT

Sometimes I stumble upon a wave of disinformation wobbling through the internet (and I’m not talking about Crypto.SE in this case, which seems to have escaped this particular wave so far). Most of the time I manage to keep my mouth shut, but this is one of those rare occasions where I felt the urge to draw a clear line between amateur chit-chat and actual cryptographic security. After all, when creating your own “randomness” thingy, you do not want to step into the most obvious pitfalls… do you?

Always remember that it only takes a tiny glitch to make your “randomness” thingy as insecure as leaving your key stuck in your front-door.

For example: I repeatedly have to disagree with people telling the world it‘s OK to rely on JPEGs provided via their webcam software, which are auto-stored on their disks and later fetched to extract “randomness” from those images. Let’s be clear on something: when doing so you are actively ignoring several issues, both from a cryptographic as well as from an infosec point of view.

Time to dive into some stuff, just for the fun of providing some food for thought…

Trust

How trustworthy is that 3rd-party webcam software you are relying on?

Think about it for a second before we simply skip this rather tin-foil hatted question, assuming you absolutely trust your webcam software because (for example) you coded it yourself.

To further limit the scope of my edit, I’m also skipping the talk about the potential issues arising from storing those images to HDs, USB sticks, or whatever storage medium you might be using. Besides the fact that this would quickly wander off into InfoSec realms, only you can know if we can or should assume your disks and system to be safe from any 3rd party access at all times because (for example) you’re the best sysadmin known to humanity and never sleep anyway.
JPEG is not even close to raw signal data!

Do not just jump for the next image format available, unless you know what the specific image format (read: file format) actually contains, how that format may influence the security of your implementation, and how potential implications of individually chosen image/file formats can be secured.

If you don‘t plug into the webcam hardware directly, at least be smart enough to use as much raw signal data as you can get… and one thing is for sure: using JPEG is not the smartest choice. Remember that JPEGs (like most image formats) introduce a repeated and predictable data block (the image header), and lose some of the wanted entropy (due to the lossy data compression – among other things) while all that post-processing takes time. To lift related issues, you‘ld have to post-process the already software-processed “random data” which created the (to stay with the example) JPEGs. By now, your own logic should already be screaming at you that using raw image data extracted directly from your webcam hardware is the smarter, safer, and faster choice.

Personally, I’ld advise you to either use raw signal data (available via hardware modification), or to grab raw image data directly from your webcam (using appropriate software and/or drivers).
“Webcams only offer JPEG” and “Webcams don’t offer raw image data” are blunt lies!

Sooner or later, you will stumble upon some people that try to tell you it’s not possible to grab raw image data from webcams and that webcams only provide JPEG output. While I somewhat admire the boldness of people pushing out such balony into the digital voids, I honestly can’t help feeling the need to explicitly state that they are absolutely wrong.

What those people are forgetting (or actively ignore) is the fact that it‘s not the webcam itself, but the webcam software which produces those JPEG images from raw image date that software grabs from the webcam. Besides potential licensing restrictions related to individual hardware, there is no reason why you wouldn’t be able to do the same raw image data such webcam proggies use – without applying JPEG compression or other image processing.

For your convenience, here are some hints of software projects which are able to grab raw image data from webcams… just in case you ever feel like proving such claims wrong:

fswebcam (quote: RAW - Reads images straight from a device or file.)
AviRaw - read raw webcam AVIs (which is – among other things – used to look at the stars)
An Image Grabber for the Creative WebCam Go

Please feel motivated to do your own research. Search engines tend to spit out truckloads of alike software solutions and sourcecodes which practically enable you to grab the raw image data from various webcams and related systems.

From this point on, be confident that anyone claiming it can‘t be done is either not informed, or bluntly hiding his/her ignorance behind an easy to uncover lie. Don’t waste your time on such people – simply turn around, take a deep breath, and try to find someone smarter to talk to.
Always “Combine & Hash”

It doesn’t take a 3-letter agency sitting in a black-windowed van to ruin your “randomness”. In fact, even that old microwave oven your neighbour uses might be that ill-placed that it influences the noise which you hope to gain from your hardware. Badly shielded speakers also tend to do their badness. And 3rd-party wifi activity as well as mobile phones outside of your home also have a good chance to skew your noisy pattern. Shielding your webcam as well as the rest of your hardware might be an option, but to keep it short: one should always assume raw signal data can and will be messed with actively and/or passively… and it’s pretty unlikely you will be able to detect such influences ad-hoc, if at all.

Due to that, I heartly recomend to generally push the captured (raw) signal data – preferrably combined with additional random data from other sources – through a cryptographically secure hash. Sure, a cryptographically secure hash takes its time to be computed… but it‘s much better to invest time in a good hash than in some superfluous image format processing (and post-processing to lift related issues) as described above in #2.

Depending in your individual setup and scenario, a HMAC might be even more applicable as it can help protect you in some of the extremer “failing randomness” situations where a regular (cryptographically secure) hash might fail to protect you.

Or you could get a bit crazy like I did when I created something related as a hobby project a few years decade ago. I ended up feeding some randomness sources to AES in CTR mode, while pulling random IVs and keys from a hashed combination of other randomness sources… think: encrypting combined random sources with IVs and passwords generated from hashes of other combined random sources, where all random sources are absolutely independent of eachother. Most of you will surely agree that this setup was more of a “crypto-overkill”… still, it was able to blow “blindly trusting what webcam & co. provided” out of the water. To my defence: I was young and über-motivated… ever since, I’ve learned to create smarter things with less overhead. ;)

Cryptography is only as smart as you implement it.

It should be noted that hashing data (either via a hash or a hmac) surely won’t save you from breaking your neck in every potential scenario, but when you watch your steps by combining raw webcam data with other independent randomness sources, hashing the lot holds the potential to increases the chances of (cryptographic) survival of your home-made “randomness” thingy.

Nevertheless, things like “still images” hold the potential of providing not enough entropy. Which is one of the main reasons why you shouldn’t generally assume ”any pic is OK” and – whenever possible – mix randomness extracted from your webcam with other randomness providers (either hardware or software based). If you don’t know what other randomness source to use, here’s a hint: at the time of writing, all major operating systems provide their own way of extracting cryptographically secure data via software. If that’s news to you, RTFM.

/* Nota Bene: Since point #4 might inspire some cool Crypt.SE questions, I’ll leave it standing as unspecific as-is. */
To build a new car, you don’t have to reinvent the wheel.

Be sure not to get caught up in an “I‘ll create my own…” mantra just because you‘re fiddling with your own hardware. There are dozens of well-vetted solutions in the realms of cryptography that may be able to fit your individual setup, implementation, and/or needs – which practically means there might be no need for you to “create your own”. In case of doubt, click that “ASK” link and throw in your question with a short but on-point description of what you’re trying to achieve. There are ample experts around here at Crypto.SE who are able to answer near to any crypto-related question you might have. It’s always better to ask for help and infos, than to be sorry later on.


Doubling a point on an elliptic curve I'm working with the elliptic curve $\mathcal{E} : y^2 = x^3 + 11x^2 + 17x + 25$ over $(\mathbb{Z}_{31},+,\cdot)$ and am trying to double $P=[2,7]$.

Following the instructions here, I'm doing the following:

$$s = \frac{3\cdot2^2+17}{2\cdot7} \equiv 29\cdot14^{-1} \equiv 29\cdot20 \equiv 22 \pmod{31}$$

$$x_R = s^2 - 4 = 480 \equiv 15 \pmod{31}$$

$$y_R = s\cdot(2-x_R) - 7 \equiv 22\cdot18 - 7 \equiv 17 \pmod{31}$$

That would then give $P+P=R=[15,17]$.

However, when I verify my result with sage, it seems incorrect:

sage: E = EllipticCurve(GF(31),[0,11,0,17,25]); E
Elliptic Curve defined by y^2 = x^3 + 11*x^2 + 17*x + 25 over Finite Field of size 31
sage: P = E(2,7); P
(2 : 7 : 1)
sage: P + P
(25 : 17 : 1)

What am I doing wrong?

Note: this is a homework assignment. Please provide just a hint, if at all possible.

The formulae on the linked page deal with curves in short Weierstraß form, that is $y^2=x^3+ax+b$. Your curve is not given in this format.
You can find the correct formulae for long Weierstraß curves (like yours, where the coefficients $a_1$ and $a_3$ are zero) on this page.


Is Chaocipher a secure cipher under ciphertext-only attack? Chaocipher was invented by John F. Byrne in 1919. The algorithm was recently revealed – see Moshe Rubin's Chaocipher Revealed, the Algorithm (PDF).

While a known plaintext attack successfully finds the keys, nobody has been able to put forward a general solution to this cipher. Is that possible?

While a known plaintext attack successfully finds the keys, nobody has been able to put forward a general solution to this cipher. Is that possible?

You really have to go back in time to learn that ChaoCipher has been subject to some cryptanalysis before the description of the algorithm/device was published. As an example: Here’s one of the oldest papers I found related to the cryptanalysis of the ChaoCipher which was first published in 2003… long before the algorithm was published in 2010 and long before the cipher was subject to a complete break.

If you do a bit of research, you’ll find a few more papers. Most cryptanalytic looks at ChaoCipher have shown ample weaknesses in the distribution, producing anomalies which could be exploited.

Having used the algorithm description to code a C version, I quickly discovered it works somewhat like a substitution cipher that incorporates a primitive version of an lfsr which scrambles the S-box. Nothing you would want to use in times of modern cryptography. It’s more like a most-primitive rotor machine.

Anyway… getting back to the core of your question: is it possible that no one has created a general “this breaks it from every side” solution?

Sure! One reason can be found in the fact that a known-plaintext-attack counts as a complete break (and in this case, a practically feasible one too). Finding additional attack vectors can be fun as a hobby, or it may be something you might want to check on while writing a thesis about ChaoCipher… but it’s not that interesting for most cryptanalysts to dive in deeper when a cryptographic algorithm already was subject to a complete break. Instead, cryptanalysts will be more interested in finding weaknesses in more modern (currently used) ciphers. Compared to modern cryptography, ChaoCipher can’t hold up.

On the other hand, there are ample  websites that talk about its internals… leaving the chance that one day, someone may find ways to break it from all sides – after investing enough time and efforts.


Why is a smaller value preferred for the public key in RSA? For my practice implementation of the RSA cryptosystem I use a random value generation function such the value of public key e holds:

The public exponent $e$ and the modulus $n$ should be $e<\phi(n)$
$e$ and  $\phi(n)$ are coprime, $gcd(e,\phi(n)) = 1$

Although this works satisfactorily, the algorithm returns values of $e$ which are very large in magnitude which, apparently, is undesirable.

Why is it preferred to generate smaller values for the public exponent in the RSA system?

As you said, choosing a large $e$ can make you vulnerable to attacks such as Wiener attack's because a big $e$ makes it possible to have a small $d$. It will also make the cost of your encryption higher. So big $e$ is not necessarily a problem (if make some verification on $d$, such as $d>\frac{1}{3}\times n^{\frac{1}{4}}$), but not the best choice.

A very common value for the public exponent is  $e=65537$, because $65537 = 2^{16}+1$, which has a nice binary representation (like all Fermat primes):
$$10000000000000001$$
This allow a fast computation using algorithm such as the sliding windows

You could choose $e=3$ for more efficiency, but you have to use a proper padding (RSA OAEP for instance). Using $e=3$ without proper padding will weaker your encryption scheme.

More details can be found in fgrieu's answer to a similar question.


In ECDSA, how many field operations are used for signature verification? I am wondering about the computational cost of ECDSA signature verification, in term of multiplications in the base field; and, as an aside, in term of (much cheaper) additions. To make things concrete, assume ECDSA in a field $GF(p)$ per FIPS 186-3 (which refers to ANSI X9.62:2005 (webstore)), using parameters as in appendix D.1.2.

I'm interested first in the straightest standard-abiding method with a cost in the right ballpark; then in the most worthwhile refinements of that. I have identified (by name, but not quantitative effect, especially for the first one):

projective coordinate systems, said to allow replacing inversion in the base field (as used in straight point addition in the elliptic curve group) by fewer operations than standard inversion algorithms, e.g $x\mapsto x^{p-2}\bmod p$ (or the more efficient extended euclidian, but that does not quite match my "multiplications in the base field" evaluation criteria);
Shamir's trick, where $a*P+b*Q$ is computed by adding either $P$, $Q$ or $P+Q$ (on the elliptic curve group) when scanning the bits of integer multiplicands $a$ and $b$;
sliding window techniques when scanning the bits of a multiplicand.

I'm not interested in the cost of verification of a certificate introducing the public key, or the cost of hashing; and only marginally by savings enabled by pre-computations, or techniques applicable only to $GF(2^n)$, or using the special form of the $p$ parameter (which allows speed-up of modular reduction $\bmod p$, but leave the number of operations in the base field unchanged).

Usually, the interleaving of wNAFs is faster than Shamir's trick for simultaneous point multiplication.
Using interleaving with window sizes 5 (fixed) and 4 (random), the total number of operations is roughly (taken from Hankerson et al's Guide to ECC)

$(0.37t +  3)A + (t + 1)D$

where t is the bitlength of the scalars (which should be the same as the bitlength of the field size for standard curves), A is a mixed point addition (projective + affine) and D is a point doubling.

For standard prime curves with $a=-3$, using Jacobian coordinates, we have (from the EFD):

$A = 7M + 4S$,

$D = 3M + 5S$,

where $M$ is a field multiplication and $S$ is a field squaring. Therefore,

$M = (5.59t + 24)$,

$S = (6.48t + 17)$.

For the 128-bit level of security, if I got everything right, $t=256, M = 1455, S = 1675$.


Are SSL/TLS used for maintaining data confidentiality? In SSL/TLS, we use symmetric and asymmetric keys to encrypt the data. Does that mean that the keys are used to encrypt the data (preserve the integrity) or provide a secure channel for the data to be sent?

And as far as I know, hashing algorithms – inside of the SSL handshake protocol – are used to provide data integrity. So when data is encrypted via SSL/TLS, do they:

Encrypt the data like hash algorithm, or
Encrypt the data so that there is no eavesdropping of data? Meaning: they provide a secure channel which means they make use of symmetric, asymmetric key to preserve data confidentiality (no eavesdropping) and hashing to preserve integrity?

The answer to the first question is both.

TLS uses a custom PRF based on HMAC to generate symmetric and MAC keys from a shared secret. The shared secret is created during the asymmetric key exchange between client and server as part of the handshake.

The PRF generates key material of a required length. That length is determined by the key sizes and the key quantity. Those are related to the ciphersuite chosen. If an encryption algorithm provides both confidentiality and integrity (like AES-GCM), only 1 key per party is generated. If HMAC is used to provide integrity, 2 keys are generated. The PRF may also generated initialization vectors.

Different keys are generated for both client and server, so there are 2 keys generated for authenticated encryption algorithms, and 4 keys for algorithms that require a MAC for integrity. The keys used to encrypt the data in transit are used with symmetric algorithms. For data secured by TLS, the hash algorithms are used in the MAC, and not part of the encryption process.


Untraceable communication protocol I am doing a research about secure communication protocols.

I would be interested to know whether a protocol exists such that it grants that the two end-points taking part to the communication cannot be traced (i.e. They can deny the communication ever took part).

Can anyone point out any relevant publication?

There are two requirements here:

Anonymity - the two end points must not be able to discover the other's location or identity, nor must any other party be able to identify either endpoint.
Plausible Deniability - both parties must be able to plausibly deny that they participated in the conversation.

The problem with this type of communication over the Internet is that packets must be routable. You need a way to ensure that messages can be passed between the two end points.

I'm not sure there is a protocol for this per se, but you should definitely look into anonymity networks such as Tor. These work by creating a network of nodes that facilitate anonymous communication.

Tor's anonymity works on the principle that information about a particular conversation is only partially known by any node.

A conversation is created by chaining a number of nodes together, between a source and client. The message is encrypted using EndPoint2's public key. The public keys of Node1, Node2 and Node3 are used to encrypt the identity of Node2, Node3 and EndPoint2 respectively, to produce a chain.

EndPoint1 <---> Node1 <---> Node2 <---> Node3 <---> EndPoint2

From this, we can construct a list of what each participant knows:

Node1 knows EndPoint1's identity and Node2's identity
Node2 knows Node1's identity and Node3's identity
Node3 knows Node2's identity EndPoint2's identity
EndPoint2 knows Node3's identity and the message

Notice that no single node knows about both EndPoint1 and EndPoint2, and only EndPoint2 knows the message. The communications between each node are encrypted, so it is impossible for an attacker to know if a node is the originator of a message or just a node in the chain.

When it comes to the final destination of the message, Tor can use both hidden services (Tor nodes with services running on them) and normal internet services. In the latter case, the message is encrypted with the final node's key, so that it can read the message and talk to the target. If the target is a plaintext service, a compromised node might perform a MitM attack. As such, it's best practice to use SSL or a similar secure protocol when talking to non-Tor services.

For a slightly more in-depth review of how Tor works and how it might be attacked, see my answer to another Tor-related question on Security.SE


Relationship between $N$ and $\phi(N)$ in the RSA algorithm Recently I started learning how the RSA algorithm works and there is one single part of the computation which really confuses me and can't get over it.

Let's say I chose 2 prime numbers,

namely

$P = 3$ and $Q = 11$

$N = 3 \times 11 = 33$

$\phi(N) = (P-1)\times(Q-1) = 20$

Now, I have to chose e based on some criteria (as per RSA), let $e = 7$
Now, I have to determine $d$ by using, $e^{-1} \equiv1 (\bmod \phi(N))$
When I encrypt and decrypt,

a) cipher = $m ^ e \bmod N$

b) message = $c ^ d \bmod N$

In the above case, instead of $\bmod N$, for the same example, I tried different $N$ than the actual $N$ ($33$), it didn't work for any other number other than $33$. Why is it so? I can feel since finding $d$ is based on inverse under $\bmod \phi(N)$, there is some relation between $N$ and $\phi(N)$, but couldn't get my head on it.

Is there some relation between $N$ and $\phi(N)$, if so, how can I learn about it in detail?

RSA is based on some mathematical theorems. The first theorem that you need to learn is the Euler's Theorem;  if $n$ and $a$ are coprime positive integers, then

$$a^{{\varphi (n)}}\equiv 1\bmod n.$$ when $n$ is a prime it is the Little Fermat Theorem.

This theorem tell us that in the power we use modulo $\varphi(n)$, i,e, $$a^{x} \equiv a^{x \bmod\varphi(n)} \bmod n $$

When one performs the textbook RSA encryption one calculates $$c = m^e \bmod n$$ and decryption performed as $$m = c^d \bmod n$$

Now, explicitly;

$$c^d = (m^{e})^d = m^{ed}$$ Since we choose $d$ as the inverse of $e$ modulo $\varphi(n)$, $e\cdot d = 1 \bmod \varphi(n),$ then

$$ m^{ed \bmod \varphi(n)} = m^1 = m \bmod n$$

  I tried different N than the actual N (33), it didn't work for any other number other than 33. Why is it so?

Because the calculations that you performed uses modulus other than defined. $m^e$ will be a different number in a different modulus.

Note that: You used $\varphi(n) = (p-1)(q-1)$ when $n=pq$. Normally Chamichael lambda $\lambda(n)$  is used $\lambda(n)=\operatorname{lcm}(p-1,q-1)$ and $$\varphi(n)=\lambda(n)\cdot\gcd(p-1,q-1).$$ This gives smallest $d$ to operate.

Note 2: In the above textbook RSA is used which should never be used without proper padding. For encryption, one should use RSA-OAEP which is introduced by M. Bellare, P. Rogaway. Optimal Asymmetric Encryption -- How to encrypt with RSA and PKCS#1 v1.5 padding. The former is preferable since it has security proof and PKCS#1 v1.5 PKCS1v1.5 encryption is inherently hard to use securely and should not be used.

Actually, we don't use RSA for encryption, We prefer hybrid encryption. RSA is mostly used for signatures and for signatures RSA is used with Probabilistic Signature Scheme (PSS). Again this is introduced by M. Bellare, P. Rogaway; PSS: Provably Secure Encoding Method for Digital Signatures

Remember, RSA Signing is Not RSA Decryption


Fast hashing into elliptic curve Is there a fast algorithm for mapping $n$-bit numbers $s$ (for fixed $n$) into a cyclic subgroup of an elliptic curve (over a finite field) in which the Discrete Logarithm Problem is hard?

By fast, I mean it takes about as long as a point addition (and is much faster than a point scalar multiplication in the elliptic curve group, or an exponentiation operation in the finite field).

The mapping: $s \rightarrow s \cdot G$, for some generator $G$, would be too slow, and also would defeat the security of construction since the discrete logarithm with respect to $G$ would be known.

It is not necessary for the running time to be independent of the input.  For instance, for elliptic curves defined by

$y^2 = x^3 + ax + b$

over the finite field $F_p$, there is the standard method of setting $x = s \bmod p$, and then computing the square root of $x^3 + ax + b$.  If $p = 3 \bmod 4$, then we can compute the square root using exponentiation in the finite field.  If the square root does not exist, we increment $x$ and try again.  In this way we can obtain a point in the elliptic curve group, and if our cyclic subgroup has cofactor 1, then we are done.  This method would be valid except that computing the square root via exponentiation takes significantly more time than a point addition.

Is there some method/choice of elliptic curve that allows a much more efficient mapping to be defined?

The speed I'm looking to beat (in order for this construction to be faster than an alternative that does not use elliptic curves) is around 100000 operations (hashes to curve points) per second on a standard single CPU core (e.g. 3.2GHz Nehalem) with a 256-bit elliptic curve.  Testing with libsecp256k1, which seems to include an optimized square root implementation, I can compute only about 77000 square roots per second.

Over large characteristic fields, I am not aware of any "point generation method" that can be computed faster than a base field exponentiation, and I would be very surprised if such a thing existed even if you do not require constant running time. So your best bet in general is probably Icart's function (I'd pick that one over Elligator if I didn't need injectivity), which won't be fast enough for your purposes.

Over binary and ternary fields, however, it is possible to do better. For example, in the binary field case, you can use the binary Shallue–van de Woestijne encoding, which can be computed with simple base field arithmetic and half-traces, as discussed by Brier et al. in Appendix E of this paper.

Some colleagues and I have an implementation paper that should appear on the IACR ePrint archive shortly, and it computes that function to a 254-bit binary curve in well under 10,000 Haswell cycles, so your goal is easy to achieve on newer CPU architectures (I think recent AMD CPUs should be quite fast as well). Nehalem doesn't have a carry-less multiplier, however, so binary field arithmetic might be quite slow in practice on that architecture.

Incidentally, as this question falls squarely within my research interests, I'm quite curious about your concrete use case if you can say something about it.


How to prove that a rainbow table is complete? Passwords that are hashed but not salted can be cracked using the rainbow table. I went through this and this which explains the logic behind rainbow table very well.

But I am missing something about the rainbow tables; how can one be sure that the hashes for all valid passwords are covered by the table ?

Lets say the passwords are 8 characters are long from [a-z][A-Z][0-9]. If I am constructing a rainbow table with 10000 hash & reverse iteration in a chain how can I determine at what point the table is complete ? ie: the password and the final hash stored includes the hashes for all the 628 valid passwords somewhere in the chain ?

Is there a mathematical way to verify the completeness of a rainbow table ?

Rainbow tables are not complete. But some have good coverage. We estimate how many distinct hashes are covered by a rainbow tables using statistical tools.

We can build perfect rainbow tables where we throw out colliding chains. This reduces redundancy in the final table. But even in a "perfect" rainbow a certain hash can appear twice(but not in the same column) so we still need to estimate the coverage.

As we approach full coverage it becomes more and more expensive. Because with a table with high coverage nearly anything we add would already be covered.


If PRF is non invertible, why does Ctr-mode work? I am currently taking Dan Boneh's Cryptography I course online.
I have just finished the segment discussing the Cipher Block Chaining and Counter-Mode.
I am having difficulty understanding why Ctr-Mode works as an encryption algorithm as PRFs are fundamentally non invertible, as per my understanding. Any clarification on this would be highly appreciated!

CTR consists of two parts: construction the key stream using a counter, and XOR-ing the output of the key stream with the plaintext/ciphertext. The key stream can be generated using a PRF, in which case it is of course not invertible. The key stream can also be created using a PRP (e.g. a block cipher like AES) in which case it is invertible.

As indicated, CTR mode encryption requires the XOR-ing of the plaintext / ciphertext as well. A PRF is a pseudo random function, so given the same input it will generate the same key stream. The XOR-ing of the key stream is perfectly reversible; you just have to perform the XOR with the key stream again. So CTR mode encryption is always reversible, even when it relies on a PRF to generate the key stream.

Because of this, CTR-mode is indeed not a PRF.