How can a public-key encryption scheme be used to construct a commitment scheme in the CRS model? For a PKE scheme $(Gen, Enc, Dec)$, the most 'obvious' idea is to commit to an encryption of a bit and in the reveal phase maybe send $r_g$, $r_e$ where $r_g$ is the randomness of $Gen$ and $r_e$ is the randomness of $Enc$.

However, if the encryption scheme is not perfectly correct, then maybe there is some $sk, sk'$ such that $Dec(sk, c) = 0$ and $Dec(sk', c) = 1$, so binding fails, because we can fiddle with $r_1$.

A solution is to only reveal $r_2$, and then in revealing one only needs to check that $Enc(pk, b, r_2) = c$. Particularly, if the probability over $Gen$ that there exists some $r_2, r_2'$ with $Enc(pk, b, r_2) = Enc(pk, 1-b, r_2')$ is negligible, then this almost works. However since the sender doesn't have to prove what $sk$ they used, we can still break binding.

How can we get around this issue in the CRS model?

Particularly, if the probability over $Gen$ that there exists some $r_2, r_2'$ with $Enc(pk, b, r_2) = Enc(pk, 1-b, r_2')$ is negligible, then this almost works.

Actually, if the public key $pk$ is a valid public key (that is, corresponds to an actual secret key), the probability is 0.

Here's why: we have $Dec(sk, Enc(pk, x, r)) = x$ for all $x, r$.  Hence, $Dec(sk, Enc(pk, b, r_2)) = b \ne Dec(sk, Enc(pk, 1-b, r_2')) = 1-b$, and so $Enc(pk, b, r_2) \ne Enc(pk, 1-b, r_2')$

On the other hand, this still leaves open the question of "what if the committer were to pick an invalid public key (which does allow collisions)", for example, RSA with $e$ not being relatively prime to $(p-1)(q-1)$.

Hence, if we were to use this commitment scheme, we would reveal $r_g$ as well; this allows the verifier to construct the public key for himself (and verify that the $pk$ in the commitment was done honestly).


Clarification regarding multiple modular exponentiation If the base is same and exponents are different,
for example:

$R_1=b^x\bmod{p}$; $R_2=b^y\bmod{p}$; $R_3=b^z\bmod{p}$;
($p$ is large prime (2048 bit); $x$, $y$ and $z$ - 160 bit integers))

To calculate $R_1$, $R_2$ and $R_3$ at the same time, then my question is:

Does the calculation finish in around one exponentiation or three exponentiations? (I feel it is one exponentiation time)

Here's one approach that, assuming $x, y, z$ are random, takes approximately the same time as two exponentiations.

The general idea is to treat x, y, z as base 4 values, which we scan from the lsbit direction.  We keep running values for $R1, R2, R3$, which are initially 1.  At iteration $i$, we have the value $b^{4^i}$ and $b^{2 \cdot 4^i}$ (which takes two modular squarings to compute); if any of $x, y, z$ have a 3 in the digit $i$ position, we also compute the value $b^{3 \cdot 4^i}$ (this happens with probability 0.578, and takes one modular multiplication when it does).  Then, for each of $x, y, z$, if their digit $d$ is not 0, then we multiply in $b^{d \cdot 4^i}$ into the corresponding $R$ value; for each variable, this takes one modular multiply with probability 0.75, for a total of 2.25 expected multiplies.

If we add everything up, we have 2 modular squarings, and 2.828 modular multiplications per step; for 160 bit exponents, there are 80 steps.  If we remove one squaring (for the initial computation of $b^{4^0}$), and the 3 initial modular multiplications of $R1, R2, R3$, we get a total of 159 squarings, and 223 multiplications; this is in the same ballpark as twice the number of operations a good modular exponentiation for a 160 bit exponent would take.

I suspect that this isn't the best possible; it does show that some speed up can be achieved.  On the other hand, I rather suspect that it'd be impossible to compute all three $R1, R2, R3$ in the same time that it takes to compute one of them; some slow down would appear to be inevitable.


Using a blockchain for secure communication I've recently heard of the idea of using a blockchain for secure communication. No details were given so it's a little hard for me to say that it can't be done. But as far as I know:

Secure communication doesn't need blockchains. We have AES, MACs,
digital signatures, etc. for that.
Blockchains are only useful for documentation. Not for securing
anything.

Am I missing something here?

Secure communication doesn't need blockchains. We have AES and digital signatures for that.

Correct, though we also require tools other than block ciphers and digital signatures. But that is besides the point, as "blockchain" is not on that list.

  Blockchains are only useful for documentation. Not for securing anything.

Blockchain is a distributed, append-only ledger. That in itself does not provide confidentiality, integrity, or authenticity. However, availability is one of the pillars of information security, and it is arguable that blockchain could be used towards that end.

  Am I missing something here?

Probably not. It has become trendy to try and attach blockchain to everything:

  Long Island Iced Tea Corp., now called Long Blockchain Corp., received an ultimatum from Nasdaq in October, when the exchange threatened to delist it unless the market value rose above $35 million for 10 business days in a row. It achieved that on Friday, flaunting one of the hottest buzzwords of the year to get there.

Often times by people who don't/barely know what cryptography is, how it works, or what is is useful for.


How to test the robustness of the cipher image against chosen and known plaintext attacks? Is there any algorithm to test the robustness of the cipher image against chosen and known plaintext attacks?

If you wish to construct a system which is resilient to Chosen Plaintext Attacks and Known Plaintext Attacks, the method to do so is through provable security, not empirical tests. If you're attacking an existing scheme which has not been proven secure, typically you would perform a variant of one of the methods that have been used for cryptanalysis in the past. For instance, you can try differential cryptanalysis or linear cryptanalysis.


libsnark generator toxic waste I'm looking through the test and examples of libsnark, let's take for example here:
https://github.com/christianlundkvist/libsnark-tutorial/blob/master/src/test-gadget.cpp
at line 19 there's:
  default_r1cs_ppzksnark_pp::init_public_params();

Is this the step that generates the toxic waste?

If so, then the same protoboard is used to generate the verification and proving keys, but then also to create the proof:
  const r1cs_ppzksnark_proof<default_r1cs_ppzksnark_pp> proof = r1cs_ppzksnark_prover<default_r1cs_ppzksnark_pp>(keypair.pk, pb.primary_input(), pb.auxiliary_input());

but shouldn't the prover and the generator be different entities? On the other hand, if I look into the initialisation (init_public_param) in the end I end up in the definition of public_params for curves in libff:
https://github.com/scipr-lab/libff/blob/master/libff/algebra/curves/public_params.hpp
which is just a list of templates, there's nothing private about it.

How should the generator step be separated from the prover step?

The prover has everything (public and private info), so he can indeed generate the circuit from scratch, but the verifier should "not" accept the keypair from the prover, correct?

Finally, the generator (who knows everything, public and private info) prepares the keys, sends them to the prover and the verifier. The prover constructs its own pb (protoboard) because he needs the pb.primary_input() and pb.auxiliary_input() to create the proof, then uses its own pb with the generator's proving key to generate the proof. In my experiments the keys generated by the generator and by the prover are the same even if I initialise 2 different pbs, this is counter intuitive to me because the prover can impersonate the generator. Are the keys the same because the init process of the protoboard is the same?

Thanks for anyone who read this far! Any hint is appreciated
T.

The line:
  default_r1cs_ppzksnark_pp::init_public_params();

is used to specify the public parameters used by the proving system ($\mathbb{G}_1, \mathbb{G}_2, \mathbb{G}_T, \mathbb{F}_p,$ ... etc). These are known by the generator, prover, and verifier and therefore are not secret.
You are 100% correct that the prover and generator should be different entities - the generator uses random "toxic waste" values to generate the keying material. Anyone who knows these toxic waste values can break the soundness guarantees of the protocol and forge proofs for statements of which it doesn't know a witness.
To answer your other questions:

How should the generator step be separated from the prover step?

The generator should only run once by a trusted party and publish the resulting proving and verifying keys. In practice, secure multiparty computation (MPC) protocols are used such that as long as $1$-out-of-$n$ of the participating parties are honest, the toxic waste is never learned by any of the participants. This is what ZCash did for instance: https://z.cash/technology/paramgen/

The prover has everything (public and private info), so he can indeed generate the circuit from scratch, but the verifier should "not" accept the keypair from the prover, correct?

This is correct. In fact, anyone can generate the circuit (and some corresponding prover/verifier keys) from scratch, because a witness is not required in order to generate these. However, a verifier should never blindly trust keys that were given to it.

Finally, the generator (who knows everything, public and private info) prepares the keys, sends them to the prover and the verifier. The prover constructs its own pb (protoboard) because he needs the pb.primary_input() and pb.auxiliary_input() to create the proof, then uses its own pb with the generator's proving key to generate the proof. In my experiments the keys generated by the generator and by the prover are the same even if I initialise 2 different pbs, this is counter intuitive to me because the prover can impersonate the generator. Are the keys the same because the init process of the protoboard is the same?

I have a feeling that your experiments are off. Libsnark gets randomness from /dev/urandom, so two different invocations of the generator should result in different toxic waste values, and accordingly different keying material. The generator is executed on the line:
const r1cs_ppzksnark_keypair<default_r1cs_ppzksnark_pp> keypair = r1cs_ppzksnark_generator<default_r1cs_ppzksnark_pp>(constraint_system);

If you run this step multiple times, you'll receive a new keypair each time.


Is it safe to generate two 256-bit ECC keys from 128 bits of entropy? Apparently it is perfectly safe to use 128 bits of entropy to generate a single 256 bit ECC key. Can I use 128 bits of entropy and a KDF to make a 256-bit ECC key?

I assume this is because 256 bit ECC keys have a bit strength of 128 bits according to How many bits of entropy does an elliptic curve key of length n provide?

The first article linked above however stipulates that if more than one 256-bit ECC key was being generated from the 128-bits of entropy, there might be the possiblitity of a 'multi target attack'.

Consider the following scenario:

128 bits of entropy are passed through keccak-256 to generate a 256-bit ECC private key. A second ECC private key would then be generated by hashing the first 256-bit ECC private key.

Would this be liable to such a 'multi target attack'? If so, how would that attack work? Can this situation be resolved by increasing the initial entropy above 128 bits, and if so, how much higher would it need to be to allow for the two ECC private keys to be safely generated?

This question is applicable to Monero, where it is the case that 256 bits of entropy are used for a wallet's private spend key. That key is then hashed with keccak-256 to generate the wallet's private view key. The necessity of 256 bits of entropy has been questioned.

The safe way to generate a large amount of entropy from a small seed is to use a CSPRNG. Most CSPRNGs in practice use a stream cipher at their core to expand a small amount of input entropy into a large keystream. The way this is done (and the process of seeding and re-seeding the generator) is very important to security, so it's best to use an existing library or your operating system's built-in CSPRNG.

The multi-target attacks are better described in DJB's page on batch attacks. They're an issue whenever there are a large number of users each with a large number of keys. The chances that an attacker will guess at least one key that at least one user has used can be quite large, even though the chance that the attacker will guess one specific key of any one specific user is still minuscule.

Batch attacks are an issue for AES-128 because 128-bit AES keys are often generated in the ephemeral key exchanges of TLS sessions. Every time a user goes to a new https webpage a new key is generated with them. Consider all users across all https pages on the internet and the chances that the NSA/PLA/FSB/Mossad/etc will be able to decrypt at least some traffic are actually quite high.

Batch attacks are much less of an issue for ECC keys, as they are often quite long term. There simply aren't enough private keys for Monero wallets for this to be a significant issue.


What is the most an adversary can do in the context of public key masquerading? Suppose two parties A and B are using a public-key encryption scheme in order to communicate securely. A and B both have a public/private key pair:

$$ A: (P_A, S_A), B: (P_B, S_B)$$

and A already knows about B's public key but has no proof of authenticity.
What is the most an adversary C can do while impersonating one of the parties (we assume there is no authentication employed). For example, if C masquerades as B and creates a key pair:

$$ C(P_B, S_C) $$

he may be able to trick A into sending it encrypted messages with the public key of B, but not more since not being in possession of B's secret key C cannot retrieve the message from A. But what more can C do from this point with retrieving the secret key of B? In a more concrete setting, how can the RSA scheme be exploited as mentioned above?

Perhaps the situation should be concretized a little.

A and B both have a public/private key pair:

Does A already know $P_B$, and vice versa? If not, then $C$ can send to A the $P_C$ saying it's «$P_B$» (similar for B, $P_C$ substitutes $P_A$), and become a typical man-in-the-middle, being able to, for example, remove any «real» message from B to A (something he can perform without keys at all) and decrypt or even modify everything that A sends to «B».

but not more since not being in possession of B's secret key C cannot retrieve the message from A.

Hypothetically, if A is «naive» enough (may A be a machine, for instance?), C sends him the message like «stop using my public key $P_B$, instead use $P_C$» (encrypted with $P_A$), A decrypts it with $S_A$, believes without approvals, switches to $P_C$, and then C becomes a man-in-the-middle again.

Does A know $S_B$? Obviously, he must not; otherwise, using the preceding trick, C may convince A to share $S_B$, and impersonate B elsewhere.

In general, the «exploitability» here depends not only on the cleverness of C, but on the «naivety» of A and B as well (they have to know what's dangerous and don't do it).

do from this point with retrieving the secret key of B?

Didn't you mean without retrieving?

Sorry if this looks like a comment. In case you consider a man-in-the-middle attack to be «the most an adversary can do» (or at least critical), it probably helps to concretize the picture. Also, although it is stated that

assume there is no authentication employed

to avoid man-in-the-middle attack is a kind of authentication, in itself.

When the situation is clarified, other answers will be much more useful, and this one may be deleted.


ECB vs CBC for encrypting high entropy data I have a master AES key and I need to encrypt other AES keys with this key. Is ECB safe to encrypt highly random data (a key)? What benefit would I get if I use CBC instead?

In particular, are the following methods secure, which one is more secure and why:

AES-ECB(random_data)
AES-CBC(random_data, iv = zero)
AES-CBC(random_data, iv = random)

ECB is fine for encrypting random data. The point of ECB is that it is secure as long as the input of the blocks isn't repeated. It's often used as a key wrapping method which seems to be your use case.

Note that ECB mode is often used incorrectly even for key wrapping. For instance because the key is embedded in a structure (e.g. PKCS#1 encoded RSA keys). In that case ECB mode may leak data not just about the structure but also about the key.

You can still get into trouble even when wrapping AES keys as neither ECB nor CBC is an authenticated cipher. So if an attacker is able to change the encrypted value you're in trouble. Padding oracles may also apply - so don't unpad an AES-192 bit key (which uses 1.5 blocks!).

Basically you could be OK with any option you mention - but it depends on the system as a whole. I would still choose CBC with a random IV, if just to be on the safe side. That is, if the above are the only options you have, there are better alternatives (e.g. key wrapping mode - first mentioned by Louis Casillas - or SIV mode).


In RSA, is it possible to compute the private key if one knows one of the primes used to generate n? Within RSA the private key can be derived if one knows both $p$ and $q$. Is it possible to derive the RSA private key or decrypt / learn something about encrypted messages if you only know one of the prime numbers and not the modulus $n=pq$? The only available knowledge of the crypto-system is the ciphertext of a single encrypted message and the exponent ($e$) used.

EDIT: In actuality what I want to do is to retrieve the original message $m$ that was encrypted with the private key resulting from $p$ and $q$. I assumed that finding the original message would be equal in difficulty to calculating the private key.

I'll read the problem as stating we have $c$, $e$ and $p$ from some encryption $c=m^e\bmod(pq)$. But for some reason we do not have $n$ (even thought it is part of the public key, which is assumed public).

We know the order of magnitude of $q$, which likely is little above $\log_2(c)-\log_2(p)$-bit. But that's a far cry from $q$.

We can compute $d_p=e^{-1}\bmod p$, then $m_p=c^{d_p}\bmod p$ which is $m\bmod p$. Depending on context, that might let us guess $m$. For textbook RSA encryption and a narrow message (bit size of $m$ less or comparable to the bitsize of $p$), we will have $m=m_p$ or $m=m_p+k\,p$ for some small $k$, revealing $m$ or allowing to guess $k$ and $m$ if $m$ has some redundancy.

If we somewhat get the full $m$, we can compute $a=(m^e-c)/p$ and that's a multiple of $q$. If we are lucky, $a$ can be fully factored, revealing $q$. That's not entirely impossible for very small $e$ when using ECM to try to pull the factors of $a$.

If we can similarly find the full $m'$ for another $c'$, then we can compute $a'=(m'^e-c')/p$ and then compute $\gcd(a,a')$. That's a multiple of $q$, and has an excellent chance to be easy to fully factor, revealing $q$.

With $p$ and $q$, we can compute a working private key per any of the usual methods in RSA.


What is the G function of FIPS-186-2? We are trying to follow FIPS 186-2 for creating a  pseudo random number generator for EAP AKA AT_MAC Calculation in SIM Authentication:

Choose a new, secret value for the seed-key, XKEY
In hexadecimal notation let t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0. This is the initial value for H0|H1|H2|H3|H4 in the FIPS SHS [SHA-1]
Code:

For j = 0 to m - 1 do
    XSEED_j = 0 /* no optional user input */
    For i = 0 to 1 do
        XVAL = (XKEY + XSEED_j) mod 2^b
        w_i = G(t, XVAL)
        XKEY = (1 + XKEY + w_i) mod 2^b
        x_j = w_0|w_1

The algorithm requires the use of function G(t,c). We have gone through several SPECS but not found the correct definition of how to implement G(t,c).

At one place we have seen that G(t,c) is the same as SHA-1 except for some padding. But, it is not very clear. What is the G function in Implementation of FIPS-186-2 for EAP AKA AT_MAC Calculation in SIM Authentication?

The RNG used (arguably misused) as a PRF for key derivation in EAP-AKA and also EAP-SIM was defined as a small almost incidental part of FIPS 186-2 (2000) plus change notice 1 (2001). The URL in the 2006 RFCs http://csrc.nist.gov/publications/fips/fips186-2/fips186-2-change1.pdf is no longer valid, because 186-2 has been superseded by 186-3 (2009) and 186-4 (2013) and those newer versions no longer define the RNGs for digital signatures; instead they refer to a separate publication, first SP800-90 and now SP800-90A, whose focus is random generators.

However, 186-2 is still available in the CSRC archive at https://csrc.nist.gov/publications/fips/archive/fips186-2/fips186-2-change1.pdf . The original definition of two RNGs, with two applications that both involve generating numbers less than a number called 'q' (the subgroup order for the Digital Signature Algorithm DSA), is in Appendix 3 starting on page 16 (PDF page 19):

  The algorithms employ a one-way function G(t,c), where t is 160 bits, c is b bits (160 ≤ b ≤ 512) and G(t,c) is 160 bits. One way to construct G is via [a modification of] the Secure Hash Algorithm (SHA-1), as defined in the Secure Hash Standard (SHS). The 160-bit message digest output of the SHA-1 algorithm when message M is input is denoted by SHA-1(M). A second method for constructing G is to use the Data Encryption Standard (DES). The construction of G by these techniques is discussed in sections 3.3 and 3.4 of this appendix.

  3.1. ALGORITHM FOR [generating x0..m-1]
  Step 1. Choose a new, secret value for the seed-key, XKEY.
  Step 2. In hexadecimal notation let
      t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0
    This is the initial value for H0 || H1 || H2 || H3 || H4 in the SHS.
  Step 3. For j = 0 to m - 1 do
    a. XSEEDj = optional user input.
    b. XVAL = (XKEY + XSEEDj) mod 2b.
    c. xj = G(t,XVAL) mod q.
    d. XKEY = (1 + XKEY + xj) mod 2b.

However, the change notice at PDF page 71 first alters section 3.1 to:

  Step 1. Choose a new, secret value for the seed-key, XKEY .
  Step 2. In hexadecimal notation let
      t = 67452301 EFCDAB89 98BADCFE 10325476 C3D2E1F0.
    This is the initial value for H0 || H1 || H2 || H3 || H4 in the SHS [FIPS 180-1].
  Step 3. For j = 0 to m - 1 do
    3.1 XSEED j = optional user input
    3.2 For i = 0 to 1 do
      a. XVAL = (XKEY + XSEED j) mod 2b
      b. wi = G(t, XVAL ).
      c. XKEY = (1 + XKEY + wi) mod 2b .
    3.3 xj = (w0 || w1) mod q

and then adds that this algorithm can be used for 'General Purpose Random Number Generation' by removing the 'mod q' term from the computation of xj.

You can see this is now the algorithm you quote from Appendix A of rfc4187 (and Appendix B of rfc4186) except those set XSEEDj to zero (as stated in section 7 of each RFC) and change the notation because RFCs are ASCII-text (| for concatenation, ^ for superscript/exponentiation, and _ for subscript).

You want the G function based on SHA-1 specified in 3.3:

  G(t,c) may be constructed using steps (a) - (e) in section 7 of the Specifications for the Secure Hash Standard. Before executing these steps, {Hj} and M1 must be initialized as follows:

  i. Initialize the {Hj} by dividing the 160 bit value t into five 32-bit segments as follows:
              t = t0 || t1 || t2 || t3 || t4
        Then Hj = tj for j = 0 through 4.

  ii. There will be only one message block, M1, which is initialized as follows: M1 = c || 0512-b (The first b bits of M1 contain c, and the remaining (512-b) bits are set to zero). Then steps (a) through (e) of section 7 are executed, and G(t,c) is the 160 bit string represented by the five words:
      H0 || H1 || H2 || H3 || H4 at the end of step (e).

Now there's a snag. FIPS186-2, and rfc4187 and rfc4186, refer to an earlier version of the Secure Hash Standard, FIPS180-1 (1995), which has also been superseded, by 180-2 (2002,2004) 180-3 (2008) and 180-4 (2011, 2015), and as far as I can tell is NOT officially archived. But Google finds http://securityv.isu.edu/isl/fip180-1.html whose section 7 a-e are the per-block 'compression function' of SHA-1, matching the substance of 6.1.2 in newer standards though different in notation. The same logic is duplicated, perhaps a little more readably, in rfc3174 section 6.1.

The EAP RFCs specify the initial value of H (now called H(0)) is 't' which is the standard initial value for SHA-1 (section 6 in 180-1, 5.3.1 in newer versions), so this amounts to the same thing as SHA-1 for a single-block message EXCEPT WITH DIFFERENT PADDING than defined by 180.

And there's the rub. Implementations of SHA-1 you find in modern systems are almost always designed to do the standard padding, not the zero-padding you need. Unless you can get at the internals -- which will depend on exactly what implementation(s) or platform(s) you use (and that part probably does belong on Stackoverflow where the question was originally posted) -- you'll have to duplicate the code for SHA-1, with this (tiny) modification. Fortunately SHA-1 is used for so many things, and very many of them open source, this shouldn't be too hard; for one possibility, rfc4634 (which updates 3174) has C code under a license that (IMOIANAL) is equivalent to CC-BY.


Fiat-Shamir zero knowledge protocol In Fiat-Shamir protocol, the final calculation is

$$y^2=x\,v^c$$

Where $c$ is the random $\{1,0\}$, $x$ is the witness and $v$ is the public key $s^2 \bmod n$.

My questions are:

What stops the attacker from reading $c$, which is never encrypted,
   $v$ which is public and then calculate $y^2$ correctly?
How does this improve entity authentication?

Man-in-the-Middle attacks are possible for almost all zero-knowledge proofs. Victor can copy everything sent by Alice, the prover, to Bob, the verifier, and reversely to impersonate the Alice. In short, Victor can relay every message.

To mitigate this, time limit can be used to prevent the relay. However, this may not be enough.

A better solution is first creating a secure channel that is free of MitM attack and then use the Fiat-Shamir protocol.


Coppersmith's method for small public exponent Can Coppersmith's method be used to break RSA when we only have access to public key and one ciphertext?
For e.g. suppose we have N and ciphertext c both are 1024-bit numbers and the public exponent e = 5. Armed with only this information can we use Coppersmith's method to decrypt c? In all the literature that I have come across regarding this topic, either some part of plaintext is known or some bits of private key are known. But if none of this is available, is it possible to decrypt c using Coppersmith's method? If not, is there any other way to solve such a problem?
References that I went through:
https://www.cis.upenn.edu/~cis556/lattices.pdf
https://web.eecs.umich.edu/~cpeikert/lic13/lec04.pdf

If you only know the ciphertext and the public key, you should not be able to do anything, since RSA is intended to  be used that way.

However, here are some leads which may help you to recover your message (since $e$ is low):

If the same message (with the same padding!) have been sent to $e$ different people (hence encrypted with $e$ different public key), you can recover the message using the Chinese Remainder Theroem. This is known as Hastad's broadcast attack.
If the message is short and not padded, you may be able to recover the message simply by taking the $e^{th}$ root of the ciphertext. Note that it can only work if $m^e < n$.

In a more general way, I invite you to take a look at Dan Boneh's "Twenty Years of Attacks on the RSA Cryptosystem" namely the section about low public exponent.


Why is elliptic curve parameter $a=-3$ somehow special Considering the equation of the elliptic curves over $GF(p)$

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

why is there some magic in using $a=-3$ ? In some well known curves (e.g. P-256) only $b$ is specified, while $a$ ist taken as $-3$. In a software library I use, $-3$ is the default value, what means, that is assumes $a=-3$ if not otherwise specified.

Why is $a=-3$ special?

The reason is that choosing $a=-3$ allows for a more efficient computation of the doubling operation, when used in projective coordinates.

In fact if you look at the doubling formula in, for example, Jacobian coordinates from wikibooks you can see that it requires the computation of an intermediate value as $M = 3*X^2 + a*Z^4$, where $(X,Y,Z)$ is the Jacobian representation of the affine point $(x,y)$ through the relation $(x,y) = (X/Z^2,Y/Z^3)$.

That formula to compute $M$ can be simplified to $M = 3*(X + Z^2)*(X - Z^2)$ exchanging the computation of two squares $X^2$ and $(Z^2)^2$ with the multiplication $(X + Z^2)*(X - Z^2)$ and, of course, you also avoided the multiplication by $a$.

This results in a more efficient computation of the doubling formula and works well even in homegeneous or Chudnovsky coordinates.


Provable security of cryptographic hash functions I am working on the following exercise question:

Consider the following construction of a “keyed” hash function from Katz & Lindell (ex. 7.22 (1st ed.)/ 8.21(2nd ed.)).
Gen : On input $1^n$ , generate a cyclic group $\mathcal{G}$ of order $q$, where $q$ is an $n$-bit prime, and a generator $h_1$. Then select $h_2, \ldots , h_t \leftarrow \mathcal{G}$. Output $s := (\mathcal{G}, q,(h_1, \ldots, h_t))$ as the key.
H : Given a key $s$ and input $x_1, \ldots , x_t$ where $x_i \in \mathbb{Z}/q\mathbb{Z}$, output $H_s(x_1, \ldots , x_t) := \Pi_i\, h_i x_i$
a) Let $\pi$ be a permutation of the integers $1, \ldots , t$. Prove that no adversary $A$, even knowing $\pi$, can distinguish between $(h_1, \ldots , h_t)$ and $(h_{\pi(1)}, \ldots , h_{\pi(t)} )$ with better than negligible probability. Give a formal description of this statement as an experiment before completing the proof.
b) Prove that if Gen produces groups $\mathcal{G}$ where the discrete logarithm problem is hard, then $H_s$ is collision resistant.

a) For this part I can intuitively see that since picking numbers from random in a cyclic group are no different than a permutation,I am not sure how to formulate it.
b) how can you break the discrete logarithm problem if you find a collision in such a scheme?

First this, a nit about the hash function: one can trivially create a collision by appending a 0 value; an appended 0 does not change the hash value, and hence that produces a collision.

If we say that collisions are required to have at least one place there two colliding messages differ with at least one having a nonzero value, then we can show it.  Here is how, given a black box which finds a collision, can perform discrete logs (with good probability).

Suppose we have the elements $G$ and $H$, and which to find the value $k = log_G H$, that is, the solution to $kG = H$.

What we do is select $h_i = r_i G + s_i H$, where $r_i, s_i$ are random values.  Then, present these $h_i$ values (along with the rest of the parameters) to the black box.

The black box will produce a collision, that is, two messages $m, m'$ with $\sum m_i h_i = \sum m'_i h_i$.  Rewriting this, we get $(\sum (m_i - m'_i)r_i)G + (\sum (m_i - m'_i)s_i) H = 0$, or $aG + bH = 0$, for values $a, b$ which we can compute (as we know the $m_i, m'_i, r_i, s_i$ values)

As the $r_i, s_i$ parameters are random values unknown to the blackbox (and at least one of the $m_i - m'_i$ values will be nonzero), it is unlikely that $b$ will be 0; if it is not, then we have $k = -ab^{-1}$


Is there an encyption scheme that combines additive homomorphism with ability to proxy re-encrypt? Is there an encyption scheme that combines additive homomorphism with ability to proxy re-encrypt? I've tried digging around on the Internet but haven't found anything conclusive on the topic.

The schemes by AFGH in this paper are pairing based ElGamal type non-interactive, single-use (single-hop) and unidirectional IND-CPA secure proxy re-encryption schemes.

Although by their construction they are multiplicatively homomorphic (the authors do not mention it in the paper, but it works analogously to ElGamal), you can use the same trick as in "exponential ElGamal" to make them additively homomorphic.

This means that you represent the message $m$ to be encrypted as power of the generator $g$ of the target group ($G_2$ in their paper), i.e., as $g^m$ for messages in $Z_p$ (with $p$ being the order of the prime order group). Then, you are, however, limited to "small" message spaces as decrypting involves computing discrete logs in $G_2$. I do not know your application, but in many scenarios that should be sufficient.

As far as I know it has never been used in this context and there are no papers I am aware of that use additively homomorphic proxy re-encryption.

There may also be other schemes (as the one from INDOCRYPT 2013 pointed out by xagawa - however, this scheme is multi-hop - which may render it impractical for some applications but may allow others not feasible with one-hop schemes), but this one should be a good starting point. As already stated by Reid, Gentry's scheme can also be used for that, but fully homomorphic encryption schemes are not yet practically efficient.


How are the points in an elliptic curve over the finite field calculated? For the elliptic curve with equation $y^2 = x^3 + x + 0 \pmod{13}$ in the finite field, how are all the points in this curve calculated. See the image below for an example created via https://graui.de/code/elliptic2/.

The above images shows 20 points. How are the coordinates of these points calculated?

Given
$$
y^2 = x^3 + x \pmod{13}\quad (1)
$$
note that in addition to the point at infinity, the other points are the solutions $(x,y) \in \mathbb{F}_{13}\times  \mathbb{F}_{13}$ of (1). With algebraic construction we add the point of infinity ($\{\mathcal O\}$) to the set of the solutions $$E := \{ (x, y) \in (\mathbb{F}_{13})^2 \mid y^2 = x^3 + x \} \cup \{\mathcal O\}.$$
Since you need to solve (1) for $y^2$ this implies that whenever $(x,y)$ is a solution so is $(x,-y).$ For a small field like this list the squares
$$\begin{array}{c|ccccccc}\hline
y & 0 & \pm 1 & \pm 2 & \pm 3 & \pm 4 & \pm 5
&\pm 6\\ \hline
y^2 & 0 & 1 & 4 & 9 & 3 & 12 & 10\\ \hline
\end{array}$$
and note that everything must be reduced mod 13. So $-4$ is actually $9.$
Now, whenever $x^3+x$ is equal to $y^2$ we pick up $(x,y),(x,-y)$ as points on the curve. So now prepare the table
$$\begin{array}{c|ccccccccccccccc}\hline
x & 0 & 1 & 2 & 3 & 4 & 5 & 6 &7 &8 &9 &10 &11 &12\\ \hline
x^3 & 0 & 1 & 8 & 1 & 12 & 8& 8& 5& 5& 1& 12& 5&
12\\ \hline
x^3+x & 0^* & 2 & 10^* & 4^* & 3^* & 0^* & 1^* & 12 & 0^*& 10^*&  9& 3^* & 11\\ \hline
\end{array}$$
and use the values of $x$ corresponding to the marked points to get the points
$$E=\{ (0,0),(2,\pm 6),(3,\pm 2),(4,\pm 4),(5,0),
(6,\pm 1),(8,0),(9,\pm 6),(11,\pm 4)\}
$$
on the elliptic curve, in addition to the point at infinity, which is the additive identity.


Why do we need Collision Resistant Hash Function for the Merkle Tree Signature Scheme? I am studying Merkle Tree Construction for digital signature. I don't quite understand why we need collision resistant hash function for Merkle tree construction.

There are few papers like XMSS that try to lower the requirement from collision resistant hash function to second-preimage hash function by introducing bit mask. However, does it implies longer public key, more works need to be done on verifier side?

is there a known attack on traditional Merkle tree that only uses second preimage resistant hash function?

There are few papers like XMSS that try to lower the requirement from collision resistant hash function to second-preimage hash function by introducing bit mask.

Actually, that's not why XMSS has the bit masks; as you point out, second preimage resistance is essentially all you need for hash based signatures to be secure; the attacker needs to find a preimage or a second preimage (depending on where in the hash scheme we're talking about) for one of a number of hashes.

Rather, it has to do with proof technique.  As mephisto points out, if you're happy with the random oracle model (and its proof method), it's straightforward to design a simple HBS method that is secure (that is, you have to find a preimage or second preimage to break).

However, what XMSS tries to do is be secure in the concrete model; that is, they try to argue that, because the bitmasks randomize the input, that what you need to do is find a (second) preimage of an effectively random string.


Decrypt affine cipher given encryption key i have a ciphertext C=TLNJG formed using the equation
c=(7p+11) mod 27,c equivalent to numerical equivalent character of ciphertext and p the plaintext
how do i get the plaintext back?
for encryption:c=(7p+11) mod 27
for decryption:p=5(c-11) mod 27
let's say i encrypt the letter B(1) I would get

c=(7+11) mod 27
c=18 mod 27=18 (letter S)

but if I do decryption using the decryption equation of the letter S I will get the letter I instead of B.Why?

p=5(18-11) mod 27
p=35 mod 27=8(letter i)

Your formulas are wrong. If $$c \equiv 7p + 11 \mod{27}$$ then by applying the modular arithmetic function $$c - 11 \equiv 7 p  \mod{27}$$ and then $$(c - 11) \times 7^{-1} \equiv p  \mod{27}$$.

Therefore, the decryption function is:
$$p \equiv (c - 11) \times 7^{-1} \mod{27}$$

For this we need to compute de multiplicative inverse of 7 modulo 27. Since they are coprime number, this inverse exists. And we can compute it using the Euler totient method like this:

$$7 ^{-1} \equiv 7 ^{\phi(27) -1}  \mod{27}$$

$$\phi(27) = 27 \times (1 - \frac{1}{3}) = 18$$
then
$$ 7^{-1} \equiv 7^{17} \equiv 4  \mod{27}$$

Finally the decode function is :

$$p \equiv (c - 11) \times 4$$

For your example:

$$(18 - 11) \times 4 \equiv 7 \times 4 \equiv 28 \equiv 1  \mod{27}$$


Does AES-CBC always use PKCS#7? I need to add AES decryption with a 256 bit key to our software, and of course I won't do it myself; rather, I chose a library that works fine for our needs. It supports various modes of operation, the one I need is CBC (I know GCM would be preferable, but we get data from older hardware, and this is what it uses. The hardware will get an update in a few years...).

However, the library always (like, there is no way to change it, it is hardcoded in the encryption and decryption routines) uses PKSC#7 for padding. Does AES-CBC always use this padding, or is it just a shortcut by the library because PKCS#7 is so ubiquitous with this algorithm that it has become a de-facto standard, and it is not conceivable to use anything else at this point?

Does AES-CBC always use PKCS#7 padding?

No. Other common or plausible paddings include

No padding, where the plaintext's length is known to be a multiple of 16 bytes.
Bit padding, where the plaintext is considered a bit stream, it is appended a bit at 1, then 0 to 127 bits at 0 to reach a block boundary. With big-endian bytes, that's appending a byte at 0x80 then 0 to 15 byte(s) at 0x00.
Zero padding (same as above without the initial 1), suitable when what uses the the plaintext is known to ignore extra zero bits, as is often the case for compressed audio/video/image.

Among paddings I have heard of in the past (but never consciously met in combination with AES), there are ESP padding and CipherText Stealing. Others know more.

An AES-CBC library can be used to obtain encryption with no padding, even if it is hardwired for one particular, by submitting plaintext of length multiple of the block size and removing the last block of ciphertext.

Such library with hardwired padding can also be coerced to ignore the padding on decryption. That's easy if the library is designed for on-the-fly decryption: just don't tell it that the end of input is reached. Otherwise, an option is to use the library in encryption mode to encipher an empty plaintext with the same key, take the 32-byte resulting ciphertext $C'_0\mathbin\|C'_1$ (where $C'_0$ is the IV, zero will do) then after the last block $C_k$ of the actual ciphertext append an extra block $C_k\oplus C'_0\oplus C'_1$ before using the library for decryption. This will insure that the padding check passes, and yield a deciphered plaintext as with no padding.

And on top of encryption or decryption with no padding, it is easy to build any padding.


why $e(g,g)^N=1$ in bilinear pairings holds? I can't get the point of prime order bilinear pairings:$\mathbb{G}\times\mathbb{G}\rightarrow\mathbb{G}_T$,$g=$ generator of $\mathbb{G}$ , $N=p*q$, $p$ and $q$ primes and $e(g,g)^N=1$. why $e(g,g)^N=1$ holds? Why is it 1?

If $N$ is the order of the group $\mathbb{G}_T$, then for any element $x \in \mathbb{G}_T$ we have that $x^N = 1$. This follows from the Lagrange theorem. Since $e(g,g) \in \mathbb{G}_T$, the same applies to it.


Can error correction and detection be done without adding extra bits? I have gone through error detection and correction techniques like Hamming codes, and BCH codes require extra parity bits for detection and correction. While sending data, we always seem to introduce error correction by adding parity and use parity while checking for errors.

Can error detection and correction be done without adding any extra bits?

In general, no. Let us say you have a data vector $x$ of $k$ bits and one bit is flipped by an error. There is no way of detecting, let alone correcting this, unless the errored data vector $x'$ is not another valid data vector.

If the errored vector $x'$ is not a valid data vector and you can do detection, then all $k$ bits cannot be used as arbitrary data bits, thus your data rate is less than $k$ bits, implying you are using parity in some sense.

More simply, if there are no parity bits, all $2^k$ data vectors are valid, and thus all errors result in another valid data vector, making all errors undetectable.

Since correction is harder than detection, the same argument rules out correction as well.You can't correct if you can't detect.


Why do look up tables speed things up compared to brute force? I'm currently reading up on lookup tables and efficiency. In my uni script it says the following:

For Brute Force:

Preparation time: $O(1)$
Disk space requirement: $O(1)$
Time required to crack the password: $O(2^n)$

Full lookup table:

Preparation time: $O(2^n)$
Disk space requirement: $O(2^n)$
Time required to crack the password: $O(1)$

I'm not sure I'm understanding this correctly.

As far as I understand, for Brute Force:

$O(1)$ is the time required to look up the password in my table of all possible passwords.
The disk space requirement is simply as large as needed for a list of all possible passwords, so $O(1)$ as well

My questions:

Why is the time needed to crack the password $O(2^n)$? How is it determined?

It seems I don't understand the concept of a lookup table either. As far as I see, a lookup table will simply hash the full list of possible passwords (so required disk space is larger) but what then? Why is the cracking of the password per se faster?

I think I'm missing something crucial here. Any help will be appreciated.

Suppose you have an $n$-bit key. Suppose further you have some reliable predicate $P(k,m)$ which decides whether a key $k$ is the key you are looking for given the reference $m$. Furthermore, suppose you have a "successor" function $F$, that takes a key and returns you the "next" key so that eventually all keys are traversed.

Now what a brute-force attack does is, given $m$, it takes a starting key $k$, evaluates $P(k,m)$ if it returns false, sets $k\gets F(k)$. This will take $\mathcal O(2^n)$ evaluations of $P$ and $F$. Assuming both can be computed in $\mathcal O(1)$ the entire calculation takes $\mathcal O(2^n)$.

Now for the look-up table. For this you simply start at some key $k$, and store the $m$ such that $P(k,m)$ yields true as a pair $(m,k)$ in a giant array (or hashmap). Now you repeat this with $F(k)$. When you then get a concrete $m$, you simply look it up in the table and find the corresponding $k$. For hashmaps and continuous arrays, this takes time $\mathcal O(1)$ (ie the lookup time is independent of the number of elements). Clearly, you need storage for all the $2^n$ pairs of $(m,k)$. Now the preparation time assumes that you can find $m$ such that $P(k,m)$ is true, but this is usually possible in constant time, e.g. by evaluating a hash function or an encryption cipher.


Re-using information from the first factor for the second factor Is it safe to re-use my username and password as information for the 2nd-factor?

For instance:

the first factor is the username and password;
the second factor is $H(H(username) \oplus H(password \| SK))$ where $SK$ is the private key.

Would this scheme be secure?

As originally described, the system of having the two factors be [password, H(username || password)] is no more secure than the password alone.

The intent of Two-Factor Authentication is that you are improving security by requiring two independent factors for authentication. In the proposed model your second factor is fundamentally the same as the first. Assuming the hash function is publicly known as part of the protocol, then once your password is compromised then both factors are compromised.

Adding a key to the hash (i.e. a keyed hash) could potentially improve security depending on how that key was generated/shared. You would need to describe the whole system of course.

Nevertheless, There are a number of rigorously analyzed 2FA methods. Something like a TOTP token or U2F hardware key does add significant independent security to a password. You would be well served to investigate existing constructions and analysis.


Is AES (or DES) provably secure? What is the hardness assumption underlying these cryptosystems? I have taken a course in applied Cryptography. I do not understand the hardness problem underlying AES (or DES).

As in RSA is based on the RSA assumption. ElGamal is based on the hardness of descrete logarithm problem. Most of the lattice crypto is based on the LWE assumption which itself is based on the hardness of BDD problem. What is the hardness problem that guaranties the security of AES? (Or DES)

In other words if there is an oracle R that can break AES. Can I use this oracle as a subroutine to solve some really hard problem? If yes, what is the reduction?

No, there is no reduction from AES to any well-known hardness assumption; in other words, the hypothesis that AES is secure is an assumption by itself.

In fact, this is the case for every practical symmetric cipher that you can think off; provable constructions from a one-way function would be completely impractical.


How to properly cypher 16 bytes message containing a CRC checksum? This question arose from a new context under early developments. If cryptographic operations are not well chosen or badly sequenced, please do notice it along your answer or comments: I am a layman in cryptography. If you think this post should be improved, any constructive feedbacks are welcome, I am new to this stack.

Imagine I have an IoT sensor that needs to send few bytes of data over a wireless network. The physical payload from sensors is about 11 bytes, then we would like to construct from this a network payload as this:

Pad physical payload to 12 bytes;
Compute checksum using CRC32 and append to padded physical payload;
Encrypt 16 bytes with a cryptographic algorithm such AES with CBC mode.

Provided it is a good idea to proceed as stated above: How must I setup the cryptographic part to make it robust, mainly:

Is this cryptographic standard relevant for this kind of task?
How do I chose the key size?
How do I chose the Block size?

Last but not least, is it known if: Does CRC32 stored in a message reduce the strength of the cryptography as it introduces a relationship among bits in the message?

Is this cryptographic standard relevant for this kind of task?

Yes to a degree, but with what's in the description (and assuming the CRC is checked after AES-CBC decryption)

There is no protection against replay of earlier captured messages. The usual options to protect from replay are a two-way protocol where the receiver generates a nounce made part of the message carrying sensor data, or/and a sequence counter maintained by the sender (but only the former solution insures freshness).
This is symmetric crypto, hence the sender is bound to contain a secret that allows decryption, and the receiver is bound to contain a secret that allows forgery of information. Both issues can be fixed by asymmetric crypto.
CRC-then-encrypt in general does not give integrity protection, and if encryption was with a stream cipher or the common AES-CTR, it would be trivial to alter the data in real time. The use of CBC encryption happens to save the day (because AES encryption of one block is not malleable), but that's a lucky choice more than by design. And if the message was larger than 12+4 bytes and thus did not fit a single AES block, I would not bet the house that there is no cryptanalytic attack on the integrity protection.
The integrity protection is only 32-bit. An adversary submitting 1000 random ciphertexts per second to each of 1000 receiving systems will sneak one thru the decryption and CRC check more often than once in 1h 15' ($2^{32}/10^6$ s) on average.

The academic solution to 3 and 4 is authenticated encryption, designed for both confidentiality and integrity. One of the most well-known is AES-GCM. It is improved in AES-GCM-SIV.

  How do I chose the key size?

There are three for AES: 128, 192 or 256-bit. They are safe/fastest, safer/faster, or safest/fast. In the context, AES-128 is technically sufficient, because the real threat is that the key somewhat leaks (gets extracted from either the receiver or sensor). AES-256 looks better on the spec sheet, likely is fast enough, and I do not see that it can make key extraction easier; so why not?

  How do I chose the Block size?

You did: AES can only be used with 16-byte block.

With AES-CBC (if kept against my recommendation of authenticated encryption) one choice you have is the padding mode, and the best is "no padding", since any padding will cause an extra 16 bytes of ciphertext.

Other, much harder things to determine for a real system are:

how the Initialisation Vector for encryption is generated;
how the keys are drawn;
how they are injected in the devices that need them;
how key leak is made unlikely;
how keys are rotated (changed, periodically or to recover from a suspected leak).

  Does CRC32 stored in a message reduce the strength of the cryptography as it introduces a relationship among bits in the message?

No, unless there was an exploitable weakness of AES iself, which can be discounted. Modern ciphers are designed to safely encrypt known plaintext, and thus are safe for redundant plaintext.


Security of AES in CTR mode with fixed nonce (but different key) If I am using AES in CTR mode and use a unique key every time but the same nonce, is this secure?

If so, does it make a difference if the nonce is public?

Yes, if you use a different key for each message, then it's secure, and it's not a problem if you use a public (or fixed) nonce.

One example where this comes up is the Integrated Encryption Scheme, which uses a symmetric system to encrypt the actual message, and which internally generates a key that will be used only for that message.  Note that in IES, you'll also need to implement integrity protection as well (e.g. a MAC)


Does applying a "PushEntropy"-function increase security of a private key? I was just reviewing the source-code of the NBitcoin-package. As far as i can see when you create a new bitcoin-keypair
Key privateKey = new Key();
(without passing some random data to be used as private key generated by yourself) then the library generates a private key using a random-number-generator for you. Very usual. But then i stumbled across the fact that the output of the random-number-generator will not directly be used as private key: NBitcoin also applies a PushEntropy-function on this byte-array:
private static void PushEntropy(byte[] data)
{
    if (!UseAdditionalEntropy || additionalEntropy == null || data.Length == 0)
        return;
    int pos = entropyIndex;
    var entropy = additionalEntropy;
    for (int i = 0; i < data.Length; i++)
    {
        data[i] ^= entropy[pos % 32];
        pos++;
    }
    entropy = Hashes.SHA256(data);
    for (int i = 0; i < data.Length; i++)
    {
        data[i] ^= entropy[pos % 32];
        pos++;
    }
    entropyIndex = pos % 32;
}

I understand what this function does, but I do not understand why we need this function to generate a private-key.
Why is a cryptographically secure random-number-generator (to generate the private key aka data-bytearray) not enough?
Does this function increase security in any kind?

Why is a cryptographically secure random-number-generator (to generate the private key aka data-bytearray) not enough?

A Cryptographically Secure True Random Number Generator would be enough. This code uses a belt-and-suspenders approach. This is common in RNGs, in recognition of the fact that RNGs are traditionally one of the most brittle components in crypto implementations (see e.g.SmartFacts).
The intention appears to be: if UseAdditionalEntropy is at it's default of true, and additionalEntropy has been set with something unguessable or/and truly random by calling one of two forms of AddEntropy

Try to save the day if initially data contains something guessable, by mixing the two (in the first loop)
Make it hard to "walk back" from the result, by applying a non-reversible transformation. When data is 32-byte and entropyIndex starts at zero, this transformation is $\mathtt{data}\mapsto\operatorname{SHA-256}(\mathtt{data})\oplus\mathtt{data}$. Given the output, the only hope to find the input is by enumeration of likely input values¹.

Step 1 can conceivably backfire, e.g. if data passed is the SHA-256 hash of what was previously passed to AddEntropy.
Step 2 slightly reduces the entropy (by less than 1 bit if data was full-entropy, see this; and negligibly so if data was less than full-entropy), but in the context that's fine.

Does this function increase security in any kind?

It does, if Random.GetBytes of the calling context has a flaw, and AddEntropy was used and passed something secret (including something random and independent of what Random.GetBytes outputs; or just a secret constant generated at random at time of installation). As long as PushEntropy,  additionalEntropy and entropyIndex remain private (thus not accidentally callable), this precaution is unlikely to accidentally backfire.

¹ If we changed += to ^= in the final mixing step of the round function of SHA-256, this transformation would be reversible. And it would be dangerously close to reversible if we changed ^= to -= in the code shown.


How can we define division operation by using Fully homomorphic encryption Last fews months, I'm working with homomorphic encryption. Now I am dealing with some computational problems with integers or real-numbers (like arithmetic mean, standard deviation) where division is necessary in homomorphic domain. Is there any practical solution of homomorphic division? I'm also looking for practical example.

In case some assistance from plaintext holder is available:
(1) choose a random, multiply it with the plaintext and also homomoprhic-encrypt the random;
(2) calculate inverse of the product in clear (no encryption);
(3) multiply encrypted random by the inverse.
This is not exactly division, still it outputs the inverse.


Multiple rounds of (Committed) Oblivious Transfer I would like to know a protocol which computes the following functionality:

Alice chooses a bit b.
For i = 1 to n, Bob chooses $x^i_0$ and $x^i_1$.
For i = 1 to n, Alice and Bob run $F_{OT}$ with Alice, acting as a receiver, inputting b and Bob, acting as a sender, inputting $x^i_0$ and $x^i_1$, resulting in Alice receiving $x^1_b, x^2_b, ..., x^n_b$.
(optional functionality) For any i in 1 to n, Bob can decide to reveal $x^i_0$ and $x^i_1$ at a later point.

It is important that Alice cannot change the chosen bit b between $F_{OT}$ interactions. Is that possible? Do Commited Oblivious Transfer help? If so, why?

The most straightward approach is to have Bob select two random symmetric keys $k_0$ and $k_1$ and have Bob publish $Encrypt_{k_0}( x_0^i )$ and $Encrypt_{k_1}( x_1^i)$.

Then, Bob does an OT with Alice, allowing Alice to select between $k_0$ or $k_1$.

She learns $k_b$, and then is able to decrypt all the $Encrypt_{k_b}( x_b^i )$ values, resulting in her learning $x_b^1, x_b^2, …, x_b^n$

Because she learns only one of $k_0, k_1$, the value she learns all come from the same half.


Extracting randomness from highly-biased RNG I have a source with a very low entropy (like 3 entropy bits per 1024 source bits). But I need to construct a 128 bit seed from the source.

Will it be helpful to XOR 350 bits with jump 128 bits, e.g. $n_0\oplus n_{128}\oplus\dots\oplus n_{128*350}$ or maybe some more times?

EDIT:
The source is SRAM so the bits are fairly independent.
Distribution of min-entropy is on the histogram. The first bar is like 500 bits, but the others are much lower so I cut the first one.

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

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

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

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

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

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

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

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

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

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

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

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


Hill-cipher, disordered alphabet I am going to apply a simple substitution cipher to my input, then encrypt the result with a Hill cipher.  How can this be broken, in a chosen-plaintext threat model?

In other words, instead of the standard mapping of letters to numbers (A=0, B=1, .., Z=25), I will randomly reorder them (e.g., A=22, B=12, ...), where the particular bijection between letters and numbers is part of the key.  Then, I'll encrypt the result using a Hill cipher.  So far I've been using a Hill cipher with a $2\times 2$ matrix, but I'd also be interested in the answer for a general $n \times n$ matrix.

This can be broken. The exact nature of the attack will depend what modulus you use for the Hill cipher: are you working modulo a prime number, or working modulo 26?

Working modulo a prime $p$

A simple attack, with no fancy mathematics needed.  One simple attack is to start by requesting the encryption of the 26 messages AAAA, BBBB, CCCC, DDDD, ..., ZZZZ.

Note that after simple substitution, the message AAAA will become the 4-vector $(a,a,a,a)$ for some number $a$, and then we'll encrypt this by multiplying the vector $(a,a,a,a)$ with a matrix that is the Hill cipher's secret key.  Similarly, the message BBBB will become $(b,b,b,b)$ and then will get multiplied by the same matrix.  Since every number has an inverse modulo $p$, there's some constant $c$ such that $b=a \times c \pmod p$ (namely, $c = b a^{-1} \pmod p$).  This means that $(b,b,b,b)$ is a constant $c$ times the vector $(a,a,a,a)$.  Consequently, the Hill-cipher-encryption of $(b,b,b,b)$ will be a constant $c$ times the Hill-cipher-encryption of the vector $(a,a,a,a)$.

Guess what number A maps to; say A maps to the number $a$.  Then each other ciphertext will be a constant multiple of the ciphertext for AAAA, and that constant will reveal what the corresponding letter maps to.  For instance, suppose each number in the ciphertext for BBBB is 9 times the corresponding number in the ciphertext for AAAA; then we know that B maps to $9a \pmod p$.  (In general, it is guaranteed that there will always be some constant we can substitute in place of 9.)  Thus, if we guess correctly what number A maps to, then we will learn what number each other letter maps to.

Now apply a standard attack for defeating the Hill cipher.  You'll repeat this $p$ times, once per guess at the number that A maps to.  You can confirm whether the guess was right, by confirming whether you have successfully broken the Hill cipher and can decrypt the ciphertexts to meaningful-looking plaintext.  One of your 26 guesses will lead to correct-looking plaintext; that's the right guess, and now you're done.

Working modulo 26

A simple attack, with no fancy mathematics needed.
We can generalize the above attack so that it also works if we're working modulo 26.  Now we have to deal with the fact that not all numbers have an inverse modulo 26.

As before, we start by requesting the encryption of the 26 messages AAAA, BBBB, CCCC, DDDD, ..., ZZZZ.  One of those will encrypt to the all-zeros ciphertext; say it is the message QQQQ.  Then you have learned that Q maps to 0.

Another of those ciphertexts will contain only the numbers 0 and 13; say it is the message DDDD that encrypted to this.  Then you have learned that D maps to 13.

Now you can apply a similar attack, by guessing which number A maps to, and then applying similar reasoning.

A fancier attack

There's a more sophisticated way you can attack this, by using some fancier mathematics.  Introduce 26 unknowns $x_A, x_B, \dots,x_Z$.  Here $x_A$ represents the number that A maps to, $x_B$ represents the number that B maps to, etc.  We don't know a priori what these numbers are; that's why they are unknowns (variables).

Also, let the $n\times n$ matrix $M$ denote the Hill cipher matrix used for encrypting $n$-letter messages.  We can think of each of the $n^2$ entries of $M$ as another unknown; i.e., $M_{i,j}$ is an unknown, for each $i,j$.

Now each known plaintext-ciphertext pair gives us a system of equations on these unknowns.  For instance, suppose the message WINK encrypts to the ciphertext $(17,5,20,2)$.  Then we learn the following equation:

$$M (x_W, x_I, x_N, x_K) = (17,5,20,2).$$

Why?  Because after simple substitution, WINK becomes the column vector $(x_W, x_I, x_N, x_K)$.  The Hill-cipher-encipherment then multiplies this by the matrix $M$.  We know what the resulting ciphertext is.

Notice that this is a system of $n$ equations in $n^2+26$ unknowns.  Sadly, they are not linear equations; they are quadratic equations.  Nonetheless, there are techniques known for solving a system of quadratic equations.  We can expect that once we obtain a bit more than $n^2+26$ equations in $n^2+26$, there will be a unique solution.  There are techniques (e.g., relinearization) for computing this unique solution, when the number of equations is large enough.
For instance, if we have at least $(n^2+26)^2$ quadratic equations in $n^2+26$ unknowns, simple relinearization will find us the value of all of those unknowns using $O(n^{12})$ time.  This number of equations can be gathered after observing $(n^2+26)^2/n$ known plaintext-ciphertext pairs.

Getting even fancier

Hey, why stop there?  We can actually solve this purely with linear algebra.

Notice that we can rewrite the previous equation as

$$(x_W, x_I, x_N, x_K) = M^{-1} (17,5,20,2).$$

So now let's choose a slightly different set of unknowns: the unknowns are $x_A, x_B, \dots,x_Z$ (this part is the same as before) and the entries of $M^{-1}$, i.e., $(M^{-1})_{i,j}$ for each $i,j$ (this part is different).  There are still $n^2+26$ unknowns.

With this change, each known plaintext-ciphertext pair gives us $n$ linear equations in $n^2+26$ unknowns.  Now the equations are linear, so they are even easier
to solve.  Once we've obtained a bit more than $n^2+26$ equations, there should be a unique solution, and it can be found using Gaussian elimination in $O(n^6)$ time.  So, if we can gather a bit over $(n^2+26)/n$ known plaintext-ciphertext pairs, we can break the cipher using linear algebra.   Cool, eh?


"Signing" with public key For this question, the following caveats and assumptions hold:

There exists a 2048-bit RSA key pair used exclusively for signing/verification
The private key is kept completely private
There exists a group of users who have the public key
There is a group shared password
I (mostly) understand the functional difference between encryption/decryption and signing/verification for RSA, but not the specific math differences
I am aware of hashing

Given the Following Operation

"ciphertext" = RSA_sign( public_key, random salt + password )

What are the security implications if using PKCS#1 old-style v1.5 padding?

Obviously, this is not the accepted way of doing things -- one does not sign with a public key.  Basically, the end result is a deterministic "encryption" of the password which can ultimately be compared among the members of the group.  That is, because there is no randomization of the padding, each member can perform the same procedure and arrive at a comparable result.  So member A and member B (neither of which have the private key) can perform this operation (as long as they have the salt) and determine that the password is the same.  (Hashing, of course, would be a much better solution.)

The above scenario is susceptible to known plaintext attacks.  eg. Similar to a hash, a malicious user can attempt to brute-force the password by simply trying combinations until they get a comparable result (the salt is, for all intents and purposes, public knowledge).

Is the private key at risk (I don't believe it is)?
Is this weaker than a hash such as SHA1?

UPDATE: After thinking about the relative security of this "RSA-hashing" mechanism to SHA1 for collisions, I realize that there would be an increased chance if msg.len > RSA.n.

(Please don't tell me to just use hashing. This is not the point of the question.  I have seen questions asking if it's okay to "encrypt" using the private key which is a clear security problem, but I've never seen an answer to the question of signing with the public key.)

Actually, if everyone uses a different salt whenever they "sign", and if the RSA_sign operation doesn't involve a hash (in general, real signature operations do, I don't know about your variant), it turns out not to be secure, and in fact, the password can be recovered fairly easily if the attacker hears enough signatures based on the same password.

Here's how it works: when someone signs the password, what they effectively do is take their password, apply the PKCS #1.5 padding to it, forming a message $M$.  Then, they select a salt $A_i$, compute the 'signature' $S_i = (M + kA_i)^e \bmod N$, and publish the pair $A_i, S_i$ (where the value of $k$ depends on exactly how you combine the password and the salt; whether it does addition or bitwise concatination; we'll assume that the attacker can guess that).  Now, this may not be the order that the signer actually implements things, but as long as the results are the same, that doesn't matter.

Now, suppose the attacker can get $e$ different such pairs $(A_i, S_i)$, and he wants to recover the common $M$ value.  What he can do is binomially expand each such pair as:

$M^e + \binom{e}{1}kS_iM^{e-1} + \binom{e}{2}k^2S_i^2M^{e-2} + \ldots + \binom{e}{e-1}k^{e-1}S_i^{e-1}M + k^eS_i^e = A_i \mod N$

Now, the attacker knows all the above values except for $M$.  So, he can then treat these equations as $e$ linear equations in the $e$ variables $M^e, M^{e-1}, \ldots, M$ within the ring $\mathbb{Z}/N$, and find the solution for $M$, recovering the password.

Now, there are several obvious ways to break up this attack:

Use a huge public exponent $e$
Combine the password and the salt in a nonlinear way (for example, by hashing them together)

On the other hand, the existence of this attack demonstrates that you really should think twice before trying it.


How do I generate a challenge for elliptic curve signing using NIST standards? Basically, NIST FIPS 186-4 describes a standard for generating some message that will be signed by an elliptic curve private key. However, I'm having difficulty interpreting how this message should look.

To give more context, with RSA, I've been attempting to follow PKCS #1 v1.5, so I'm basically doing pad(sha1(crypto.randomBytes(256)), which I believe creates a sufficiently random challenge of appropriate length in the case of RSA. (If I'm wrong here, please let me know that as well).

What are the discrete steps in the case of ECC? (I'm trying to follow B.5.1 Per-Message Secret Number Generation Using Extra Random Bits and B.5.2 Per-Message Secret Number Generation by Testing Candidates of the publication above).

  In this method, a random number is obtained and tested to determine that it will produce a value of k in the correct range. If k is out-of-range, another random number is obtained (i.e., the process is iterated until an acceptable value of k is obtained.

So in plain English looking at the publication, it appears I do the following to create a challenge, k:

Find the bit length N of the public key
Generate a string of N random bits
Convert the string of random bits to a non-negative integer c (using the method for bit-to-string conversion in the same publication)
If c is greater than n-2, start over...
k = c + 1

Make sure k and the inverse of k are within the limits [1, n–1].

However, there doesn't seem to be any hashing going on. In the context of RSA, I've been reading you should always hash this random bit string before signing it (and of course, we must pad it appropriately so the message is the correct size). Am I missing something in the case of ECC? (Of course, I could theoretically just send any random message to be signed, but I want to follow some standard for the challenge, and it looks like NIST is the way to go...)

I believe you're misunderstanding how ECDSA works.

When you sign a message with RSA, you pad out the message somehow; some padding methods are determanistic, and some are randomized.  However, once you get this padded message, you present it to the underlying RSA private operation, which is entirely determanistic.

However, ECDSA isn't like that.  Instead, the ECDSA private operation selects a value k; this value k is not the message being signed, instead it's a random value (and there are known attacks that can occur if it's biased; that's why FIPS 186 goes into such detail about exactly how you do it - if you ignore their advice without knowing what you're doing, well, there be dragons here).

Now, once you have the value k, you can take the message (actually, the hash of the message), and then present that to the ECDSA signature operation to generate the signature.

So, with ECDSA, there is a hash involved; however it's the message that is hashed, not k.


Are there equivalent IVs in DES/CBC? I'm playing around with the CryptoPP library with DES/CBC and I've noticed that for some sets of data, if I decrypt the ciphertext with Key1, IV1, I get a good cleartext result -- but if I decrypt the same ciphertext with Key1, IV2, I get the identical good cleartext result.

I find this very surprising.  So much so, that I think I'm doing something wrong.

I want to check my assumptions: I've been under the impression that changing even 1 bit of the IV will alter the decryption result.  Is this not true?

Is there such a thing as an "equivalent" IV?

During CBC mode decryption, each ciphertext block is first decrypted with the block cipher, and then the first decrypted block is XORed with the IV, while later blocks are XORed with the previous ciphertext block:

Thus, the first block of plaintext is computed as: $$P_1 = IV \oplus D_K(C_1).$$

Equivalently, we may solve this equation for $IV$ to obtain: $$IV = P_1 \oplus D_K(C_1).$$

This means that, for any ciphertext and key, it's always possible to choose the IV so that the first block will decrypt to any plaintext we want.

This also implies that CBC mode is trivially malleable: an attacker who can modify the encrypted message can flip arbitrary bits in the first block of the plaintext simply by flipping the corresponding bits of the IV.  In particular, if the attacker can guess the original first block of plaintext, they can rewrite it to say whatever they want without knowing the key.  (A similar attack is possible for later blocks, but it tends to randomly scramble the previous block of plaintext.)

Such malleability is a general feature of CBC and all other non-authenticating cipher modes.  To protect against it, it is necessary to verify the integrity of the ciphertext using a MAC, or to use a combined authenticated encryption mode.


How to protect a device which has different levels of access to its storage? There is a device which has three software running on it, the main purpose is the control of some machinery.

a GUI front-end, running on a single-board computer with easily accessible storage (hard disk or SD card, etc.)
a back-end, running on the same SBC as the above.
a microcontroller which drives the hardware, and communicates solely with the back-end. The messages between #2 and #3 are short, in the range of 10 to at most 50 bytes.

Income is solely made by manufacturing and selling the device itself. However, the majority of the development costs are made up by developing the software #1 and #2.

The threat model is someone making a physical clone of the device, implementing their own version of software #3, and stealing software #1 and #2. For our threat model, for the attacker to read the memory (either volatile or non-volatile) of the microcontroller in #3 is to be considered impossible. Wiretapping the communication between #2 and #3 is to be considered easy.

This looks like a standard case of software protection dongle, with its obvious drawbacks: if it's only "check for the presence of the dongle", even if it's based on sending randomly generated code encrypted by the public key on one end, and decrypting it with the private key on the other end, it's easy to defeat with a single change in a single jump instruction to bypass the "if". Anything more would require very complicated solutions, like executing some code meant to be executed in #1 or #2 in the microcontroller instead.

Instead, I'm considering the following:

The microcontroller, obviously, will hold the private key of an asymmetric encryption.
The commands sent from #2 to #3 will be encrypted by the public key.
The replies (mainly status messages about the states of the controlled machinery) sent from #3 to #2 will be encrypted with the private key.

Does this scheme has critical drawbacks? Are there better alternatives?

I can see the following problems:

It doesn't secure #1 at all. (Maybe it could be done by routing it through #2 but it would make it needlessly complicated)
There are not too many types of messages and the messages are relatively short. Especially replies could be attacked, as the state of the machinery is visible, so by wiretapping one can see what kind of message gets generated in which state of the machinery. Yes, the messages could be padded, but not by orders of magnitude (it would reduce bandwidth), and adding random junk seems to be like a form of security through obscurity.

This question may be more suitable for other forums (https://security.stackexchange.com/ ?) This is not about cryptography.

I don't think cryptography will help you to secure the devices to protect your IP to the extend you'd like. Once you hand over the hardware to the 3rd party, there isn't much you can do.

Please do not count this as an answer, as it won't help you to achieve your goals. This "answer" should help you to clarify some options

  stealing software #1 and #2...
  change in a single jump instruction to bypass the "if"

So you are already assuming the SBC running the frontend could be fully read and the software modified (this is often so). If you give the adversary this power, you cannot do much about it. In that case "obfuscation" is the best what I can see (any better idea?).

  or the attacker to read the memory (either volatile or non-volatile) of the microcontroller in #3 is to be considered impossible

That's a very strong assumption.. though you've linked a "secure microprocessor", maybe you've already have something like that in mind  (smart card with crypto features? hms?)

  The commands sent from #2 to #3 will be encrypted by the public key.
  The replies (mainly status messages about the states of the controlled  machinery) sent from #3 to #2 will be encrypted with the private key.

Encryption is done with public keys, you could decrypt with a private key. So the microcontroller and the frontend both need each its own keypairs (private and public). PKI encryption will blow the message a lot, it is very performance expensive.

However - when you already came to an assumption that the adversary could read everything off the frontend (including the private key), the adversary could inpersonate the frontend and read/decrypt the messages anyway (accessing the private key of the frontend).


Static Diffie-Hellman in TLS Static Diffie-Hellman (cipher suites with DH in their name but neither DHE or DH_anon - requires that the server owns a certificate with a DH public key in it.

When static DH key exchange is used, the server provides a certificate containing fixed Diffie-Hellman parameters signed by the certificate authority (CA) - (ServerKeyExchange message is not used in this case).

Examples of static DH cipher suites:

TLS_DH_DSS_WITH_3DES_EDE_CBC_SHA
TLS_DH_RSA_WITH_3DES_EDE_CBC_SHA
TLS_DH_DSS_WITH_AES_128_CBC_SHA
TLS_DH_RSA_WITH_AES_128_CBC_SHA
TLS_DH_DSS_WITH_AES_256_CBC_SHA256
TLS_DH_RSA_WITH_AES_256_CBC_SHA256

From Diffie–Hellman key exchange
Alice and Bob publicly agree to use a modulus p = 23 and base g = 5 (which is a primitive root modulo 23) where p is prime, and g is a primitive root modulo p.
My question is.

Are the fixed Diffie-Hellman parameters provided in the certificate p and g ?

This has been (re-)defined in RFC 3279: "Algorithms and Identifiers for the Internet X.509 Public Key Infrastructure Certificate and Certificate Revocation List (CRL) Profile". For DH section 2.3.3: "Diffie-Hellman Key Exchange Keys" applies:

Here is the ASN.1 module (which was copied from X9.42, so this is at least a copy of a copy):

  DomainParameters ::= SEQUENCE {
        p       INTEGER, -- odd prime, p=jq +1
        g       INTEGER, -- generator, g
        q       INTEGER, -- factor of p-1
        j       INTEGER OPTIONAL, -- subgroup factor
        validationParms  ValidationParms OPTIONAL }

  ValidationParms ::= SEQUENCE {
        seed             BIT STRING,
        pgenCounter      INTEGER }

So it at least $p$, $g$ and $q$, but the co-factor $q$ is usually set to 1. This set has been defined for OID 1.2.840.10046.2.1 ("dhpublicnumber").

However, when trying this for myself using openssl command line, I only got two parameters, $p$ and $g$. Turns out openssl is using PKCS#3 instead:

  DHParameter ::= SEQUENCE {
        prime    INTEGER, -- p
        base     INTEGER, -- g
        privateValueLength INTEGER OPTIONAL }

which has been defined for OID 1.2.840.113549.1.3.1 ("dhKeyAgreement").

So yeah, $p$ and $g$ are certainly in there, which set of parameters are in there depends on the OID that defines the key type of the public key and the choices of the organization implementing it. That's a lot of options for something that is barely used.


Using authenticated encryption along with signing I know of a project that implemented e2e encryption using both authenticated encryption and public key signing. So the ciphertext produced for a message would be:
ciphertext = signature_Ed25519 + nonce + mac_Poly1305 + XSalsa20(plaintext)

I struggle to understand what the benefits of doing both could be, as MAC is already there to authenticate the sender. Any ideas?

The full flow is as follows:
Alice and Bob each have an X25519 encryption key pair for talking to each other.
Alice has an Ed25519 signing key pair that is used for everybody.

Alice sends a message to Bob:
1. encrypted = crypto_box(plaintext, nonce, bob_publickey, alice_secretkey)

This is provided by crypto_box().
encrypted is now = nonce + mac_Poly1305 + XSalsa20(plaintext)
2. ciphertext = crypto_sign(encryted, alice_signing_secretkey)

This is provided by crypto_sign().
ciphertext is now = signature_Ed25519 + encrypted

Signatures provide one property that MACs don't: non-repudiation. With only a MAC (or an AEAD) any party with the secret key could have sent the message. So Bob could forge a message and claim Alice sent it. With a signature only the party holding the corresponding private key could have created the signature.  MACs authenticate the message, not the sender.
When this property is needed one must accept the performance decrease of adding the signature. If this property isn't needed, then there's no need to sign.


Homomorphic $\bmod p$ operation Let $E(m)$ a be the encryption  operation using Paillier encryption scheme. Let $N$ be the public key and $p$ be a large prime number, such that $p<N$.

Question: Is there any protocol, that given $E(m)$ can compute homomorphic $\mod p$, so after decryption we would a message in $\mathbb{F}_p$?

Or is there any multi-party computation protocol that can do it?

Is there any protocol, that given $E(m)$ can compute homomorphic $E(m \bmod p)?$

If there were a way to perform that operation (for any $p>1$ relatively prime to $N$) without the Pallier private key being involved, then you have just shown that Pallier is Fully Homomorphic; that is, you can homomorphicly implement any computation; at the very least, by doing homomophic circuit evalutation.

One approach to show this is to implement a NAND function, which we can do as follows:

$$\textit{NAND}(x, y) = 1 + p^{-1} \cdot ( \lambda(x + y) \bmod p - \lambda(x+y))$$

where:

All the operations are done homomorphically, for example, $x + y$ means the homomorphic addition of $x$ and $y$
$\lambda$ is an integer $p > \lambda \ge p/2$
$p^{-1}$ is the multiplicative inverse of $p$ modulo $N$

All the computations included in the NAND definition are additions, subtractions, multiplications by the constants $\lambda$ and $p^{-1}$ (all of which can be performed homomorphicly within Pallier), and the $\bmod p$ operation, which we are assuming also can be performed homomorphicly.

And, if we evaluate NAND (assuming that $x, y$ are constrained to be either 0 or 1, we find that if either $x, y$ are encrypted 0 (or both are), NAND evaluated to encrypted 1; if both are 1, it evaluates to an encrypted 0.

And, NAND is known to be complete; we can construct any circuit be a sufficiently large pile of them.  That is, we can design a circuit to evaluate our function (e.g. SHA-3), and then give as inputs as a series of encrypted 0's and 1's, and get the output as a series of encrypted 0's and 1's.


PKCS#10 why keeping the Subject Public Key in the X.509 Certificate In the pkcs#10 workflow to obtain the x.509 certificate used in digital signature, in the Certificate Request Information, itself in the CSR, we have the Subject Public Key.

That Subject Public Key will be used to verify that the CSR isn't modified since the Subject wrote it. All is fine up here.

Once the verification of the CSR is done, the Certificate Authority generate the X.509 Certificate. In the PKCS#10 (3. Overview, first paragraph after the ordered list), it is stated that we give the Subject Public Key in the X.509 Certificate.

The Subject Public Key was provided because we signed the CSR with the Subject Private Key, but this private key won't be reused afterward. It might have been generated only for the CSR creation, and the CSR isn't kept in the X.509 Certificate.

Also, the X.509 Certificate is signed by the Certificate Authority with its own private key, not the Subject Private Key.

So the question is : Why keeping the Subject Public Key in the X.509 Certificate, as its goal is reached once we verified the CSR, verification done before the X.509 Certificate generation?

The certificate is signed with the Certificate Authority's private key, but the purpose of an X.509 Public Key certificate is to associate a public key with a subject-entity.

You generate a public/private pair
You generate a PKCS#10 CSR which contains the SubjectPublicKeyInfo, signed with the private key as proof-of-possession.
You submit the PKCS#10 CSR to a CA.
The CA does whatever validation they do to ensure that you're the subject that you claim to be in the CSR (or whatever subject you claim to be external to the CSR) ... and for whatever extensions you may have requested.
The CA copies the SubjectPublicKeyInfo into a new certificate they create, and they sign it with their private key.
People can now use the trust of the certificate to understand that signatures that come "from you" and verify under the public key within the certificate are actually from you (or used a stolen/cracked version of your private key).

Alternatively: Whose public key do you want them to put in your certificate?  If they just made one up on the fly for you they'd also have had a copy of your private key, which is clearly less secure than only you ever having your private key.


Can Hill Cipher be considered as Asymmetric? I know hill cipher is a block chipher ,We produce decryption key by inverse of key matirx but we still use different key for decryption. Therefore Can we say that Hill cipher is asymmetric chipher?

No, because matrix inversion can be done efficiently. Namely, if encryption is multiplication by a matrix $A$, then you can define decryption with $A$ as first computing the inverse of $A$ and then multiplying.

An essential property of public-key cryptosystems is that it should not be possible to efficiently derive the (private) decryption key from the (public) encryption key. In the Hill cipher, the matrix must be kept secret.


What is wrong with encryption-based / hash-based commitment schemes? In the slides to my information security class it is stated without explanation that a encryption-based commitment scheme defined as follows is broken:

Commit: P outputs c = Enck(m)
Reveal: P sends k to V. V decrypts c and learns m = Deck(c)

Similarly, a hash-based commitment scheme (using cryptographic hash function H) defined as follows is also stated to be broken:

Commit: P outputs c = H(m)
Reveal: P sends m to V. V verifies that c = H(m).

Why are these schemes broken with respect to hiding and binding?

The only reasons I can think of that these schemes might be broken are the following:

In the encryption-based scheme, the encryption might reveal something about the length of the message, breaking the principle of hiding. However, this could be addressed by padding the messages to a fixed length.
In the hash-based scheme, two hashes might collide, breaking the principle of binding.

Are there any other reasons these schemes are not valid commitment schemes?

The second construction is trivially not hiding. It is easy to verify a guess $m'$ just by recomputing $H(m')$ and comparing the result with the commitment.

The first construction is a bit trickier. If it is a CPA secure encryption scheme, then it is certainly hiding. However it may not be binding.

It is easy to construct secure encryption schemes, where different keys decrypt the same ciphertext to two different messages. In fact most symmetric encryption schemes without authentication definitely fall into this category. As do public key encryption schemes such as ElGamal encryption.


Block cipher does not provide security by itself What is this statement all about? When I look at a block cipher it seems pretty hard to break it and the mathematics behind insure a good complexity. It may refer to key generation, initialization vector (IV), padding scheme ?

That statement is ambiguous, so I'll list a couple of limitation of block ciphers and cryptography in general:

A raw blockcipher by itself only permutes a fixed size block (128 bits for AES). You need to add a mode of operation (together with IVs and possibly padding) to make it flexible enough for practical use. There are many modes to choose from, including CBC, CTR, OCB, SIV, GCM and XTS. Each one has different properties and strength, so which one is best depends on the the situation.
Encryption without integrity checks (e.g. using AES in CBC mode) is often vulnerable to active attacks, so you need to add a MAC. A modern trend is to use a mode-of-operation that provides both integrity and confidentiality (authenticated encryption, AEAD).
Encryption reduces a confidentiality problem to a key management problem. You still need to solve the key management problem.
Cryptography doesn't provide security by itself. You always need to consider the larger system. This includes endpoint security, threat models, key and identity management and much more.


Determine if $f(x)+x_0+x_n$ is balanced If $f(x)=x_0x_1\oplus x_1x_2\oplus\cdots\oplus x_{n-2}x_{n-1}\oplus x_{n-1}x_n\oplus L(x)$ is a balanced boolean function (which is a boolean function whose output yields as many 0s as 1s over its input). Determine if $f(x)\oplus x_0\oplus x_n$ is balanced.    Notice that $L(x)=k_0x_0\oplus k_1x_1\oplus k_2x_2+\cdots\oplus k_nx_n$, where $  k_i \in \{0,1\}$.

Newly to this field. Any hints would be helpful.

If you want to learn about your new field, I strongly recommend you to read only section 3 of Correlation of Quadratic Boolean Functions: Cryptanalysis of All Versions of Full MORUS, maybe skipping the proofs but definitely not the examples during the first reading.

Try then to solve your problem for at least an hour, before reading my solution below. (Hint: Apply Algorithm 1 (no need to program it) to your function $f$, and then Lemma 4 to the result of Alg. 1.)

As a self-contained answer would be much too long, I assume that the reader understood section 3 of the paper mentioned above.

Following Algorithm 1, define $x'_0 := x_0+x_2$ then $x'_2 := x_2 + x_4$, and so on, and additionally (don't look at the $k'$ before you understood about the $x'$) $k'_0 := k_0, k'_{2i+1} = k_{2i+1}, k'_{2i+2} := k_{2i+2}+k_{2i}$ to clean up the linear term L  to get

$$f(x'_0, x_1, x'_2, x_2, \dots) = x'_0x_1 + x'_2x_3 + \dots + x'_{m-1}x_m + k'_0x_0 + k'_1x_1 + \dots + k'_nx_n,$$

in disjoint quadratic form, where $m=n$ if $n$ odd and $m=n-1$ if $n$ even.

Lemma 4 tells you now that kodlu is right in claiming that $f$ cannot be balanced if $n$ is odd, as all variables $x'_0, x_1, x'_2, \dots$ show up in some quadratic term (that are separated after the substitution).

Lemma 4 tells you also that for $n$ even, $k'_n = k_n+k_{n-2}$ being $1$ is equivalent to $f$ being balanced, as $x_n$ is the only variable not showing up in any quadratic term (that all are separated over the variables $x'_0, x_1, x'_2, \dots$).

For $n$ even adding $x_n$ to $f$ corresponds to replacing $k_n$ by $k_n+1$ making $k'_n=0$ and $f$ not balanced.

Adding then $x_0$ to $f$ corresponds to replacing $k'_i$ by $k'_i+1$ for all even indices $i$, in particular also for $i=n$ even, making $k'_n=1$ and $f$ balanced again.


How can I share a number with an opponent? Let's say I have a message (eg: Hello, world!) and I want to encrypt this message using symmetric encryption (AES-256). I am using a list of keys, where I randomly take one as a key (so that each message has a random key). My opponent also has this list of keys, but due to its size it will take too much time to brute-force.

I would like to somehow share either the key, or the index number of the key in the key-list with my opponent, but I have to do it at the same time I am sending the message.

Is there an algorithm or protocol which I can use to handle this scenario?

Throw away the key lists and generate a fresh key every time you want to transmit a message. Use a key exchange algorithm like for example Diffie-Hellman.

If an enemy can steal your keys they are pretty much useless. You would have to notice the theft and replace all your keys with new ones. Asymmetric encryption like RSA won't help you here because as with symmetric keys the private key could be stolen. There's not much left you can do now, except for a key exchange algorithm. With that you create a new key every time you want to send a message to your friend. Beware that this won't help you against active attackers which can intercept and replace the communication between you two. It also needs direct responses from the other person to create a key, so you can't send him a new message when he's offline.


Can homomorphic encryption achieve program integrity (verification) in the cloud? As I understand it, homomorphic encryption can be used to keep data confidential while still allowing computations over the data. From another question, I found out that one can also verify the integrity of the computation, (by which I mean one can verify that a returned value is indeed the result of the requested computation) by re-computing the result.

I am interested in a scenario where re-computing is not possible. For example, the original data might not be available anymore or the original data is very large and re-computing is too expensive. Are there other ways to verify that a result corresponds to the required computation?

That is, say I want to perform the operation r = a + b + c using homomorphic encryption, in the cloud. Once the cloud returns the result r, how can I verify that r is the result of a + b + c and not, say, the result of a + b or some other computation?

Can I use homomorphic encryption to keep cloud computation confidential and also guarantee the integrity of computation?

You're looking for verifiable computing:

  Verifiable computing (or verified computation or verified computing) is enabling a computer to offload the computation of some function, to other perhaps untrusted clients, while maintaining verifiable results. The other clients evaluate the function and return the result with a proof that the computation of the function was carried out correctly.