Why is a 1 added after the message input and before adding padding zeros (if necessary) when using SHA256 or RIPEMD160? In preparing an input for SHA256 or RIPEMD-160 a single bit (1) is appended to the message before adding any necessary zero padding and before adding the bitlength (64 bits) to form 1 or more 512 bit blocks. What is the purpose of adding the single bit (1)?

If you look at the Wikipedia on padding article page, you will see many different ideas.

The main problem when designing a padding, firstly, one has to consider how to eliminate the padding correctly, all the time. It is the designer's choice, as noted in and the original RFC 4634 -- SHA and HMAC-SHA.

Once you put 1 followed by many 000 to the end of a string, you can remove the padding by looking the first position of a single 1 from the end. That was the simplest idea for padding, AFAIK.

When considering that hashes only supply integrity, If finding a collusion is easy with this (or any) padding than the hash is already failed there.


Maximum output of HKDF I got a question with the RFC of HKDF https://tools.ietf.org/html/rfc5869.

There is a maximum specified for the output keying material. The length of the OKM shall be <= 255*HashLen. What does it mean? For example there is a hashfunction with output of 32 byte. Is my maximum OKM then 255*32 = 8160 Byte? Or does it mean, my maximum repetition in the loop is smaller or equal than 8160? So that would mean, that you can generate 8160 (rounds) * 32 (per round output) 261120 Byte output.

I am a little bit confused...thanks for help.

The former. Maximum output must be <= 255*HashLen. So for SHA256 which has a digest of 32 bytes, max HKDF output would be <= 8160 bytes. For SHA512 which has a digest of 64 bytes, max output must be <= 16320 bytes. I can't imagine you would need a key longer than 8160 bytes. If you require multiple keys you can use the 'info' parameter for different contexts/keys from the same PRK.


What is the Lord of the Ring(s): Side Channel Attack and What are the results A recent Paper to appear on USENIX Security 2021 titled as
Lord of the Ring(s): Side Channel Attacks on the CPU On-Chip Ring Interconnect Are Practical by Riccardo Paccagnella Licheng Luo Christopher W. Fletcher
They were able to use the ring interconnect’s functioning of Intel CPUs previously exploited. They claim to extract RSA and EdDSA keys and key-stroke timings.

How does this attack work on the high level?
What are the mitigations against his attack?
What are the consequences of this attack?
Are secure implementations affected by this attack?

bonus part:

How does this attack works on the low level?

How does this attack works on the high level?

Resource sharing on multicore CPUs has benefits like low cost and efficiency. This, however, is the attack point that we saw over the years. With the cache attack, the victim's data extracted with cache manipulations.
The countermeasure against the various cache attacks is disabling simultaneous multi-threading (SMT) and the obvious is the cleansing of the cache during the context switching. The cross-core cache attack is prevented by partitioning the Last Level Cache (LLC) (e.g. Intel CAT) and disabling shared memory for different security domains.
The presented attack works even the countermeasures are applied. This attack leverages contention on the ring interconnect, which is the component that enables the communication between the different CPU units.
The hardest part of this attack is getting information about the ring since it was not well documented.
L1 and L2 caches are called private caches since they are private to the core so that cross explanation is not possible. Since the Nehalem-EX the L3 cache (LLC) is divided into slices into equal size and only one slice per core.
In Intel architecture the L1, L2, and LLC are inclusive, meaning that if there is data on L1 and L2 then it is also in L3.

The ring-bus in the above picture tells most of its structure. It used in intra-process communications when a cache miss occurs in L1,L2 then the data must travel on the ring-bus to arrive LLC.
Now skipping the low-level details, the attacker's process can create a contention by transmitting 1 and idle with 0. By measuring the latency they can extract keys from insecure naive square-and-multiply RSA implementation. Like in the power attack, the second peak indicates the bit 1. This is similarly done for EdDSA.

The second face of this new channel is the keystrokes. The attack leaks the timing of the keystrokes and this can be used to reconstruct the typed words or worse the passwords. Like in this article;

Peeping Tom in the Neighborhood: Keystroke Eavesdropping on Multi-User Systems, 2009, Zhang and Wang

What are the mitigations against his attack?

For cryptographic code use secure implementations particularly constant-time programming principles. A side-channel secure implementation will not be vulnerable to the current state of being in the Cache-Ring attack. However, achieving that may not be an easy job since Intel CPUs perform hardware store elimination between the private caches and ring interconnect ( see Hardware Store Elimination)
For keystrokes, hardware can be designed based on spatial partitioning and statically-scheduled arbitration policies. Also, a software-based solution can be designed for sending the password in regular intervals.

What are the consequences of this attack?

It opened a new side-channel on the multicore CPUs. I've expected that clever minds will improve this attack in many ways. Note that, still, if your code is not vulnerable to cache attacks and they are timing-attack free, I don't see an exploit there, yet.

Are secure implementations affected by this attack?

Currently, no. Keystrokes, however, can be a big issue.


Can one-way permutations be constructed from one-way functions? We can construct various symmetric key primitives like PRGs, PRFs, SPRPs etc., assuming the existence of either one-way permutations or one-way functions with the former assumption allowing simpler constructions.

However, what is the relationship between one-way permutations and one-way functions? Clearly, the existence of one-way permutations implies the existence of one-way functions. Is the converse true? If it isn't then assuming one-way permutations is strictly stronger than assuming one-way functions.

It was shown by Rudich in his PhD thesis [R] that it is not possible to construct one-way permutations (OWPs) from one-way functions (OWFs) in the framework of black-box reductions.$^1$ This was later strengthened by Matsuda and Matsura [MM], who ruled out black-box construction of OWPs from injective OWFs (which are much more structured than OWFs) that expand by even a single bit. So, yes assuming OWPs is strictly stronger than assuming OWFs (or iOWFs).

The technique employed in both the results is called oracle separations. The idea is to construct an oracle relative to which OWFs (or iOWFs) exist, but any black-box construction of one-way permutations is broken. An overview of Rudich's argument can be found on this thread.

But as Maeher points there could still exists non-black-box constructions of OWPs from OWFs. For example, we know that given indistinguishability obfuscation (IO), it is possible to construct (even trapdoor) OWPs from OWFs [BPW].$^2$ I believe a construction without IO is still open.

You can read more about the different notion of reductions here and on black-box separations here and the references therein.

$^1$ This was under a conjecture which was later proved by Kahn et al. [KSS].

$^2$ There have been attempts at at ruling out even non-black construction of cryptographic objects from one-way functions (e.g, [DS]), but I am not sure if any of them extend to OWPs.

[BPW] Bitanksy, Paneth and Wichs, Perfect Structure on the Edge of Chaos, TCC 2016

[DS] Dachmann-Soled, Towards Non-Black-Box Separations ofPublic Key Encryption and One Way Function

[KSS] Kahn, Saks and Smyth, A dual version of Reimer's inequality and a [enter link description here]5proof of Rudich's conjecture, CoCo 2000

[MM] Matsuda and Matsuura, On Black-Box Separations among Injective One-Way Functions, TCC 2011

[R] Rudich, Limits on the Provable Consequences of One-way Functions, PhD Thesis


Determining key size in bits by knowing plaintext and ciphertext I need to know how can I determine the key size in bits knowing the ciphertext and the encryption algorithm used?

For example suppose the plaintext was "ABC" and after the encryption it became "DEF" so the key size in bits = 1 bit because each letter is shifted only by 1 to its next character? Or I am wrong?

Please explain it in more details and thanks in advance and sorry for the inconvenience.

I need to know how can I determine the key size in bits knowing the ciphertext and the encryption algorithm used?

That depends on what you mean exactly by the term encryption algorithm used.

The full description of an encryption scheme usually consists of three parts. For example if AES-128-GCM was used to encrypt, that means that the block cipher AES was used in GCM mode using a 128 bit key. If your scheme is named liked this, than you are presented with the key length directly (Note that there are different schemes as well (like stream ciphers), which won't follow this naming scheme).

If the key size is not included in the name, there is usually no way to deduce it from the ciphertext. This is due to the fact that most encryption algorithms can be used with different key sizes (128, 192 and 256 bits in the case of AES) while keeping other parameters, visible to the outside world (input and output length), the same.

  For example suppose the plaintext was "ABC" and after the encryption it became "DEF" so the key size in bits = 1 bit because each letter is shifted only by 1 to its next character? Or I am wrong?

In the case of the classic Caesar cipher that you are using here, the key is an integer value between zero and 26 (of 52, or 62, if you allow for more characters) specifying the shift. So, depending on the size of your alphabet (the number of input / output characters that will be encrypted), the key's size will be between 5 and 7 bits.


Why multiple homomorphic operations on a ciphertext leaks no information about the plaintext? Scenario:

Assume I encrypt message $m$ using Paillier encryption, so I would get $c=E(m)$.

I give the identical $c$ to two different parties, parties $D$ and $E$.

Party $D$ computes: $c_{D}= E(m)^{h_1}=E(m \cdot h_1)$
Party $E$ computes: $c_{E}= E(m)^{h_2}=E(m \cdot h_2)$

Values $c, c_{D}$ and $c_{E}$ are given to a malicious server.

Question: Does the server learn anything about values $m,h_1$ or $h_2$? if yes/no why?

Remark 1: It seems to me it cannot learn anything about the messages, because given $c$ it can do homomorphic operation on its own to get the ciphertexts $c_{D}$ and $c_{E}$; and if it could the homomorphic encryptions would not be secure anymore. But, the problem is that we have not changed the random value $r$ (in encryption) so all ciphetexts possess the identical random value.

Remark 2: I mentioned Paillier because I'm using it right now, and the question can be generalized for any homomorphic encryptions.

If the parties do exactly what you have described, then yes, the malicious server can learn some information. In particular, if $h_1 == h_2$, then $c_D == c_E$. So, given the $c$ values, the malicious server can learn whether or not $h_1 == h_2$. Furthermore, the malicious server can learn if either $h$ value is $1$, as $c$ would not change. Finally, if the $h$ values are drawn from a small set of numbers, where the set is known to the malicious server, the malicious server can actually brute-force the $h$ values given the $c$ values.

This is all due to the fact that homomorphically multiplying by a constant (which is done via exponentiation in the ciphertext domain) with Paillier is deterministic. Given the same ciphertext value and the same constant, you will get the same result.

To fix this issue, you should homomorphically add a fresh encryption of $0$ to the ciphertext after any operations. This rerandomization step* is very important when using Paillier or other additively homomorphic ciphers.

* Sorry to link to my own project on this, but it illustrates the point, I think.


Notation question for hash functions Let $H(-)$ be a cryptographic hash function with values in $\{0,1\}^k$.

What do we mean when we say that $H(x) < D$ for some $D\in \mathbb N$? Are we summing the elements of $H(x)$?

$H(x) < D$ likely mean that $D$ is greater than the integer in range $[0,2^k-1]$ represented by the $k$-bit bitstring $H(x)$ in binary, per some convention. If we note the bits of that bitstring $b_0$ for the first/left one, and $b_{k-1}$ for the last/right one:

$\displaystyle\ \ \ D>\sum_{i=0}^{k-1}b_i\,2^{k-1-i}\ $ for big-endian, which thends to be the default convention; or

$\displaystyle\ \ \ D>\sum_{i=0}^{k-1}b_i\,2^k\ \ $ for little-endian.

If $H$ is secure in the random oracle model, and $x$ chosen without knowledge of $H$, then (for either convention) $H(x) < D$ holds with probability $\displaystyle{\max\left({D\over2^k},1\right)}$.


Hash function construction I recently studied a Hash function and its security requirement. I have studied that simple hash construction from XOR is weak. My question is, based on Xor property the following Hash based on RSA Mi<n calculated by
$H(M_1,M_2)=(M_1^e \bmod n) \oplus (M_2^e \bmod n)$, where $(n,e)$ is an RSA public key.
satisfy the collision resistant and 2nd preimage resistant?

The construction is trivially neither collision resistant nor second preimage resistant, since XOR is commutative. I.e. for any $a,b$ it holds that $a\oplus b = b \oplus a$.
Consequently, given $M_1,M_2$ as a first preimage, we can trivially find $M_2,M_1$ as a second preimage. To break collision resistance, simply choose $M_1,M_2$ arbitrarily.


Is the ring of octonions "commonly" used in Cryptography? I've recently read "Fully Homomorphic Encryption on Octonion Ring" by Yagisawa, which is based on octonion rings over finite fields.

Personally I've never encountered octonion rings in cryptography before. Is there any example of them being used in previous work?

Please don't mention the mentioned previous version of this scheme.

I can’t remember having stumbled upon them in RealLife™ cryptography either, but I am well aware of a somewhat older, related patent by the same author. (Which might or might not violate your “Please don't mention the mentioned previous version of this scheme.” depending on what you’ve previously been reading. The patent is titled “Schemes for signcryption” and dates back to 2012. The paper published before the one you’ve mentioned was “Fully Homomorphic Encryption without bootstrapping”, published in 2015.)

Anyway…

From what I’ve seen, “patents” related to cryptography are a good way to ensure that no one feels the urge to use your “invention” anytime soon – which might explain the (lack of) popularity of the term.

  Publication number: US20140169556 A1
  Publication type: Application
  Application number: US 13/995,312
  PCT number: PCT/US2012/070369
  Publication date: Jun 19, 2014
  Filing date: Dec 18, 2012
  Priority date: Dec 18, 2012
  Also published as WO2014098807A1
  Inventors: Masahiro Yagisawa
  Original Assignee: Empire Technology Development Llc
  Export Citation: BiBTeX, EndNote, RefMan
  Classifications (10), Legal Events (2)
  External Links: USPTO, USPTO Assignment, Espacenet

  Schemes for signcryption

  US 20140169556 A1

  Abstract

  Technologies are generally described for providing a signcryption scheme. In some examples, a method performed under control of a sender device may include calculating a public key of the sender device based on a system parameter, calculating a temporary public key of the sender device based on the system parameter, calculating a temporary common key of the sender device based on a temporary secret key of the sender device and a public key of a receiver device, calculating a ciphertext from a message based on the temporary common key and generating a signature of the sender device based on an intermediate parameter, the system parameter and the secret key of the sender device. The temporary secret key of the sender device, intermediate parameter and secret key of the sender device are engaged in a non-associative octonion ring.

  In some examples, a method performed under control of a receiver device may include calculating a public key of the receiver device based on a system parameter, calculating a temporary common key of the receiver device based on a temporary public key of the sender device and a secret key of a receiver device, deciphering the ciphertext based on the temporary common keys of receiver device, determining whether the digital signature received is generated by sender device. A temporary public key of the sender device, the secret key of the receiver device and the temporary common keys of the receiver device are engaged in a non-associative octonion ring.


Prime factorization of 700 decimal digits number I'm a newbie to encryption. If I create a number 'n' as a product of two prime numbers 'p' and 'q' with the following specifications:

'p' is a fully random prime with 300 decimal digits in length.
'q' is a fully random prime with 400 decimal digits in length.

My question is: If I make 'n' public, will anyone be able to get 'p' and 'q' within a month? Tanks in advance!

No an attacker will not be able to factor your $n$ (e.g. break it).

Your $n$ is of size 700 decimal digits which is $\frac{700}{\log_{10}(2)}\approx2325$ bits. Now 2048-bit moduli is the most widespread size used on the internet and hasn't seen a failure yet (without exploiting bad random number generators), so you are secure with that modulus size.

As for the largest known-broken modulus size, this would be a 768-bit modulus and it is conjectured that nation-state attackers are able to factor 1024-bit moduli using their ressources.

You have chosen 400 digits and 300 digits. While this is safe in this instance, this is unusual to do, because too much unbalancedness can help the attacker as he can apply attacks that find small factors first (by trial division or ECM). The standard way of approaching this is to generate two equally large primes (in terms of digits) and ensuring that $|p-q|>2^{k/3}$ (where k is your modulus bitlength), which will hold anyways with overwhelming probability if you choose both primes independently at random.


What is the length of the SHA-1 message digest and how is RSASSA-PSS used for verification? I am a newbie to cryptography and SHA-1.

Currently I am configuring a SHA-1 hash function which takes default length as 128 bits. Is it okay to configure it this way, since I see in most cases SHA-1 uses 160 bits? So what is the most common length used for SHA-1 hashes?

I read in many places that RSASSA-PSS is used for signature verification?
I assume message digest or hashed value or signature all refer to output hashed value of SHA-1.

How do I use the RSASSA-PSS function to verify the signature? Should I pass it the message digest value and expect that the plain text should match the initial input given to the SHA-1 function?

Currently iIam configuring SHA1 hash function which takes default length as 128 bit. Is it OK to configure with this, since I see in most of the SHA1 uses 160 bit? So what is the most common length used for SHA1 Hash?

Assuming that you mean output size: the output size of SHA-1 is 160 bits (20 bytes) and cannot be configured. In some cases protocols however use only the leftmost bits of the hash.

Although using only the leftmost bits is generally considered secure SHA-1 already has a security strength of about 80 bits (half of 160 bits output size) - about the bare minimum. Removing bits from the output size will also decrease the security, so that is not recommended.

Sometimes protection against pre-images is not an issue and cutting down the SHA-1 size is not a problem (HMAC-SHA1 for instance could use fewer bits).

  I read in many places that RsaSsaPss is used for verification of signature? I assume Message Digest or Hashed Value or Signature -> all these terms refers to output Hashed value of SHA1.

Only Message Digest or Hashed Value refer to the output of the hash value. The signature is generated using a combination of the hash function, the padding function (e.g. PSS) and of course the RSA modular exponentiation. More details in PKCS#1 v2.1 or v2.2.

  How to use Rsa Ssa Pss function to verify the signature? should i pass the Message Digest value and expect that the plain text should match with initial input given to SHA1 function?

Depending on the implementation you need either to pass the data and the signature into the signature verification function or you need to pass the hash function or hash value and the signature to the signature verification function.

The signature implementation must have been configured for the right algorithm and initialized for verification with the correct public key, of course.

For signature generation / verification it is generally required to use a secure hash function such as SHA-2.

Beware that the MGF1 function that is used for PSS may also use a hash function. You may have to configure that one separately - it should default to SHA-1 - which in the case of MGF1 would be secure.


Number of preimages of hash function from bounded domain Suppose we have an "ideal" cryptographic hash function

$H: \{0,1\}^{n+k}\to \{0,1\}^{n}$

and a given bitstring $b\in \{0,1\}^{n}$, Can we estimate how many preimages $H^{-1}(b)$ there are?

With ideal I mean that it behaves like a random oracle.

I assume you mean behaves like a uniformly chosen function from the set of functions mapping $\{0,1\}^{n+k}$ to $\{0,1\}^n.$

Let $p_z$ be the probability that the random variable $Z=|H^{-1}(b)|=z,$ for $0\leq z\leq 2^{n+k}.$
Then $$p_0=(1-2^{-n})^{2^{n+k}}\approx \exp[-2^k]$$
which is the probability that a fixed $b$ is missed $2^{n+k}$ times. Of course $\mathbb{P}(|H^{-1}(b)|=z)$ is independent of $z$ and distributed binomially, i.e., $$\mathbb{P}(|H^{-1}(b)|=z)=\binom{2^{n+k}}{z}(1-2^{-n})^{2^{n+k}-z} (2^{-n})^{z}$$

With high probability, the distribution $p_z$ is concentrated around its expectation $Z=2^{k},$ for example via the Chernoff bound.


Error Check in Lattice PQC I am by no means an expert in the PQC field and am just trying to self teach myself about it. I was hoping to look into error correcting in lattice. I want learn about error or fault detection as it applies to lattice, but I am unable to find many resources.
Does something like CRC apply to a lattice? Or are there lattice specific mechanisms?
I know this is a little broad, just looking for some insights.

Error-correction occurs within lattices in roughly two forms:

Binary error-correction is sometimes used within lattice-based protocols, although not all of the time. There are certain issues with doing this, namely that the errors in LWE-based encryption are not naturally of small hamming weight, while binary error-correction corrects errors of small hamming weight. Some analysis used a certain independence heuristic which ended up being invalid, leading to improper settings of parameters/attacks on NIST PQC candidates.

Error-correction with "lattice codes", or more properly codes for the Additive White Gaussian Noise (AWGN) channel. These are often called "sphere packings", and are used to correct the LWE error $e$ in an LWE sample $(A, As + e)$, which is of small $\ell_p$ norm (generally for $p = \infty$).

Lattice cryptography very often uses this second type of code. Basic examples are in Regev-style encryption, where one encrypts $m\in\{0,1\}$ via $(A, As + e + (q/2)m)$.
Here, one can view $(q/2)m$ as the value of $m$ being encoded under the lattice code corresponding to $(q/2)\mathbb{Z}^n$.
There are other more complex lattice codes used --- the Micciancio-Piekert "gadget matrix" $G$ can be seen as using the lattice $\bigoplus_i\Lambda_q(g^t)$, where $g = (1,2,\dots,2^{k-1})$. Van Poppelen's masters thesis looked into the potential benefits of using (direct sums of) the Leech lattice $\Lambda_{24}$.
There are more things you can do with lattice codes, but I hope the above is useful in understanding the "error correction" that most commonly occurs within lattice cryptography.


Complete Set of Test-Vectors for ECDSA secp256k1 Although there are several implementations of ECDSA secp256k1 public available over the internet (the most popular being OpenSSL), it seems that there are no complete set of test-vectors available.

The few test vectors I could find always miss some important information:

do not provide the hash integer or the secure random integer k.
do not provide the (r,s) signature pair, instead only provides some hash of it according to bitcoin protocol format.

A complete set of test-vectors would require the following information:

private key
public key x-coordinate
public key y-coordinate
hash
secure random integer k (see note bellow)
r signature
s signature

Example:

1. private key: D30519BCAE8D180DBFCC94FE0B8383DC310185B0BE97B4365083EBCECCD75759
2. public key x-coordinate: 3AF1E1EFA4D1E1AD5CB9E3967E98E901DAFCD37C44CF0BFB6C216997F5EE51DF
3. public key y-coordinate: E4ACAC3E6F139E0C7DB2BD736824F51392BDA176965A1C59EB9C3C5FF9E85D7A
4. hash: 3F891FDA3704F0368DAB65FA81EBE616F4AA2A0854995DA4DC0B59D2CADBD64F
5. secure random integer k: CF554F5F4224223D52DC9CA784478FAC3C1A0D0419FDEEF27849A81846C71BA3
6. r signature: A5C7B7756D34D8AAF6AA68F0B71644F0BEF90D8BFD126CE951B6060498345089
7. s signature: BC9644F1625AF13841E589FD00653AE8C763309184EA0DE481E8F06709E5D1CB

Note that a set o test-vectors without the random integer k might also be helpful for validation purposes:

first validate the signature verification code
than use the validated signature verification code to validate the signature generation code

The reason I consider important to include the random integer k is because with it you can validate different parts of the code independently of each other, therefore reducing the risks of hidden bugs.

Question
Is there any public available test-vector with the aforementioned set of information?

OK, so I quickly found out that there is a test in Bouncy Castle called:

org.bouncycastle.crypto.test.ECTest.testECDSASecP224k1sha256()

which tests exactly what you are trying to do (with a message the same size of a SHA-256 hash).

So I decided to create a new test that duplicates this test, but for SecP256k1 and SHA-256.

I've generated the following test vectors (I'll use hexadecimals):

 d = ebb2c082fd7727890a28ac82f6bdf97bad8de9f5d7c9028692de1a255cad3e0f
 k = 49a0d7b786ec9cde0d0721d72804befd06571c974b191efb42ecf322ba9ddd9a
 M = 4b688df40bcedbe641ddb16ff0a1842d9c67ea1c3bf63f3e0471baa664531d1a

resulting in:

 r = 241097efbf8b63bf145c8961dbdf10c310efbb3b2676bbc0f8b08505c9e2f795
 s = 021006b7838609339e8b415a7f9acb1b661828131aef1ecbc7955dfb01f3ca0e

note that $s$ starts with 6 zero bits, which should be fine.

Finally, you'd want to verify the signature as well of course, so here is the public key:

 q = 04779dd197a5df977ed2cf6cb31d82d43328b790dc6b3b7d4437a427bd5847dfcde94b724a555b6d017bb7607c3e3281daf5b1699d6ef4124975c9237b917d426f

where $q$ is an uncompressed point, consisting of the following coordinates:

x = 779dd197a5df977ed2cf6cb31d82d43328b790dc6b3b7d4437a427bd5847dfcd
y = e94b724a555b6d017bb7607c3e3281daf5b1699d6ef4124975c9237b917d426f

Method of generating the parameters:

private static final void createAndPrintRequiredParameters()
{
    // code used to generate the random key pair (public point converted to uncompressed point encoding manually)
    ECKeyPairGenerator gen = new ECKeyPairGenerator();
    X9ECParameters p = SECNamedCurves.getByName("secp256k1");
    ECDomainParameters params = new ECDomainParameters(p.getCurve(), p.getG(), p.getN(), p.getH());
    SecureRandom kpr = new SecureRandom();
    ECKeyGenerationParameters genParams = new ECKeyGenerationParameters(params, kpr);
    gen.init(genParams);
    AsymmetricCipherKeyPair ecKeyPair = gen.generateKeyPair();
    ECPrivateKeyParameters ecPrivate = (ECPrivateKeyParameters) ecKeyPair.getPrivate();
    ECPublicKeyParameters ecPublic = (ECPublicKeyParameters) ecKeyPair.getPublic();
    System.out.println(ecPrivate.getD().toString(16));
    System.out.println(ecPublic.getQ().toString());

    // code used to generate the message (hash) M
    byte[] mesg = "Maarten Bodewes generated this test vector on 2016-11-08".getBytes(StandardCharsets.UTF_8);
    SHA256Digest dig = new SHA256Digest();
    dig.update(mesg, 0, mesg.length);
    byte[] M = new byte[dig.getDigestSize()];
    dig.doFinal(M, 0);
    System.out.printf("M = %s%n", Hex.toHexString(M));

    // code used to generate the random k
    SecureRandom krng = new SecureRandom();
    BigInteger k;
    do {
        k = new BigInteger(256, krng);
    } while (k.compareTo(params.getN()) >= 1);
    System.out.printf("K = %s%n", k.toString(16));
}

To make sure that the value of $k$ is used directly within the algorithm I did some tests. A $k$ consisting of all FF bytes and a shorter $k$ both failed as expected . A $k$ consisting of 7F byte followed by all FF bytes does work. So the value $k$ within the FixedSecureRandom constructor is indeed directly used.

And finally the method of testing the deterministic result:

private static void testECDSASecP256k1sha256()
{
    X9ECParameters p = SECNamedCurves.getByName("secp256k1");
    ECDomainParameters params = new ECDomainParameters(p.getCurve(), p.getG(), p.getN(), p.getH());
    ECPrivateKeyParameters priKey = new ECPrivateKeyParameters(
        new BigInteger("ebb2c082fd7727890a28ac82f6bdf97bad8de9f5d7c9028692de1a255cad3e0f", 16), // d
        params);
    SecureRandom    k = new FixedSecureRandom(Hex.decode("49a0d7b786ec9cde0d0721d72804befd06571c974b191efb42ecf322ba9ddd9a"));

    byte[] M = Hex.decode("4b688df40bcedbe641ddb16ff0a1842d9c67ea1c3bf63f3e0471baa664531d1a");

    ECDSASigner dsa = new ECDSASigner();

    dsa.init(true, new ParametersWithRandom(priKey, k));

    BigInteger[] sig = dsa.generateSignature(M);

    BigInteger r = new BigInteger("241097efbf8b63bf145c8961dbdf10c310efbb3b2676bbc0f8b08505c9e2f795", 16);
    BigInteger s = new BigInteger("21006b7838609339e8b415a7f9acb1b661828131aef1ecbc7955dfb01f3ca0e", 16);

    if (!r.equals(sig[0]))
    {
        fail("r component wrong." + Strings.lineSeparator()
            + " expecting: " + r + Strings.lineSeparator()
            + " got      : " + sig[0]);
    }

    if (!s.equals(sig[1]))
    {
        fail("s component wrong." + Strings.lineSeparator()
            + " expecting: " + s + Strings.lineSeparator()
            + " got      : " + sig[1]);
    }

            // Verify the signature
    ECPublicKeyParameters pubKey = new ECPublicKeyParameters(
        params.getCurve().decodePoint(Hex.decode("04779dd197a5df977ed2cf6cb31d82d43328b790dc6b3b7d4437a427bd5847dfcde94b724a555b6d017bb7607c3e3281daf5b1699d6ef4124975c9237b917d426f")), // Q
        params);

    dsa.init(false, pubKey);
    if (!dsa.verifySignature(M, sig[0], sig[1]))
    {
        fail("signature fails");
    }
}

which is a direct copy of the test for SecP224k1 and SHA256, but of course with the different parameters.


Generating a random point on an elliptic curve over a finite field I have coded an implementation of elliptic curves in order to apply some of the ECC algorithms. However, in most of them, Alice needs to choose a point P on a given curve. What is the general procedure for selecting such a point?

Given a small example such as $y^2 = x^3 + x + 1$ over $F_{25}$, is there an algorithm to generate a random point on the curve? In my implementation points on this field are represented by polynomials, if that is relevant.

is there an algorithm to generate a random point on the curve?

By having a good random source like /dev/urandom you can generate a random point $R$ on a curve at least by two methods;

By using random scalar and scalar multiplication

Choose a generator point $P$ on the curve
Get random integer between $0 < k < \text{Order of the Group}$
Calculate $R =[k]P$ by scalar multiplication, prefably executing by double-and-add algorithm.

Using random element with sample rejection on the curve equation.

Choose a random element $x \in \mathbb{Z_{25}}$.

Check the equation $y^2 = x^3 + x + 1$ has a solution, i.e. it is a quadratic residue.
If there is no solution return to 1. step ( reject the sample)
Else, we have two solutions, $y$ and $-y$ (or one $y=-y$). These values can be found using the Tonelli-Shank algorithm and its generalizations.

Now use the random source to select $\bar{y}$ as $y$ or $-y$, or toss a coin.

Form the random point on the curve as $R=(x,\bar{y})$

Note that, the point at infinity cannot be expressed in affine-coordinates without some tricks. Therefore, this method cannot return the point at infinity. If the point at infinity is also required on the random selection, one can select it with an initial random. Select it within $\frac{1}{\text{Order of The Group}}$ probability. Then use the above.

If you are using SageMath then it has a function
random_element() and the explanation is given as
Return a random point on this elliptic curve, uniformly chosen among all rational points.
SageMath random_element() function uses the 2. method with an addition that it can also return the point at infinity, $\mathcal{O}$

In my implementation points on this field are represented by polynomials, if that is relevant.

The $\mathbb{F}_{25}$ is an Extension Field and it is usual to represent the elements of the field by the polynomial representation which is very advantageous on operations. As a result, the coordinates of points have polynomial representation.
From comments of OP

I used Sage to calculate the order of each point: (sagecell.sagemath.org/…) and it can be seen that even though the cardinality of the group is 32 the biggest order is 16. Is it just a matter of choosing an EC with prime cardinality?

The SageMath construction is not correct;
E = EllipticCurve(GF(25, 'x'),1, 1) provides this curve $y^2 = x^3 + x + 2$ not $y^2 = x^3 + x + 1$
One can construct as below;
    E = EllipticCurve(GF(25, 'x'), [1, 1])
    print(E)
    print(E.abelian_group())
    print ( E.cardinality())
    for i in E.points():
        print (i.order())

The construction EllipticCurve(Finite Field,[a,b]) is for the standard Weierstrass from $y^2 = x^3+ a x + b$ where $a,b \in F$ in which the curve defined. You only need to provide $a,b$, and $F$. The set of points commonly represented as $E_{a,b}(F)$
The abelian_group() functionality prints the abelian group structure of the group of points on this elliptic curve. The result is
$$\mathbb{Z_3} \oplus \mathbb{Z_9}$$
One should not call this function for a large group. There is a theory behind this and this can be found in a book such as Washington's book, however, the reference can go back to J. W. S. Cassels, 1966, Diophantine Equations with Special Reference To Elliptic Curves
Theorem: Let $E$ ben elliptic curve group over the finite field $\mathbb{F_q}$. Then $$E(\mathbb{F_q}) \simeq \mathbb{Z_n} \text{ or } \mathbb{Z_{n_1}} \oplus \mathbb{Z_{n_2}}$$ for some integer $n \geq 1$, or for some integers $n_1,n_2 \geq 1$ with $n_1|n_2$.


Given the first half of a SHA-1 hash, can you predict the second half? I know this applies to secure ciphers, but does this also apply to hashes?

Not without knowing anything about the message.

Each 32-bit word of the hash is a function of the current state plus one 32-bit word of the expanded message.

If the message is longer than 448 bits (512-bit block less 64 bits for length) then you would also need to know the output of the previous block, since it gets added to the output of the current block.


What is the difference between MAC and HMAC? In reference to this question, what are the "stronger security properties" that HMAC provides over MAC. I got that MAC requires an IV whereas HMAC doesn't. I also understood that MAC may reveal information about plaintext in contrast to HMAC. Is my understanding right?

What are other security properties of MAC and HMAC?

A Message Authentication Code (MAC) is a string of bits that is sent alongside a message. The MAC depends on the message itself and a secret key. No one should be able to compute a MAC without knowing the key. This allows two people who share a secret key to send messages to each without fear that someone else will tamper with the messages. (At least, if someone does tamper with a message, this can be detected by checking to see if the MAC is right.)

The term "MAC" can refer to the string of bits (also called a "tag") or to the algorithm used to generate the tag.

HMAC is a recipe for turning hash functions (such as MD5 or SHA256) into MACs. So HMAC-MD5 and HMAC-SHA256 are specific MAC algorithms, just like QuickSort is a specific sorting algorithm.

There are other ways of constructing MAC algorithms; CMAC, for example, is a recipe for turning a blockcipher into a MAC (giving us CMAC-AES, CMAC-DES, CMAC-PRINCE, and the like).

Some MAC algorithms use IVs. Others, such as HMAC, do not.

MAC algorithms should have the security property of being unforgeable under chosen-message attacks. Let's say that Alice and Bob share a secret MAC key (which they use when sending messages to each other), and that Eve is spying on them and sees both their messages and the corresponding tags.
Eve should not be able to use what she learns to fake valid tags. This should even be true if Eve can convince Bob to send specific messages.

For example, pretend Eve tells Bob to send the message:

  Dear Alice,

  Eve said "hi."

  Love, Bob

and then Eve sees the corresponding tag.
Eve should still be unable to "fake" the tag for the message:

  Dear Alice,

  Please give Eve $100 for me. I'll pay you back.

  Love, Bob

In addition to being unforgeable under chosen-message attacks (UF-CMA), HMAC has the stronger property of being a pseudo-random function (PRF). This means that if Eve doesn't know the key, then all of Bob's HMAC tags look like completely random strings of bits, even if Eve knows or even chooses what messages Bob sends. This is a stronger property because every PRF is UF-CMA (you can't guess a big random number), but not every UF-CMA MAC algorithm is a PRF (it's possible that for some MAC algorithm, all the tags begin with 10 zeroes --- not very random-looking at all, but the other bits could still be hard to guess without knowing the key).


What hash is concatenating with the data to be signed in TLS 1.3 CertificateVerify message? According to specification, to create data that will be signed with server private key for CertificateVerify message, we need to concatenate 64 space characters, the string "TLS 1.3, server CertificateVerify", null and the hash of all handshake messages to this point. During the handshake process, we choosing the cipher suite and signature scheme...
So, if the cipher suite is, for example, TLS_AES_256_GCM_SHA384 and the signature scheme is rsa_pss_rsae_sha256 (different hash algorithms), hash of which algorithm should be used as handshake hash in data to sign, SHA-384 or SHA-256?

rsa_pss_rsae_sha256 is the signature scheme that defines to use of the SHA-256 during the RSA-PSS signature algorithm.
Since Rabin-Signature Scheme, which is the first true signature scheme, the security of the signature is a part of the hashing a message and that enables us to sign arbitrary long messages, too. The rsa_pss_rsae_sha256 will use SHA-256 to hash the message before signing.
The RSA-PSS also needs a hash function to use in its Message Generation Function 1 (MGF1). RSA-PSS defined in RFC 8017 also known as RSASSA-PSS. The SHA-256 will be used in MFG1, too.
TLS_AES_256_GCM_SHA384: AES-GCM doesn't need the SHA-384. The SHA-384 suffix;

In Pre TLS 1.3, the appending hash function SHA-384 defines PRF to use in key derivation and Finished and HMAC when the cipher suites required.

For cipher suites ending with _SHA384, the PRF is the TLS PRF
[RFC5246] with SHA-384 as the hash function.

In TLS 1.3: TLS 1.3 finally defined a KDF; HKDF that replaces PRF and there is no more need for HMAC since all modes are authenticated encryption modes that use CCM, GCM, and Poly1305 message authenticators.
The hash function in the cipher suite definition represents the hash function that is used to hash the handshake messages for the Finished message and HKDF.

What hash is concatenating with the data to be signed in TLS 1.3 CertificateVerify message?

Therefore it is SHA-384


URN for ECDSA signature algorithms (including hash algorithm) The URN form ECDSA signature algorithm is urn:nist-gov:ecdsa.

But I am not able to find a named URN for algorithm SHA1withECDSA or SHA256withECDSA.

Up to now I've found the xmldsig URL for this algorithms: http://www.w3.org/2001/04/xmldsig-more#ecdsa-sha1 and http://www.w3.org/2001/04/xmldsig-more#ecdsa-sha256

And I have the option to generate the URN with its OID, according to RFC3061: urn:oid:1.2.840.10045.4.1 and urn:oid:1.2.840.10045.4.3.2

I could even create my own version of its URN as something like urn:nist-gov:ecdsa-sha1 and urn:nist-gov:ecdsa-sha256

But, is it a named standard URN for signature algorithms SHA1withECDSA and SHA256withECDSA?

According to the IANA registry at https://www.iana.org/assignments/urn-namespaces/urn-namespaces.xhtml, there is no nist-gov URN namespace.  Outside obscure antisocial protocols like RFC 2802 there is no reason to try to use this URN namespace.  You appear to have gotten these URNs from a defunct internet-draft.  If you're using XML signatures, as you appear to be doing, then you can use use the URI http://www.w3.org/2001/04/xmldsig-more#ecdsa-sha256 like RFC 4051 specifies.

(But consider throwing XML signatures in the garbage—if not XML too.  Just sign binary blobs with a fixed signature scheme baked into your application; using XML signatures is asking for trouble.)


What is the proof that a hash output contains random binary numbers I have heard quotes by many that a SHA-512 hash output is random.

Does anyone know what method was used to come to this conclusion? If it is not randomized, how could that be shown?

Whilst the random oracle model(1) is the theoretical construct that should produce random 'looking' hash output, the scientific principle also requires that we test the hypothesis for proof.

So let us assume a simple set of inputs to the function. If the null hypothesis is that the output will appear random(2), the output will have certain testable properties:-

For a simple counter input, we expect that any output bit will all uniformly distributed with $P(X = 0, X = 1) = \frac{1}{2}$, and for multiple conditional bits, $P(X | Y) = \frac{1}{2}$. These formulae extend as $P(\dots)= \frac{1}{2^n}$  and $P(\dots|\dots)= \frac{1}{2^n}$  for $n$ bit tuples.
For randomly entered bits, we can count the numbers of set input and output bits and determine whether an avalanche effect is occurring. We expect that 50% of the bits will change per any random input. The actual probability mass function of the changes is expected to be Binomial, tending to a Normal probability  distribution as the block width $(n)$ increases. We'd expect $\mu = 0.5n, \sigma = 0.5 \sqrt{n}$.
Standardised randomness testing (Diehard, NIST etc.) can also be used, and we expect SHA-512 to pass all of them whilst hashing simple inputs. There is also no specialised distinguisher and can separate the hash output from a pseudo random sequence (3).

This 'random' hypothesis has so far held in the laboratory. So in your parlance, the output is random, and no one has yet proved otherwise. Some of these experiments might have shown it up otherwise, depending on the degree of bias.

Notes.

(1) A very imperfect model, as explained here.

(2) By random output, I take it you mean independent and identically distributed bits, not easily related to the input, or each other.

(3) Just be aware that these lab tests cannot determine any form of security measure.


Ed25519 PKCS8 private key example from IETF draft seems malformed Malformed PKCS8 Key

Algorithm Identifiers for Ed25519, Ed448, X25519 and X448 for use in the Internet X.509 Public Key Infrastructure § 10.3. Examples of Ed25519 Private Key states the following:

An example of the same Ed25519 private key encoded with an attribute
and the public key:

-----BEGIN PRIVATE KEY-----
MHICAQEwBQYDK2VwBCIEINTuctv5E1hK1bbY8fdp+K06/nwoy/HU++CXqI9EdVhC
oB8wHQYKKoZIhvcNAQkJFDEPDA1DdXJkbGUgQ2hhaXJzgSEAGb9ECWmEzf6FQbrB
Z9w7lshQhqowtrbLDFw4rXAxZuE=
-----END PRIVATE KEY-----

The same item dumped as ASN.1 yields:

  0 114: SEQUENCE {
  2   1:   INTEGER 1
  5   5:   SEQUENCE {
  7   3:     OBJECT IDENTIFIER '1 3 101 112'
       :     }
 12  34:   OCTET STRING, encapsulates {
 14  32:     OCTET STRING D4 EE 72 DB F9 13 58 4A D5 B6 D8 F1 F7
                 69 F8 AD 3A FE 7C 28 CB F1 D4 FB E0 97 A8 8F 44
                 75 58 42
       :     }
 48  31:   [0] {
 50  29:     SEQUENCE {
 52  10:       OBJECT IDENTIFIER '1 2 840 113549 1 9 9 20'
 64  15:       SET {
 66  13:         UTF8String 'Curdle Chairs'
       :         }
       :       }
       :     }
81  33:   [1] 00 19 BF 44 09 69 84 CD FE 85 41 BA C1 67 DC 3B
              96 C8 50 86 AA 30 B6 B6 CB 0C 5C 38 AD 70 31 66
              E1
       :   }

The last bit doesn't seem to be valid be a valid PKCS8 private key. Here's the ASN.1 definition for private keys from PKCS8:

PrivateKeyInfo ::= SEQUENCE {
  version                   Version,
  privateKeyAlgorithm       PrivateKeyAlgorithmIdentifier,
  privateKey                PrivateKey,
  attributes           [0]  IMPLICIT Attributes OPTIONAL }

The ASN.1 definition has one context-specific tag with a tag number of 0 whereas the private key my first snippet has has two context-specific tags - one with a tag number of 0 and one with a tag number of 1.

Do the ASN.1 standards permit the appending of arbitrary strings to an ASN.1 encoded object? Because it seems that that's what the "private key encoded with an attribute and the public key" is doing...

Alternate Approaches

It seems to me that if the authors wanted to make the private key include the public key they could add the public key live in the PrivateKeyAlgorithmIdentifier. Quoting the definition for that:

PrivateKeyAlgorithmIdentifier ::= AlgorithmIdentifier

AlgorithmIdentifier  ::=  SEQUENCE  {
     algorithm               OBJECT IDENTIFIER,
     parameters              ANY DEFINED BY algorithm OPTIONAL  }

(AlgorithmIdentifier is defined in RFC5280)

DSA private keys do this. The DSA Parameters $p$, $q$ and $g$ are defined in the parameters field of the AlgorithmIdentifier. So it's not like use of that field isn't without precedent (see RFC5912, for example).

Another possibility: just hijack ECPrivateKey. Just make it so Ed25519 can only be utilized with a NamedCurve and parse publicKey and privateKey differently (as specified in RFC8032) when Ed25519 is being used...

That example private key is not encoded with PKCS#8, but with the format described in RFC 5958, which is supposed to replace PKCS#8 (at least, in IETF parlance, RFC 5958 "obsoletes" RFC 5208, which is a copy of PKCS#8 v1.2). The ASN.1 type if called OneAsymmetricKey:

 OneAsymmetricKey ::= SEQUENCE {
   version                   Version,
   privateKeyAlgorithm       PrivateKeyAlgorithmIdentifier,
   privateKey                PrivateKey,
   attributes            [0] Attributes OPTIONAL,
   ...,
   [[2: publicKey        [1] PublicKey OPTIONAL ]],
   ...
 }

The structure is similar to that of PrivateKeyInfo in PKCS#8, but with the extra publicKey field (optional) at the end. Also note that the version field, which is an INTEGER, has value 0 for PKCS#8, but value 1 for OneAsymmetricKey; this is meant to allow some level of backward compatibility, in the sense that a decoder for OneSymmetricKey can accept an encoded PrivateKeyInfo, and will use the version field to apply the proper semantics (i.e. to decode the contents of the private key blob).

I must say that I have, so far, never encountered a OneSymmetricKey structure in the wild. The openssl command-line tool encodes keys in PKCS#8, and applications tend to expect that. RFC 5958 has status "proposed standard", but sometimes you cannot enforce acceptance.


Helper data authentication in PUFs As I understand, PUFs work by using two procedures: generation and reproduction. Generation reads a value $w$ from a fuzzy source and generates a key $R$ and helper data $P$. Then, in the reproduction procedure, it reads $w'$ from the fuzzy source and, using $P$, is able to recover $R$.

My question is: this seems to assume that $P$ can be stored safely and can be authenticated, since if a attacker changes the value $P$ that is stored then he can force the system to use a different key. How can this be done, if you don't have a key in the first place? Or am I missing something?

(I have followed the notation from A Soft Decision Helper Data Algorithm
for SRAM PUFs by Maes, Tuyls and Verbauwhede.)

It is very similar to how we authenticate ourselves to a website. During registration, the website must store enough information to, at some time in the future, convince itself that the person trying to authenticate now is the same person who registered at some time in the past. For online services, this typically involves storing some function of the password. The online service also wants to make sure that the stored information is stored safely (i.e., unauthorized entities cannot get it) and authenticated (i.e., no unauthorized parties can change it). Otherwise authentication would fail.

With a PUF, it is almost the same. You register the PUF with the system by extracting $R$ and $P$ from $w$. $R$ and $P$ would then be stored in, for example, a database. When the PUF is used again to authenticate, the service would read $w'$, pull $P$ from the database and run the reproduction procedure to get $R'$. It could then pull $R$ from the database and see if $R==R'$. If so, authentication is successful and access is granted.

How you protect $R$ and $P$ from the generation phase is up to you. It also depends on how paranoid you are, how valuable the service is, your threat model, etc. For some, simply storing them in a database that (hopefully) only they have read access to is fine. Others might want to encrypt and sign the values.

It should be noted that $P$ is a public value. It does not need to be kept secret for the system to be secure. As you noted, however, if someone tampers with $P$, they could trick the system into authenticating the wrong party. Equivalently, if I change the hash stored in a database with login credentials, I can now become that user.

Active Attacker Update

Things become tricky when you allow your adversary to modify $P$. AFAIK, there are no guarantees that the attacker cannot modify $P$ in a devistating way (e.g., to publically reveal $R$). And I am not aware of any PUF research to mitigate the problem.

Fortunately PUFs and biometrics are very similar.

Both are a noisy source
Both require fuzzy extraction to be used to handle the noise

Given that, hopefully the following will at least help to solve the problem.

In "Robust and Reusable Fuzzy Extractors" by Boyen in the book "Security with Noisy Data", Boyen tackles a similar problem. From the chapter:

  Unfortunately, ordinary fuzzy extractors do not address the issue of an active adversary that can modify $P$ maliciously, either on the storage server or while in transit to the user.

I don't fully understand the details of the work yet, so I don't feel it wise to try and describe the algorithms and protocols.

NOTE: It looks like much of that chapter was taken from a paper by Boyen and some of his colleagues titled "Secure Remote Authentication using Biometric Data". I have not read the paper to confirm that all the detail you might be looking for is there, however.


Understanding math behind RSA key derivation I was reading through the key derivation for RSA. Here are the steps per wiki -

Select strong primes $p$ and $q$ such that $pq = n$
$\phi(n)$ = $(p-1)(q-1)$
select $e$ such that $e$ and $\phi(n)$ are coprime.
Select $d$ such that $ed mod(\phi(n)) = 1$

I do not understand why the $\phi(n)$ is even needed. Why can't we just skip the step and say -- select $e$ such that $e$ and $n$ are coprime.

Would it not work? Is the math somehow dependent on that? If so what is it?

Also why should $e$ be coprime to $\phi(n)$?

To clarify my main question was about why e needs to be relatively prime to phi(n). Would it not work if its relatively prime to n?

After following poncho's answer -- Lets say I want to pick e relatively prime to n. In his example N = 77. Lets say e = 4 then d = 19. So $edmod(N) = 1$. Of course e is not a prime number here, but the spec does not say e should be prime.

It would appear that the $\phi(n)$ is chosen so that its smaller than N giving an opportunity to find the $e$ and $d$. So why choose $(p-1)(q-1)$? Why can't it be some other operation to make the result smaller than n?

I know I am missing something here and its not clicking. Hope some one explains it.

Well, if $e$ is not relatively prime to $\phi(N)$, then there won't be any such $d$; in fact, there generally won't be a unique decryption.

For example, let us consider the toy example $N = 77$ and $e=3$.  Note, that $\phi(N) = 6 \times 10 = 60$ is not relatively prime to $e$.

Then, let us assume that we receive a ciphertext $41$, and we need to find the plaintext $P^3 \equiv 41 \pmod{77}$.  The problem is that there are three; we have $P=13$; as $13^3 \bmod 77 = 41$.  However, we also have $P=24$; as $24^3 \bmod 77 = 41$ as well.  pick a plaintext $P=13$ and compute the corresponding ciphertext $C=13^3 \bmod 77 = 41$.  $P=68$ also works.  So, which is the right one?  The decryptor has no way of knowing.

We avoid this problem if $e$ and $\phi(N)$ are relatively prime.


Infinite one time pads using a pseudorandom hash function Paul Christiano writes (source):

  I’ll assume that we have some 256 bit cryptographic hash function F [...] The first important observation is that a 256-bit shared secret allows Alice and Bob to talk for as long as they want, by just using their secret to create a new pseudorandom pad for each message. That is, if Alice and Bob share a secret s, then Alice can send a message m by picking k at random, and sending the pair (k, F(sk) ⊕ m). It’s easy to confirm that Bob can still get the message, and if F is random then this is secure.

This is confusing to me. I was under the impression that there is no way of using a one time pad based on a shared secret of $n$ bits to transmit securely more than $n$ bits but this seems to imply it is possible by sending messages with $k=1,2,\dots$

What am I misunderstanding?

This is called a stream cipher.  It is a practical instantiation of the one-time pad model, where we encrypt a message $m$ with a single-use pad $p$ by using the ciphertext $c = m \oplus p$.

When $p$ is generated from a short key $k$ by $p = F(k)$, obviously $c$ and $m$ are not technically independent—we can't say of the probabilities that $P(m \mid c) = P(m)$, because obviously some pads are impossible—but the advantage the adversary has at breaking the cryptography knowing that we used $F(k)$ is limited by their advantage at distinguishing $F(k)$ from a uniform random bit string.

If $k$ is uniform random and $F$ is, e.g., ChaCha or SHA-256, the adversary has no hope of doing this without a breakthrough in cryptanalysis.


For the theoretic scenario of a brute force attack, how would you know if you succeeded? That is something I never understood:

If you managed to brute force an AES encrypted text, how would you know you cracked it? After every attempt, you wold have to compare the text to an English dictionary right? That would take ages.

In the scenario of an AES encrypted program, you would get hexadecimal code every time even if you succeeded right? So you would not even know if you cracked it.

So i want to know, how do the best AES cracking methods of today work?

If you managed to brute force an AES encrypted text , how would you know you cracked it ? After every attemt , you wold have to compare the text to an english dictionary right ? That would take ages .

Yes, thats why you could first check if most values are mapped to normal ASCII letters. If they do, then you could try that for more blocks, and when you got enough confidence you can check if those are most likely proper words, for example with dictionary. Since only marginal number of keys would result in such data, it wouldn't matter.

  In the scenario of an AES encrypted program , you would get hexadecimal code every time even if you succeeded right ?

Every program in virtually any OS has a structure to it. You would find static elements, which would make checking plaintext even simpler: try to read file header, to see if this is valid header.
Even if your specific code had no header, you could still easily predict that this code starts with 0x55 0x89 0xE5 (push ebp;mov ebp,esp), as thats typical procedure entry code (of course this is specific to architecture, example is given for x86).

Very same continues for virtually every data you can invent except for plain random data which is never reused anywhere.

  So i wanna know , how do the best AES cracking methods of today work .

There are no AES cracking methods that we know of. There are some theoretic attacks on AES which are nowhere near being applicable. Problem in cracking any modern cipher is cost of trying all keys, check if decryption is right can be easily checked on most data.


Simulation-based proofs and universal composability proofs I recently read Ran Canetti's famous UC paper but I'm still trying to wrap my head around the concepts. I think this answer has me confused a bit, particularly where it says

  The stand-alone simulation-based definitions give you security under sequential  composition, and universal composability and its variants give you security under concurrent composition

What does this mean, exactly?

Moreover, how does a UC proof work? Is the following correct:

A UC proof works if you show that the environment can not tell if it is interacting with the real adversary and the real protocol, or the simulator/ideal adversary and ideal functionality.
To this end, for the proof one must define, for each real adversary, a simulator.

My (other) question is, how do we define this simulator? In proofs, I only ever see the simulator being defined by how it behaves when it receives a message from the ideal functionality and how it behaves when it receives a message from the adversary? But why is it never described by how it behaves when it receives a message from the environment?  The environment wants a two-way interaction with the real adversary/simulator right? So do we have to define the simulator so it knows how to respond and interact with the environment?

Also, I would be most grateful if you should show me example proofs in the UC framework. The shorter/easier the better, just so I can get my head around it. I would absolutely love a paper like Shoup's tutorial on game hopping proofs.

Many thanks!

What does this mean, exactly?

The purpose of the environment is to model "everything else happening in the universe" besides the protocol execution. In the UC model, the adversary is allowed to talk to the environment during the execution of the protocol. So UC security means "security no matter what else is going on in the world, even if other things are going on in the world during the protocol execution." For instance, the adversary could be running instances of other protocols (or the same protocol), against the honest parties, who could be using related inputs, etc.

There are several flavors of standalone security definitions, not all equivalent. But for the purposes of this question, think of standalone security as exactly the same as UC security, except that but the adversary is not allowed to talk to the environment during the protocol execution. They can talk only before and after the execution. In this model we cannot use the environment to capture an adversary who is doing "other things" during the execution of our protocol. We can model adversaries who run other protocols with honest parties on related inputs after or before our execution, but not during.

A protocol supports sequential composition if it is secure when many instances are executed sequentially, possibly on related inputs. It's easy to express this in both standalone and UC model. You can capture sequential composition by just having the adversary pass along its state between executions. Pre/post-execution communication with the environment is enough to do this, so it's fine in the standalone model.

A protocol supports concurrent composition if it is secure when many instances are executed concurrently, possibly on related inputs. It is not possible to express this in standalone -- only in UC. So standalone security does not guarantee this property, and there are indeed counterexamples of standalone-secure protocols that are insecure when run concurrently.

This restriction of standalone security (i.e., not talking to the environment during the protocol execution) is actually used in security proofs in the standalone model. A common technique for the simulator is to "rewind" the adversary, meaning to revert his internal state back to a previous time in the protocol. This is safe in the standalone model, because the adversary is detached from the environment. But it's not valid in the UC model because if you're trying to rewind the adversary back to round $r$ of the protocol, the adversary might have already spoken to the environment at round $r+1$. The environment cannot be rewound, so this would cause the environment to notice the difference between real & simulated --- this technique cannot be used in a UC security proof.

  A UC proof works if you show that the environment can not tell if it is interacting with the real adversary and the real protocol, or the simulator/ideal adversary and ideal functionality.

Yes.

  To this end, for the proof one must define, for each real adversary, a simulator.

Yes, but there is a shortcut. Take any environment and adversary that you wish to consider, and imagine logically moving the adversary into the environment so that all that is left as a syntactic "dummy adversary". The dummy adversary just says whatever the logical adversary (living inside the environment) tells it, and also reports back all the messages it sees as they are received. This doesn't change the interaction, it only repackages the parts. So every UC interaction can be expressed in terms of an equivalent interaction where the adversary is such a dummy adversary. Since UC security quantifies over all environments, it just suffices to prove security with respect to a dummy adversary.

  My (other) question is, how do we define this simulator? In proofs, I only ever see the simulator being defined by how it behaves when it receives a message from the ideal functionality and how it behaves when it receives a message from the adversary? But why is it never described by how it behaves when it receives a message from the environment? The environment wants a two-way interaction with the real adversary/simulator right? So do we have to define the simulator so it knows how to respond and interact with the environment?

Perhaps this question is cleared up with the understanding of dummy adversaries. When you imagine an interaction with a dummy adversary, you lose the distinction between the environment and the logical adversary embedded in the environment. So the receiving a message from the [logical] adversary / receiving a message from the environment really refer to the same thing. We just know without loss of generality that all communication with the environment will be of the dummy-adversary form: environment says "here is a message to send in the protocol", dummy adversary / simulator has to report back all [simulated] protocol messages that are seen.

  Also, I would be most grateful if you should show me example proofs in the UC framework. The shorter/easier the better, just so I can get my head around it.

Nothing comes immediately to mind. You might want to search for "UC security" + "lecture notes". Also you may be interested in the following recent paper that presents a simplified model of UC that nevertheless is sufficient for 99% of use cases:

Ran Canetti and Asaf Cohen and Yehuda Lindell: A Simpler Variant of Universally Composable Security for Standard Multiparty Computation, CRYPTO 2015.


CBC-MAC just to verify integrity I have a message and I want to verify its integrity and authenticity.

I have a shared secret (key) that is not used for other encryption.

Is it safe to send a plaintext message containing all the data I want, and to verify its integrity and authenticity using CBC-MAC?

I mean - of course the data is not secret, but do I have a risk of someone changing the message / MAC and messing with my message? Is it possible to deduct the Key?

Yes, this is exactly what a message authentication code is for.  Its job is to prevent an attacker from tampering with your message, or from forging completely bogus messages.  For a secure MAC, it should not matter what these messages contain.

(And no, a secure MAC cannot compromise your key; if it did, it would by definition not be secure, since an attacker could use the key to forge messages.)

However, you probably don't want to use classic CBC-MAC if you can avoid it, since it's not provably secure when used on arbitrary messages.  (It is secure when the messages are prefix-free, i.e. when no valid message can be a prefix of another valid message, but this can be somewhat tricky to ensure.)  It's better to use CMAC or one of the other modern cipher-based MACs (OMAC2, PMAC, etc.) instead; unlike CBC-MAC, these have security proofs that don't require any special assumptions about the messages.

Also note that a MAC does not prevent an attacker from:

blocking or delaying the delivery of valid messages,
re-sending verbatim duplicates of previously captured messages, or
tampering with any metadata (such as sender or receiver IDs) that is not included in the MAC input.

To protect against such attacks, you'll likely want to include an incremental message ID and/or a timestamp in your messages, as well as some way of identifying who sent the message and to whom.  You also need to make sure that these extra fields are actually included as part of the MAC input, so that the attacker cannot change them.

Ps. When combining encryption with a MAC, the reason why we usually encrypt the message first is actually the opposite of what you may think: it's not meant to hide the plaintext from the MAC, but to protect the encryption scheme from chosen-ciphertext attacks by ensuring that only ciphertexts with a valid MAC are ever passed to the decryption code.

(Also, not all MACs are guaranteed to be privacy-preserving, which means that, if you calculate the MAC on the plaintext and then transmit the MAC output unencrypted, an attacker might theoretically learn something about the plaintext just by observing the MAC output.  That said, most commonly used MACs — including CBC-MAC, when used properly — are privacy-preserving.  And in any case, this doesn't matter for you, since you're transmitting the whole message unencrypted anyway.)


Finding scalar that creates a point with zero X-coordinate for popular elliptic curves In signature creation in ECDSA we use a nonce, commonly identified as $k$.
To create an ECDSA signature, we need to calculate two integers, commonly identified as $r$ and $s$.
$r$ is simply the X-coordinate of the base point multiplied by $k \bmod n$.
$s$ is the actual signature, so it's $s = k^{-1}\cdot(z+d\cdot r)\text{ mod }n$, where $z$ is the number signed (usually the hash value as a big-endian integer), $d$ is the private key, and $n$ is the order of the base point.
Now, if a curve includes points with X-coordinate equal 0, then there may exist such a scalar that when multiplied by the base point it will result in a point that has such coordinate. That's true for some popular curves like NIST P-256, points

$\small{(0, \texttt{0x66485c780e2f83d72433bd5d84a06bb6541c2af31dae871728bf856a174f93f4})}$ and
$\small{(0, \texttt{0x99b7a386f1d07c29dbcc42a27b5f9449abe3d50de25178e8d7407a95e8b06c0b})}$

lay on the curve, and the curve has cofactor $1$, so we know that there is such $k$ that will generate them.
The ECDSA algorithm does require a retry with a different $k$ if either $r$ or $s$ ends up $0$, but I'd like to test if that code actually works correctly.
My questions:

Do we know of $k$ values for the popular curves (like the NIST P-256) that create points with $x = 0$?
Is there an algorithm to find them?
Same for the $s$ value: do we know of a triplet of $k$ value, message, and the private key that will result in $s = 0$ when using one of the popular curves?
If so, how would I go about finding it?

I did try a brute force approach (keep adding a base point to an accumulator, check fox x becoming zero), but that's too slow even for the likes of secp112r2.

No (See 2.). An alternative way to test a library could be to change the base point. You can find the point with x coordinate equal to zero, multiply it by a random $r$ and then use the result as the base point of ECDSA with $k=r^{-1}$.
This is equivalent to solving an ECDLP (discrete logarithm problem) which on standard curves, is believed to be hard (practically unfeasible)
This is possible.
$s=k^{-1}(z+rd)$ which is 0 when $(z+rd)=0$. If you can freely choose $z$ (e.g. the library receives it as parameter, and doesn't compute it internally) then you can choose $z$ such that $z=-rd$. Otherwise, you can select $d$ such that $d=-\frac{z}{r}$.

Note that another corner case that I test on implementations of ECDSA is where the $x$ coordinate of $k*G$ is greater than the $G$'s order. This again is done with the same trick I described in point 1.


Implementation of garbled circuits using RSA I was just reading these notes  on garbled (Yao) circuits and I just stuck trying to figure out how an implementation of Table 1 would work using RSA encryption. In RSA the public key is $(n,e)$. So for the first row, for example, I guess that ${\rm Enc}_{k_1^0}(k_2^0)$ means: "encrypt the "message" $k_2^0$ with the key $k_1^0$". So does the value of $k_1^0$ stand for $n$ or $e$ of RSA? What am I missing here?

The notation you are seeing is for symmetric crypto. Garbled circuits typically use symmetric crypto since it can and symmetric crypto is fast. You may be able to do garbled circuits with asymmetric crypto, but it is definitely non-standard and may have subtle issues.


Is this approach to generating a "random" number from a sha512 hash effective? I'm looking to run a small raffle but i'd like people to be able to verify that the number chosen was fair. I know some sites use a "Provably Fair" system to achieve this where user input is combined with a secret string which is then hashed to determine the winner. Once the secret string is released, participants can verify using the hash that the correct winner was chosen.

From a sha512 hash a "random" number from 0-n (n varies in length but is 255 at most) should be generated to determine the winner. This is what I thought up:

Creating an array of n length and inserting pairs of characters that can appear in a sha hash. If n was 255 for example, the array would have: array('aa','ab','ac'...'fd','fe','ff'...'97','98','99'). Basically it'd have every combination of two characters using a-f and 0-9.

It'd then look at the first two characters of the hash and use array_search to see if that pair exists in the array. If it does, it's index is the number picked, otherwise it moves over to the next pair of characters and searches those. In the rare scenario it doesn't find a match it'll continually hash itself and use the new hash returned to continue the search.

$values = array('a','b','c','d','e','f','0','1','2','3','4','5','6','7','8','9');
    $numbers = array();
$ENTRANTS = 100;
    $rand =  md5(uniqid(rand(), true));
$hash = hash('sha512',$rand);

$values_index = 0;
    $current = $values[$values_index];
$options = 0;
    while ($options < $ENTRANTS){
     $remaining = ($ENTRANTS - $options > 15)? 16: $ENTRANTS-$options;
     for ($n=0; $n < $remaining ;$n++){
      array_push($numbers, $current . $values[$n]);
      $options++;
    }

    $values_index++;
     $current = $values[$values_index];
}

$outcomes = array();
    $winning = null;
$i = 0;

while (empty($winning)){

    while ($i+1 < 64 && empty($winning)){
        $combo = $hash[$i] . $hash[$i+1];
      $number = array_search($combo,$numbers);
        if ($number !== false){
       $winning = $number;
        }

        $i++;
    }

    if (!empty($winning)){
      echo "
" . print_r($numbers,true) . "
";
      echo $hash . "
" . $winning;
     }
     else {
      echo "re-hashing" . "
";
      $hash = hash("sha512",$hash);
      $i = 0;
    }
}

This is working when tested but I'm unsure if it is effectively generating a random number. Are the characters in a sha512 hash for the most part evenly and unpredictably distributed? If you can see any issues with this or have any advice on how it could be improved please let me know!

In general, your way to select one of the entries seems unnecessary complicated. As fgrieu pointed out, you should be fine by reducing the hash value modulo the number of participants (But with $n$ people, you calculate $h$ mod $n$, and assign the numbers from $0$ to $n-1$).

An important question though, is how you determine the input to your hash function. If you seed it with something random, people can't really be sure you didn't cheat (by trying out different seeds).

In order to provide confidence, you might want to do something like this:

Initially you provide a commitment to some secret value of your choice. After everything is done, you can unveil the commitment and show the secret value.
Then you run your raffle. People can sign down their names, and you keep the list public. This way they can make sure that their name is in the raffle. The list index also gives the "lucky number" to each participant.
Afterwards you first reveal the secret value by publishing the decommitment. Then you create a long bitstring: concatenate all the names in the list and the secret value. Use this bitstring as input to a hash function (SHA512 does the trick, but with an final result  of at most $2^8$ possibilities, any cryptographic hash function should work). Calculate the number modulo the number of participants. If you want results from $1$ to $n$ instead of $0$ to $n-1$, then just add 1 (or interpret the $0$ as $n$).

Why can no one cheat in this scenario?

You can't cheat, because your input to the function is fixed before the raffle starts (at least if your commitment scheme is binding; btw. you can also just use something like "I encrypt my name with AES. The commitment is the ciphertext and the secret value is the used key")
The other people can't cheat either, because without knowledge of your input they should not be able to change the outcome in their favor on purpose.
Since the growing list of names changes with each additional entry the hash result, no one could predict the outcome before the last person entered his name.
The worst attack scenario I can think of, is that you work together with the last person added to the list. This person could try out different variations of his name and calculate the result with knowledge of the secret. But right now I can' think of anything to solve this problem.


Blockwise Montgomery multiplication I have to implement a 256*256 bit Montgomery multiplier for pairing computations. The straightforward approach is to use a bit-serial version, but I would like to utilize the built-in 64*64 bits multipliers on soft cores of modern FPGA devices, therefore I need a blockwise implementation (64 bits each). Two choices for implementation are:

Get a 512-bit product and then apply Montgomery reduction.
Reduce the intermediate products (128 bits) in each step using Montgomery reduction.

Which strategy is faster? If intermediate results are reduced in each step, then what should be the value of $R$: is it $2^{256}$ or $2^{64}$?

As I said above, I feel the question is bit off-topic here. However, there does not seem to be too good a place in SE for questions that combine mathematics and programming on VHDL, where target is obviously something cryptography related.
Most questions regarding FPGA are seen in electronics.stackexchange.com.

Montgomery reduction in Wikipedia is useful description of Montgomery reduction. The value of R you usually use is the same than word size used in processing. In your case, it could be $2^{256}$ or $2^{64}$ depending on how you implement the montgomery multiplier. If you have multiple $64*64$ bit multiplier units, you may want to use them in parallel, to perform large multiplications and/or montgomery reductions at once.

Assuming you had two multipliers available, one way around this would be using one multiplier for 64*64 multiply and another for montgomery reduction of previous 64*64 multiply, and thus R would be $2^{64}$. Then you would need to build 256*256 from e.g. 16 executions of 64*64 multiply. But, the algorithm, approach and processing pattern somewhat depends on how many multiplier you have available. Notice that you do not need to use rectangular size: you may build 128*64 montgomery step (from e.g. 4 multipliers) and you can use it to build 256*256.

The speed of different implementation decisions in the end depend on your target platform. Likely you need to design and implement appropriate benchmarks yourself.

Coming back to the original question. Overall, it is often most efficient to work locally i.e. inside one 64 bit / 128 bit word, i.e. to try to constrain each handling path to process word at time. (I.e. choice 2.)
Note: you cannot restrict all operations to work in 128-bits, but occasionally need to handle carries etc. concerns.

Advice

Or how to proceed in practice.

In case you are experienced with "ordinary" programming languages in addition to the HDL language you use (often verilog or VHDL), I would propose first trying to make functional model of the multiplier in one of usual programming languages and comparing the results against some existing big number multiplier code, because it may appear that it is not always completely straight forward to build correctly functioning processing step.

There may be inexpensive already existing design for your FPGA, available for licensing with reasonable cost. It may be superior option compared to doing it your self. (For SW implementations I also recommend using one of existing libraries, and in fact for HW this same choice usually exists as well.)

If side-channel attacks (such as timing) are considerable threat in your use, you'll need to carefully consider the side channels during the implementation. Standard "basic" implementation of montgomery reduction is not side channel free.


Transmit half the bits of the $g^a$ and $g^b$ as MITM countermeasure in DH key exchange? I remember this trick from one of my crypto courses way back then, but I can't find the details, and I'm unable to figure out the logic behind it.

I'm talking about a countermeasure to the MITM attack on "plain" (textbook, unauthenticated) DH key exchange.  It was something like Alice and Bob compute $g^a$ and $g^b$ (respectively, where $a$ and $b$ are their randomly chosen not-to-be-disclosed values), but first transmit half the bits, and only after receiving the first half bits of the other party, then transmit the remaining half (example, if Alice's $g^a$ is 0x12345678, then transmit first 0x1234, and only after receiving Bob's first half, then transmit 0x5678).

My memory of the description of such trick is that Mallory (the MITM attacker) somehow needed to commit to something based on the first halves, but somehow what Mallory needed required the complete $g^a$ and $g^b$, which, by the time he/she gets those, it is too late and he/she cannot change the value now without being detected.

Does this ring any bells to someone?  What part am I missing?  I can't see how simply transmitting the first half, and only transmitting the second half after receiving the other party's first half would prevent Mallory to play MITM --- he/she just plays the game with Alice and Bob separately.

Thanks!

The question's technique does not prevent a Man in the Middle attack, for the reasons stated in the question. Nothing cryptographic can, under the question's assumption. Pre-existing trusted material allows that, and is used to that effect in authenticated DH.

What the question's technique achieves is

Give more insurance to Alice that the shared secret that she will use can't have been chosen to have certain properties, because the other party's secret exponent $b$ can't be chosen with knowledge of the full $g^a$ chosen by Alice. When doing the normal way (where Alice reveals $g^a$ in full before receiving $g^b$), the party communicating with Alice (no matter who) could chose $b$ such that $(g^a)^b$ has (for example) its low-order 20 bits set to zero, then send the corresponding $g^b$ to Alice; exploring $b$ sequentially, this require only about a million multiplications.
Make it harder or impossible to tell if Alice has chosen a somewhat poor value of $a$ before going as far as the second message sent by Alice, so that analysis of logs of failed connections will have more chance to reveal an attack forcing repeated connections until such poor choice (no answer from Bob on the first message can simply mean that Bob is offline; no answer on the second message, repeatedly, can't have this simple explanation and should raise alarm).
More generally, lessens the asymmetry in timing of information disclosure between the originator that sends the first message, and the other party.

That might guard against some attacks, or make some security proofs possible.

For example, the question's technique might at least partially mitigate an attack where Mallory, actively performing MitM during key exchange, tries to make Alice and Bob compute a common shared secret that Mallory also knows, which then allows Mallory to passively eavesdrop later direct communication between Alice and Bob, encrypted under a symmetric key derived from the shared secret. There's an illustration in the second section.

If additionally the convention exists that the originator sends the high half first, while the other party sends the low half first, then:

Assuming authenticated symmetric encryption from the shared DH secret, this blocks a denial of service by reflection attack where Alice is made to communicate with herself by always sending back to Alice whatever message she sends.
This could have some (hopefully strengthening) effect on protocol attacks that attempt to change originator/target roles.

Half-baked construction where the question's practice mitigates MitM even so slightly.

Start with naive Diffie-Hellman key exchange to establish an encryption key in $\mathbb Z_p^*$ with prime $p$ and $g\in\mathbb Z_p^*$ with $g\ne1$ (perhaps a generator). Normally the protocol goes:

Alice draws random secret $a$ and sends $m_a=g^a\bmod p$ towards Bob
Bob draws random secret $b$ and sends $m_b=g^b\bmod p$ towards Alice
Alice receives alleged $\hat m_b$, computes $s_a={\hat m_b}^a\bmod p$, then $k_a=\operatorname{SHA-256}(s_a)$ used as a secret shared key for a symmetric cryptosystem.
Bob does similarly and ends with $k_b=\operatorname{SHA-256}(s_b={\hat m_a}^b\bmod p)$, which if everything went well is the same as $k_a$.

Mallory playing active attacker could perform a classic MitM (where he plays as Bob to Alice, and as Alice to Bob), and have Alice and Bob use $k'_a$ and $k'_b$ that Mallory knows. But that leads to different $k'_a$ and $k'_b$, and Mallory has to decipher then re-encipher all symmetrically-enciphered messages between Alice and Bob. That's at least a chore for Mallory, and might lead to his active snooping to be detected.

Thus Mallory wants $k'_a=k'_b$. With the basic protocol above, he can achieve this my making $\hat m_a=\hat m_b=1$, $\hat m_a=\hat m_b=p+1$, or $\hat m_a=\hat m_b=p$, which will lead to $s_a=s_b=1$ or $s_a=s_b=0$, hence $k'_a=k'_b$ and known to Mallory. The question's countermeasure won't help against that, but the simpler countermeasure that Alice checks $s_a>1$ will block it. We assume that from now on.

Mallory can still succeed with fairs odds by sending $\hat m_b=p-1$. With odds about 25%, $a$ and $b$ will both be odd, giving $s_a=s_b=p-1$. If $g$ is a generator of $\mathbb Z_p^*$, Mallory can even force Alice to use odd $a$, by having Alice retry until ${m_a}^{(p-1)/2}\bmod p\ne1$ (which insures $a$ odd); same for Bob. The question's technique starts helping, even so little: Mallory can no longer determine the parity of $a$ from what Alice first sends, and must allow the protocol to advance to the second step for Alice before Mallory aborts it, or not.

Note: I tried to find attacks that work even if further it is checked $s_a<p-1$ or something similar intended to block the above, but so far found none. I welcome these (there's an open question), and vaguely conjecture that the question's countermeasure is likely to mitigate such other attack, if any.


Initialization Vector Properties This is a multi-layer problem, and I want to take you through the whole thing rather than just asking about IVs. Bear with me. Also, all code below is in Common Lisp because that's what I'm using, but if there are any complaints, I'll edit to put up pseudocode.

I'm trying to put together a procedure which will produce hard-to-guess session tokens for use in a server implementation. What I've got so far is

(ql:quickload (list :ironclad :cl-base64))
(setf *random-state* (make-random-state t))

(defmethod sha256 ((message integer))
  (ironclad:digest-sequence
   :sha256 (ironclad:integer-to-octets message)))

(let ((cipher (ironclad:make-cipher :aes :mode :ecb :key (sha256 (random (expt 2 1024)))))
      (counter (random (expt 2 512))))
  (defun new-session-token ()
    (let ((raw (ironclad:integer-to-octets (incf counter))))
      (ironclad:encrypt-in-place cipher raw)
      (cl-base64:usb8-array-to-base64-string raw :uri t))))

A side question here: what vulnerabilities does this approach have over using AES in counter mode?

The way to use this in counter-mode would be to change the line that defines cipherto :

...
(let ((cipher (ironclad:make-cipher
           :aes :key (sha256 (random (expt 2 1024)))
           :mode :ctr :initialization-vector [16-element vector goes here])
...

My questions are as follows:

What properties does that IV need? The only one I've seen mentioned is uniqueness, which implies that it doesn't have to be secret.
Do I need to generate a new one each time I generate a session token?
What's a good way of generating one?

EDIT:

As per comment by Stephen Touset, Ironclad supports CSPRNG out of the box (more specifically, it supports Fortuna. For my purposes, the above functions can be replaced with

(let ((prng (ironclad:make-prng :fortuna)))
  (defun new-session-token ()
    (cl-base64:usb8-array-to-base64-string
     (ironclad:random-data 32 prng) :uri t)))

ironclad:make-prng seems inconsistent in runtime; I've timed between 8 and 70 seconds.

Don't use ECB mode. ECB mode is fundamentally unsound except in very specific use-cases.
IVs have different requirements depending on the mode. In CBC mode, the requirement is "unpredictability", which is typically construed to mean "cryptographically random". CTR mode only requires that the IV be a nonce (e.g., is guaranteed to be unique).
A new IV must be used for each and every use of a key for an encryption operation.
IVs do not need to be kept secret. They are considered public information.
SHA-256(rand) is not a cryptographically strong random number generator. Hash functions evenly distribute existing entropy. If your underlying random source is predictable (e.g., has low entropy), hashing it does not improve that. Use a real CSPRNG.
In almost all contexts, you want to use authenticated encryption. GCM mode, EAX mode, and CCM mode satisfy this requirement. Non-authenticated encryption modes can allow attackers to modify ciphertexts in ways that have well-defined effects on the underlying plaintext.

If you want to generate hard-to-guess symmetric keys, just use a cryptographically-strong source of random numbers. If you need to establish these keys over an insecure channel, use something like the Diffie-Hellman key exchange.

You appear to be very new to cryptography. In general, I would strongly caution against working with ciphers at this low a level – the details are extremely important, and they are very difficult for amateurs to get right. The fact that you have already made multiple serious mistakes in fewer than 20 lines of code should give you an indication of just how difficult it actually is.

Unfortunately, I am not personally familiar with any higher-level abstractions for this sort of stuff for Common Lisp.


Difference between oracle behavior and real execution Suppose that there is a place in a security proof where the behavior of an oracle differs from the corresponding real execution (for example, the decryption oracle rejects certain types of ciphertexts but in the real world the decryption function accepts them). Let us assume also that the probability of this situation is not negligible (i.e., the adversary can force this easily).

My understanding is that this automatically means that the proof is incorrect, although I cannot justify it further than stating that "there is a difference between oracle behavior and real execution".

First of all, am I right? If so, is there a more profound explanation?
Do you have some authoritative reference on this matter?

Update: The only example I can find on this respect is a paper from Bellare and Ristenpart, which discusses the proof of Waters' IBE scheme. This proof is tricky:

  But A can make Extract queries that force any conceivable simulator to
  fail, i.e. have to abort. This means that the advantage against DBDH
  is conditioned on A not causing an abort, and so it could be the case
  that A achieves $\varepsilon$ advantage in the normal IND-CPA experiment but
  almost always causes aborts for the simulator. In this (hypothetical)
  case, the simulator could not effectively make use of the adversary,
  and the proof fails. (...) To compensate, Waters’ introduced “artificial aborts”

Although I grasp the meaning in the remarked sentence, I would like to have a deeper explanation

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

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

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

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

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


Proof of knowledge and replay attacks I was reading the ZK proof of knowledge of Schnorr and fiat shamir transformation, and I figured out that replay attacks are possible. Why these protocols don't take into account this attack? That seems very strange.

Thank you.

In General: ZK protocols become insecure if computed concurrently; I think this is what you are referring to. If the protocol is run in parallel, an adversary could request a proof of two relationships and produce a witness for the first with the knowledge gained from the second prover-output. When run concurrently, this attack cannot be executed because the adversary cannot receive a second commitment on the same relation to learn/produce a witness for the first. As far as I know, there is no protocol that achieves concurrent security.


DROWN Attack - Which is the SSLv2 vulnerability exploited? In order to get the session key used in TLS communication, an attacker must capture X TLS handshakes based on RSA key encryption, and switch to a server supporting SSLv2 protocol, and sharing the same private key.

The same RSA key lenght is used for encryption between SSLv2 server / TLS 1.2 server in order to use the attack right ?

So why it is mandatory to switch to a server supporting SSLv2? Can you explain me the SSLv2 vulnerability exploited in the case of a DROWN attack?

Thanks.

SSLv2 has the property that after it receives an encryption of the pre-master secret, the server sends a message that uses the derived key. (This is unlike SSLv3 where the server first checks the MAC from the client.) Now, when using a ciphersuite with 40-bit keys, it is possible to brute force and find the derived key. Importantly, in SSLv2, the derived key is just 40 bits of the pre-master secret (no hashing or anything). So, this gives an oracle for finding 40 bits of the pre-master secret. It is possible to use this to quickly find all of the bits of the pre-master secret, 40 bits at a time.

Some more details. In SSLv2 the RSA encryption uses PKCS#1 v1.5 padding. In order to prevent Bleichenbacher's attack, if the padding is incorrect the server just chooses a random secret and uses that instead (this fix was used throughout SSL versions). Thus, an attacker modifying the ciphertext cannot know if the padding was incorrect and this is a random value or if the padding was correct and this is the real value. The DROWN attack works by sending the SSLv2 server the same modified ciphertext twice. If the same key is used to compute the server reply both times, then the attacker knows that the padding was correct. (It also gets more information since as I wrote it gets 40 bits of the plaintext.) If the same result is not received both times, then the attacker knows that the padding was incorrect. The attacker knows if the same key was used since it just needs to brute force one of the messages in $2^{40}$ time to get the key. It can then try and see if that key matches the other ciphertext. All of this works since the server replies immediately and the attacker does not need to send a message with a correct MAC in order to get the server reply.

Note that this isn't the exact Bleichenbacher oracle, but it's a "Bleichenbacher-type" oracle.


Does it make sense to block RSA keys under 1024 bits? A paper I found (http://eprint.iacr.org/2012/064.pdf, which was submitted to a cryptography conference about two years ago), is based on the analysis of some 7.1 million 1024-bit RSA keys published online. By subjecting the modulus of each public key to an algorithm first postulated more than 2,000 years ago by the Greek mathematician Euclid, the researchers looked for underlying factors that were used more than once. Almost 27,000 of the keys they examined were cryptographically worthless because one of the factors used to generate them was used by at least one other key.

As these findings were related to 1024-bit RSA keys (and even those show some points of weakness), does it make sense to generally block all RSA keys under 1024 bits to enforce/strengthen used crypto?

Those findings were based on a broken PRNG. A broken PRNG affects all keys generated on such a device, no matter the size or the algorithm.

Common primes were how the problem was detected, but the problem itself is unrelated to primes or RSA. If RSA keys of a specific size where affected, that's only incidental because that's what the broken devices generated.

Blocking keys smaller than 1024 bits can be a good idea, because their security margin against factoring attacks has grown pretty thin, even when they're correctly generated. But that threat isn't related to the paper you link.