Leaving authentication data blank less secure for AES GCM? The AES GCM example for Ruby / OpenSSL shown at: http://ruby-doc.org/stdlib-2.0/libdoc/openssl/rdoc/OpenSSL/Cipher.html has a GCM example of the following:

cipher = OpenSSL::Cipher::AES.new(128, :GCM)
cipher.encrypt
key = cipher.random_key
iv = cipher.random_iv
cipher.auth_data = ""

encrypted = cipher.update(data) + cipher.final
tag = cipher.auth_tag

decipher = OpenSSL::Cipher::AES.new(128, :GCM)
decipher.decrypt
decipher.key = key
decipher.iv = iv
decipher.auth_tag = tag
decipher.auth_data = ""

plain = decipher.update(encrypted) + decipher.final

puts data == plain #=> true

In the example, auth_data (authentication data) is set to nothing.

My question is: Does this make the encryption less secure by using blank auth data?

Any help is greatly appreciated. Thanks!

AEAD modes like GCM are authenticated encryption with associated data; this setting only affects the associated data half of that. The ciphertext itself is still authenticated. The associated data portion is there to provide contextual information for the authentication of the ciphertext. Usually this data is something that's outside of direct control of the party providing the ciphertext to be decrypted.

As a contrived example, it could be the database ID of the user whose data is encrypted. This way, even if another user found a way to copy a victim's secret key and ciphertext into his own account, he wouldn't be able to successfully decrypt the ciphertext since the user IDs would not be the same. Alternatively, in something like an over-the-wire communication protocol, a sequence number could be used as the associated data. This would prevent some types of replay attacks at the cryptographic layer — any attempt to replay a ciphertext would fail, since the other side can reject packets with duplicated sequence numbers, and any other sequence number would fail to decrypt the cryptogram.

To get around to answering your question, "less secure" than what? Not using authenticated data doesn't render the underlying ciphertext inherently weaker than had you used another, non-AEAD mode. But if there's additional context that could be included and you're not using it, it could be more secure if you did use it.

As always, it's important to understand what your threat model is before you involve cryptography. What are you trying to protect? From whom are you protecting it? What are the possible threats, and the vectors an attacker might use to compromise the protected data?


How does the "biased-$k$ attack" on (EC)DSA work? I recently stumbled across Thomas Pornin's old answer about deterministic (EC)DSA again. There he states the following:

  Note that $k$ must be generated uniformly in the $[1, q-1]$ range
  (where $q$ is the subgroup order). Any information on $k$, even
  partial (such as: values between $1$ and $2^{160}-q$ are twice as
  probable than values between $2^{160}-q$ and $q$), can be exploited by
  the attacker.

When asked for clarification on this, he responded with a link to "The Security of DSA and ECDSA Bypassing the Standard Elliptic Curve Certification Scheme" by Vaudenay (PS) which mentions that Bleichenbacher discovered the attack and mentioned it in private communication with the author.

Now the paper has a short paragraph (section 2.2), which basically states an approximate equation for the bias and says that

  Bleichenbacher actually used it in order to approximate the secret key more
  and more precisely with signatures.

Now my question:
How does this attack work in a more detailed description? or formulated differently: How does one exploit this tiny bias to recover the secret key and how many signatures (ie oracle queries) are required for this along with what approximate computational effort (if it is non-negligible)?

The relevant section from the paper is (for your convenience):

  The initial standard pseudorandom generator in DSA for $k$ was simply
  a 160-bit pseudorandom number reduced modulo $q$. Bleichenbacher
  observed that the probability of $k$ in the $[0, 2^{160} − q]$ range
  have probability which is twice of the others. This leads to a bias

  $$E\left(e^{\frac{2i\pi k}q}\right)\approx \frac{q
 e^{i\pi\frac{N-1}q}}{\pi N} \times \sin\left(\frac{\pi N}q\right)$$

  where $N=2^{160}$. Since $q \approx N$, this may be large depending on
  the $\frac{\pi N}q$ angle. Bleichenbacher actually used it in order to
  approximate the secret key moreand more precisely with signatures.

Nguyen and Shparlinski detail the method in The Insecurity of the Elliptic Curve Digital Signature Algorithm with Partially Known Nonces. I'll largely follow the notation in that paper.

The idea is to convert the determination of a private key from biased $k$ nonces in several ECDSA signatures into instances of the hidden number problem (HNP), and then solve the HNP as a reduction to the closest vector problem.

So you collect a lot of signatures and construct a lattice out of them, and reduce that lattice using LLL or BKZ, and then you can extract the private key from the reduced basis vectors.

Estimated computational effort required

I tested this with a hand-crafted LLL Python implementation (it's so slow it surely must constitute an upper bound in performance...) running on a Ubuntu 16.04 VM with 2GB RAM, and I have the following sample runs:

96-bit bias, 5 signatures: (failed) 31 seconds
64-bit bias, 10 signatures: (success) 4 minutes
32-bit bias, 12 signatures: (success) 12 minutes
16-bit bias, 17 signatures: (success) 49 minutes
8-bit bias, 19 signatures: (failed) 79 minutes
8-bit bias, 21 signatures: (success) 244 minutes
8-bit bias, 20 signatures: (success) 177 minutes

I stopped there.  Nguyen and Shparlinski were apparently able to recover the secret key with only 3 bits of bias with 100 signatures and think that recovery is possible with only 2 bits being known.

More problem details and setup

So let's say you know the low $\ell$ bits of $k$. (This paper describes one way of recovering those bits.) Then you can write $k$ as

$$k = a + 2^\ell b$$

In other words, you know $a \in [0, 2^\ell -1]$. For simplicity, let $a = 0$. Then the equation for $s$ in the ECDSA signature $(r,s)$ becomes

$$s = (h + rx) \cdot (2^\ell b)^{-1}$$

where $h$ is your hashed message and $x$ is your private key, and everything is modulo $q$, the order of your base point. Rewrite this as

$$xr \cdot (2^\ell s)^{-1} = -h \cdot (2^\ell s)^{-1} + b$$

Define $t \equiv r\cdot (2^\ell s)^{-1}$ and $u \equiv -h \cdot (2^\ell s)^{-1}$ and you have

$$xt = u + b$$

Remembering that $0 \lt b \lt q/2^\ell$, you have

$$xt - u \lt q/2^\ell$$

So this is basically the HNP. $b$ is smaller by a factor $1/2^\ell$ than $x$,$t$, and $u$, so approximate this equation:

$$xt - u \approx 0 \longrightarrow xt - u - jq \approx 0$$

since everything is mod $q$. So first collect $n$ signatures, giving you several tuples of $t_i$, $u_i$, and $j_i$, and you can construct a matrix out of basis vectors:

$$ \begin{pmatrix}
q & 0 & 0 & \cdots & 0 \\
0 & q & 0 & \cdots & 0 \\
\vdots & \vdots & \vdots & \ddots  & \vdots \\
0 & 0 & 0 & \cdots & q \\
t_0 & t_1 & t_2 & \cdots & t_n \\
u_0 & u_1 & u_2 & \cdots & u_n \\
\end{pmatrix}
$$

(The first $n$ rows contain all zeroes and one $q$, one for each of the unknown $j_i$.) This is an $(n+2) \times n$ matrix. Now let $T \equiv (t_0, t_1, \cdots, t_n)$ and $U \equiv (u_0, u_1, \cdots, u_n)$. Then the short vector of interest, $X$ is going to be something like

$$U - xT + \text{(other stuff)}$$

You can modify your matrix to include "sentinel values" $s_T$ and $s_U$ so that you can identify $X$; if you see a reduced vector $T'$ with $s_T$ as its last slot, most likely you'll see the next-to-last entry containing $-x\cdot s_U$ from which you can recover $x$. Disclaimer: I saw this trick in a cryptopals problem first and makes things way easier than just guessing. The modified matrix looks like:

$$ \begin{pmatrix}
q & 0 & 0 & \cdots & 0 & 0 & 0\\
0 & q & 0 & \cdots & 0 & 0 & 0\\
\vdots & \vdots & \vdots & \ddots  & \vdots  & 0 & 0\\
0 & 0 & 0 & \cdots & q & 0 & 0\\
t_0 & t_1 & t_2 & \cdots & t_n & s_T & 0 \\
u_0 & u_1 & u_2 & \cdots & u_n & 0 & s_U\\
\end{pmatrix}
$$

Now you can use an implementation of LLL from NTL or fplll, find the sentinel value, and extract $x$.


What is the main difference between a key, an IV and a nonce? What are the main differences between a nonce, a key and an IV? Without any doubt the key should be kept secret. But what about the nonce and the IV? What's the main difference between them and their purposes? Is it only that, in literature and in practice, an IV is being used as "initiator" of a block cipher encryption mode which should be unique? And the same property should hold for a nonce as well, but since it doesn't instantiate something we call it a nonce? I.e: in AES-CTR mode the IV is a nonce+counter. And both are put in plaintext format in the beginning of the ciphertext.

A key, in the context of symmetric cryptography, is something you keep secret.  Anyone who knows your key (or can guess it) can decrypt any data you've encrypted with it (or forge any authentication codes you've calculated with it, etc.).
(There's also "asymmetric" or public key cryptography, where the key effectively has two parts: the private key, which allows decryption and/or signing, and a public key (derived from the corresponding private key) which allows encryption and/or signature verification.)
An IV or initialization vector is, in its broadest sense, just the initial value used to start some iterated process.  The term is used in a couple of different contexts and implies different security requirements in each of them.  For example, cryptographic hash functions typically have a fixed IV, which is just an arbitrary constant which is included in the hash function specification and is used as the initial hash value before any data is fed in:

Conversely, most block cipher modes of operation require an IV which is random and unpredictable, or at least unique for each message encrypted with a given key.  (Of course, if each key is only ever used to encrypt a single message, one can get away with using a fixed IV.)  This random IV ensures that each message encrypts differently, such that seeing multiple messages encrypted with the same key doesn't give the attacker any more information than just seeing a single long message.  In particular, it ensures that encrypting the same message twice yields two completely different ciphertexts, which is necessary in order for the encryption scheme to be semantically secure.
In any case, the IV never needs to be kept secret — if it did, it would be a key, not an IV.  Indeed, in most cases, keeping the IV secret would not be practical even if you wanted to since the recipient needs to know it in order to decrypt the data (or verify the hash, etc.).
A nonce, in the broad sense, is just "a number used only once".  The only thing generally demanded of a nonce is that it should never be used twice (within the relevant scope, such as encryption with a particular key).
The unique IVs used for block cipher encryption qualify as nonces, but various other cryptographic schemes make use of nonces as well.
There's some variation about which of the terms "IV" and "nonce" is used for different block cipher modes of operation: some authors use exclusively one or the other, while some make a distinction between them.  For CTR mode, in particular, some authors reserve the term "IV" for the full cipher input block formed by the concatenation of the nonce and the initial counter value (usually a block of all zero bits), while others prefer not to use the term "IV" for CTR mode at all.  This is all complicated by the fact that there are several variations on how the nonce/IV sent with the message in CTR mode is actually mapped into the initial block cipher input.
Conversely, for modes other than CTR (or related modes such as EAX or GCM), the term "IV" is almost universally preferred over "nonce".  This is particularly true for CBC mode since it has requirements on its IV (specifically, that they are unpredictable) which go beyond the usual requirement of uniqueness expected of nonces.


For hardware encryptions, is it possible to know the key by analysing the hardware? For example, Square reader uses hardware encryptions when swiping credit cards.

Is it possible to know the key that is used by the hardware encryption cipher by analysing the hardware circuitries?

The key has to be somewhere in the hardware, right?

That really depends on the device. Usually there is a full, layered, key management scheme. That may involve a key in ROM, but that's then just use to load the next keys for the higher layer in persistent memory (flash or EEPROM mostly). In the end session keys are generated in transient memory (RAM).

It's very likely that if you find a key in ROM that that key is only used to load the initial software. The keys to actually encrypt the (credit card) data are likely to be in EEPROM somewhere, possibly encrypted with a static key in the software.

"Hardware encryption" usually means that the encryption algorithms themselves are in the chip. That makes them less vulnerable to side channel and fault injection attacks. It will usually also give a large performance enhancement; 8 and 16 bit CPU's are not too efficient with block ciphers like AES.

Sometimes a key store is however implemented using hardware. The key that protects the data in that key store may be in ROM.


Are these hash function compositions collision resistant? If a hash function $H$ is collision resistant, are the following two hash functions collision resistant or not?  ($||$ is concatenation)

$H'(m) = H(H(m)) || H(m)$

$H''(m) = H(m) || H(m)$

My first approach to the problem for the first function is this: by proof of contradiction, I find that there aren't $m_1 \ne m_2$ so that $H'(m_1) = H'(m_2)$, because:

$H'(m_1) = H'(m_2) \iff H(H(m_1))||H(m_1) = H(H(m_2))||H(m_2)$

If we suppose that $m'_1 = H(m_1)$ and $m'_2 = H(m_2)$ then:

$H(m'_1)||m'_1 = H(m'_2)||m'_2$  which is false because $H$ is collision resistant.

Is my solution correct or am I missing something?

I can apply the same technique to the second function, but what confuses me is that first half bits are always the same as the last half bits, and this definitely doesn't look secure. But collision resistance is all I need.

Your first approach $H'(m) = H(H(m)) || H(m)$ will not have any improvement collision resistance. The reason being is that a collision in the right half automatically causes a collision in the left half, since the output of $H$ is identical for the colliding messages. The left half is not a function of the message, but of the message hash, the concatenation will have the same collision resistance as the hash itself, but take up twice the space and require an additional hash iteration, with no improvement in any security property

The second approach will also have identical collision resistance to $H$, but simply take up twice the space, with no improvement in any security property.


tower of extension field while working on tate pairing, i have to implement towering technique. like i have point p on F(q) and point Q(F(q^k)) (here embedding degree k=12 for BN curve).

instead of taking a point Q on F(q^12), i take this point on twisted curve E'(q^2).

finally i need to map this point to F(q^12),how can i use this towering technique (2-2-3), because output of tate pairing for BN curve should be F(q^12).
i have studied different articles but still confused, any numerical example would be very helpful.
thanks in advance

Are you sure you want 2-2-3, not 2-3-2? The latter is more common in my experience.

None the less, the first step is almost always done with a quadratic extension where i^2=-1. So you just need to implement complex numbers over your field of choice.

Multiplying complex numbers is simple if you just treat them as (x+iy) - I hope that's basic.

For inversion see See "Implementing cryptographic pairings", M. Scott, section 3.2. (ftp://136.206.11.249/pub/crypto/pairings.pdf)

And here's my code for this step: https://code.google.com/p/go/source/browse/bn256/gfp2.go?repo=crypto

For the cubic extension see http://eprint.iacr.org/2006/471.pdf. I used τ^3=i+3. The multiplication is little more complex, but still just an application of basic algebra. For inversion, I'll have to point you at the comments that I wrote in my code: https://code.google.com/p/go/source/browse/bn256/gfp6.go?repo=crypto#242

Now you're at q^6 you can work in the twisted curve.

Lastly, the quadratic extension to q^12 is similar to the original extension. After the cubic, it should be easy! I used ω²=τ because I was following http://cryptojedi.org/papers/dclxvi-20100714.pdf.

For exactly how you get from the twist over q^6 to the curve over q^12 depends on the exact homomorphism in question.


AES Inverse Key Schedule I have a 128-bit input-block and the corresponding cipher-block given.
Additionally I have the last round-key given.
Is it now possible to get (calculate) the associated cipher-key? I already implemented the normal key-schedule with the rcon to generate the round-keys out of a cipher-key (like on wikipedia: https://en.wikipedia.org/wiki/Rijndael_key_schedule), but it didn't help me much for the other way...
Ist the AES Key Schedule easily invertible? I'm a bit baffled now because i thought it would be.

Thanks in advance for your answers.

Yes, that is possible: It is quite obvious from the description of the key schedule that all involved operations are invertible. An implementation of that inversion is the function aes128_key_schedule_inv_round found in this C file.


In which situations is a length-extension attack a problem? A lot of hash functions, including the SHA-2 family(but not the SHA-3 candidates and SHA256d) are vulnerable to length extension attacks. But when is this property a problem?

I guess certain naive MAC implementations might have issues. Are there also some situations where length-extensions cause problems for unkeyed hashes?

The archetypal situation where the length-extension property becomes problematic is when ones builds a Message Authentication Code from a hash function as $$\textrm{BadMAC}(K,M)=\textrm{Hash}(K||M)$$ where $K||M$ is the concatenation of the Key and the Message.

The length extension property then translates directly into the capability to forge a different message, starting as the original, for which computing the $\textrm{BadMAC}$ is trivial.

In practice, that could allow adding an appendix to a text protected by $\textrm{BadMAC}$ (after a short rash of garbage in most cases, but often it could be invisible when printed). Also, that could allow extending the size of a short signed message so that it creates a buffer overflow after its integrity is checked using $\textrm{BadMAC}$.

HMAC is secure against that; and then more.

Another (artificial) example could be when it is asked the hash of increasingly long messages (with precisely the wrong content) as a Proof-Of-Work: one user knowing the hash constituting the POW of a user could abuse that into another POW indicative of slightly more work.


Strategies to address an immutable key in a symmetric cryptosystem I have a power constrained environment where I do not have enough power to update an encryption key.  For this reason, the symmetric key will be programmed before the devices are distributed, and this key is used to encrypt a payload.  I have two different things that I could possibly change, one is a nonce, and the other is a modification to the base key.  I don't have a way to generate a nonce locally; however, in the system, you have a "host" and a "client" and the host polls the client. The encrypted packed goes from the client to host.  For the sake of scope, let's assume AES-128.  I have a very small, non-volatile memory of 128 bytes.  Here is a list of things that I could possibly do within the current framework:

I could send a random number and XOR that with key that is already stored in the "client".  The problem there is that I have 128-bit key but only the ability to send a 32-bit value to the device (currently that is, I possibly could get 128-bits, but I need to look into the channel bandwidth)
The device creates a 16-bit pseudorandom number that is generated by the client is known by both the host and client, and I could use that a nonce in some way.  This approach is easiest because it becomes a host-side software issue because the key is not modified.

Above is basically a nuance to the problem, so the question is:
Is there a standard method to deal with the problem of an immutable key structure in a system which uses a symmetric cipher?

I'm not sure if this is precisely what you are asking, but developing single-session keys from a long term hard-wired key is something that mobile phones and SIM cards do. Hard-wired keys on the SIM and known to the service provider kick off key derivation process augmented with a random nonce value from the service provider's base station. The 3GPP MILENAGE suite is such a method, is standardised via ETSI, and only uses symmetric primitives (block ciphers).


Does TLS 1.3 really send PSKs encrypted? In the following link it says:

  When a 1.3 client connects to a 1.3 server they agree on a resumption key (or PSK, pre-shared key), and the server gives the client a Session Ticket that will help it remember it. The Ticket can be an encrypted copy of the PSK—to avoid state—or a reference number."

https://blog.cloudflare.com/tls-1-3-overview-and-q-and-a/

I have read through the draft of TLS 1.3 and have only found that a Client sends an PSK-identifier, which is a number, that belongs uniquely to a PSK. I couldn't find any mention of "an encrypted copy of the PSK".

Am I wrong? Did I miss something in the draft? Because if I did not miss anything, servers would need to keep state of every PSK they have established, no?

PSK is encrypted and normally sent after finished message.
If you inspect with wireshark, it appears as application data.
If you decrypt this message, you will find the session ticket including the psk id.

Servers can use psk id for stateless approach.
Servers can encrypt the resumption psk, issue time, and so on..
and use this encrypted message as a psk id.
When the client present psk id, server can fetch those informations to resume by decrypting it.


is it necessary to write C=E(K,P), Can we write C=E(P,K)? I just want to know that can we write encryption and decryption formula like
$C=E(P,K)$ instead of $C=E(K,P)$

Personally I keep to what I do during development: the variable that is most static is to the left, the more dynamic ones to the right. So I use key, IV and input in that particular order.

A cipher is a keyed permutation, often written as $\text{E}_K$, so in my opinion $\text{E}(K, M)$ is closest to $\text{E}_K(M)$. Writing the parameters in a different order is not as nice. But as in any mathematical function, it is up to you to define it.

As Geoffroy said, if it is made clear then you can certainly get away with it. But I still would keep to the most common order if just to avoid confusion.

Oh, I just noticed that you use $P$ for "plaintext" while I use $M$ for "message", but that's really not much of an issue in my opinion.


How to represent point-at-infinity in affine coordinate In projective coordinates point-at-infinity can be identified with z=0. How to identify the point-at-infinity in affine coordinate.

Whether x=0 and y=0 can be considered as point-at-infinity in affine coordinate?

From a mathematical point of view this is not possible. I would say almost by definition because the point at infinity does not lie in the affine part. To be more precise:

Let $\mathbb P^2$ is the two dimensional projective space with coordinates $(x:y:z)$ and $\mathbb A^2 \subset \mathbb  P^2$ the affine part where $z \neq 0$ then one can see $X = x/z$ and $Y = y/z$ as coordinates on $\mathbb A^2$. Then $\mathbb P^2 \setminus \mathbb A^2$ is exactly the part where $z=0$ by definition.

Now if $E$ is the curve given by $y^2z = x^3 + axz^2 +bz^3$, then there is exactly one point of $E$ in $\mathbb P^2 \setminus \mathbb A^2$. Indeed by setting $z=0$ one obtains $0 = x^3$ hence $x=0$ showing that (x:y:z) = (0:1:0) is the only point of $E$ not in $\mathbb A^2$. This point (0:1:0) is the point at infinity and does not lie in $\mathbb A^2$ hence you cannot represent (0:1:0) in affine coordinates.


HSM RNG - Compliance to FIPS 186-2 If the RNG of a HSM is said to be compliant to FIPS 140-2 (approved DRBG - SP 800-90 CTR mode) does also imply that it is compliant to FIPS 186-2 ?

FIPS 140-2 and FIPS 186-2 (PDF) are not standards that describe RNGs.

FIPS 140-2 refers the task of standardizing RNGs to SP800-90 (PDF) which specifies software-based pseudo random number generators, to which your module seems compliant.

FIPS 186-2 only talks about RNGs in one place, in Appendix 3, where it says that using the RNG from appendix C of ANSI X9.17 is appropriate (it no longer is as of today) and it also says that using other FIPS approved is appropriate. As it stands it looks like the RNG can be considered appropriate because FIPS 200 (PDF) says, that you should follow SP800-53 (PDF) which in turn says that SP 800-90 should be followed, which specifies the RNG in question and thereby the RNG is "FIPS-approved".

Note though that you can't claim FIPS 186-2 compliance just because you use a compliant RNG because FIPS 186-2 specifies the RSA, DSA and ECDSA signature algorithms which you'd have to implement and provide properly in order to claim FIPS 186-2 compliance.

The relevant quote from FIPS 186-2 Appendix 3 (PDF):

  Any implementation of the DSA requires the ability to generate random
  or pseudorandom integers. Such numbers are used to derive a user's
  private key, x, and a user's per message secret number, k. These
  randomly or pseudorandomly generated integers are selected to be
  between 0 and the 160-bit prime  q  (as  specified  in  the
  standard).   They  shall  be  generated  by  the  techniques  given
  in  this appendix, or using other FIPS approved security methods.

  One FIPS approved pseudorandom integer generator is supplied in
  Appendix C of ANSI X9.17, "Financial Institution Key Management
  (Wholesale)".


How HSM stores keys securely when we say that HSM  stores keys securely we mean that non-authoriszed requester cannot access the keys.

but the key is stored physically anyway in the hardware, so access is still possible

if the keys are encrypted, that means that there is another key in the hardware that encrypted those keys. this key is not encrypted then !!

I'm confused

The key is stored physically anyway in the hardware, so access is still possible

The assumption is that it is practically impossible to read the keys that reside (permanently or temporarily) inside the HSM. They will be present in usable form, and used, only inside the HSM, and it is the HSM's job to protect these keys (including enforcing restrictions about what can be done with them).

Preventing access to information stored and processed in the HSM (and deliberate interference with that processing) is accomplished to some useful degree by physical barriers that prevent connecting probes to the insides of the HSM. There are sensors intended to detect if these barriers are pierced or operating conditions otherwise not normal, checks to detect incorrect processing... In such case, the HSM typically attempts to destroy the keys and data being processed, so that there is no longer anything useful that can be extracted.

Additionally, it is often insured that the keys are just not there (thus can not leak) unless there is good assurance that the HSM is operating under rightful conditions (for example, it might be necessary to reunite several partial keys, some in Smart Cards under control of security officers and protected by a PIN code with counter, in order to obtain and use the actual keys inside the HSM).

  If the keys are encrypted, that means that there is another key in the hardware that encrypted those keys

Yes. That's typical.


Generating a random number using a quantum computer I have been looking into the creation of truly random numbers using a quantum computer, but I have been having trouble with finding resources on this problem. Is it possible to create a truly random number using a quantum computer?

In theory, my thinking is that we can prepare a qubit in the $|0\rangle$ state, apply a Hadamard to obtain a $|+\rangle$, and then measure in the logical basic to get a 0 with probability $\frac{1}{2}$ and a 1 with probability $\frac{1}{2}$. Repeat the process as many times as you want to create a random number in binary (i.e. 0110001...)

Now there are obviously problems with this practically (regarding the accuracy of our state initiation, Hadamard transform, and measurement). But is the theory correct? In theory can we therefore produce a truly random number using a quantum computer?

Yes, it is possible to use quantum computer as a true random number generator, by applying Hadamard gates to all available qubits in initial $|0\rangle$ state and measuring them in the standard basis; but this is inefficient way of generating random numbers because quantum computer requires time to cool down its qubits to the initial state before starting a new computation.

There are other cheaper and faster methods of generating random numbers using quantum effects, see for example ANU Quantum Random Numbers Server


Is there a single-use signature scheme, where a second use of the private key discloses it to the world? With ECDSA (and possibly DSA too) I'm aware that if the same value for $k$ is used with the same private key $D_A$ to sign two different messages, then anyone possessing the two messages $m_0$ and $m_1$ and two signatures $(r_0, s_0)$ and $(r_1, s_1)$may recover $D_A$ trivially (as in fail0verflow's PS3 private key recovery).

Does there exist a way of using this weakness to make a signature system where each private key can only be used once, with the deterrent that if the private key is used a second time, everyone can calculate and use it?

This would require an extra verification step to prove that $k$ was deterministically generated from $D_A$ (in a prescribed manner) so that signings would only be valid, if they used the single, known way of calculating $k$ (without revealing $k$).  Otherwise, if a malicious signer were to use different $k$s for the same $D_A$ there would be nothing to deter it, so $k$ must be a deterministically generated from $D_A$.

(This is different from RFC 6979 which uses a hash of the message and $D_A$ to ensure a good pseudo-random value for $k$.)

From answers to With ECDSA is there a way for the verifier to calculate any properties of $k$? and With EC secp256k1 is there a way of transforming a function of the private key to a function of the public key? it looks like this is impossible.

Is there a way of making a single-use signature scheme, where a second use of a private key discloses that private key to the world?

Trivial solution: generate a random $k$ as part of the private key and include $r$ as part of the public key.

The verifier uses $r$ from public key, so the signer must use the same $k$ for every valid signature. The signer could create multiple related public keys and reuse $D_A$, but then, they might as well just create multiple key-pairs in the first place.


Is a random string good for an AES-256 instance I have a randomly generated string of about 256 characters long. This string is hashed to for a key and initialization vector for a program running on the .NET framework 4.8. Is this method secure from a professional point of view?

The Following Code Is Now Using The Password Derive Bytes Function, All Values Will Be Changed Accordingly
    string Password = "Example";
    byte[] IV = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15};
    byte[] Salt = Encoding.ASCII.getBytes("Salt Example");
    PasswordDeriveBytes pdb = new PasswordDerivedBytes(Password,Salt);
    Aes Alg = Aes.Create();
    Alg.Key = pdb.CryptDeriveKey("Aes","SHA256",256,IV);
    Alg.IV = IV;

The Code Above Is C#


Protocol to generate Client Certificates at the start of a SSL session automatically? A more secure form of 'cookie' could be created for SSL communications through the following method.

The client generates and requests the server to sign a certificate.
Then the client authenticates to the https server using the client certificate.
Additional basic auth is used to tie the client certificate to the site credentials.

That would allow the 'client computer' to be able to prove it's identity (knowledge of private key) to the server (also assuming that the server certificate is authenticated using PKI).

I am not aware of this protocol being used, advantages? disadvantages? or is it just pointless because cookies give us enough security?

I suspect that you may wish to read the current Internet draft on TLS Origin-Bound Certificates and note the organisation of the authors at the bottom.


RSA public key can decrypt the ciphertext it encrypted? For this example of my problem I used $2$ and $7$ for $p$ and $q$, and $2$ for my plaintext... but I have tried this with many different numbers and they all have the same problem.  Phi of $n$ was $6$.  My public key was $m^5~mod~14$ and my private key was $m^{11}~mod~14$.  This all worked fine.  If I encrypted my plaintext $2$ with my public key, $2^5~mod~14$, I got $4$.  If I took my ciphertext, $4$, and sent it through the same equation again, $4^5~mod~14$, I get back $2$. How can it be that my RSA public key can decrypt the ciphertext it encrypted?

The prime 2 is special, and too small.

You happened to choose an $e$ which is equal to $d,$ as I explain below.
For a proper choice of large primes, it is extremely unlikely that $d=e,$ but if it is, one can simply choose another $e$ and compute the corresponding $d.$

Also, a correction, you public key is $(n,e)=(14,5)$. It is your ciphertext which is $c=m^5~mod~14.$ For this tiny example it happens that $e=5$ satisfies $$e^2=1~(mod~\phi(14))$$ so $d=e$, thus your public and private exponents are the same, not a good thing.

Also you say your private key is $m^{11}~mod~14$, which I interpret to mean your private key $(d,p,q)$ has $d=11.$ This is a valid $d$ since $5\times 11=55=1~mod~\phi(14).$ The correct terminology is $$m=c^d~(mod ~n)$$since the letter $m$ is reserved for the message.


Why aren't there function based discrete log problems? If discrete logarithm is based on the fact that finding $x$ for $a^x$ is difficult, wouldn't it be difficult to find $n$ such that if $f(x_1) = x_2$ then $f(x_2) = x_3 ... = x_n$ if $x$ is a generator with the equation for a group $N$?

I'm just confused as to why there seem to be only two discrete logarithm problems, EC scalar multiplication and exponentiation.

Applying a function successively as you indicate does indeed form a group - Each time the function is applied, it is effectively equivalent to incrementing the group value by 1. This allows for an indirect way to compute an addition operation, by enumerating the number of times that the function has been applied.

You can actually instantiate Diffie-Hellman with an arbitrary deterministic function $f$ - correctness is guaranteed, but security is not.

Effectively, your DH private key is the number of times that the function has been applied. In classic DH, the function $f$ is simple multiplication by the generator $g$.

It is easy to see that when you apply the function $x$ times, and then apply the function $y$ more times, then the function has been applied in total $x + y$ times. Provided that both parties use the same $f$ and initial starting value (the generator $g$), both parties will arrive at the same value.

An example with small numbers:

$priv_1 \leftarrow 4\\
priv_2 \leftarrow 3\\
pub_1 \leftarrow F(F(F(F(g))))\\
pub_2 \leftarrow F(F(F(g)))\\
share_1 \leftarrow F(F(F(F(F(F(F(g)))))))\\
share_2 \leftarrow F(F(F(F(F(F(F(g)))))))$

Clearly, $share_1$ and $share_2$ yield the same output, as the function has been applied the same number of times. Thus correctness is guaranteed.

Challenges

There are three challenges that I have encountered to create a DH protocol this way.

The first is finding some $f$ that is difficult to recover the number of times that $f$ has been applied, given some output $F(F(F....(g)))$.

Failing to fulfill this property implies the ability of an adversary to recover the private key

The second is that the public keys must not be usable to reach the shared secret.

I.e. if $share_{secret} = pub_1 * pub_2$, then recovery of the private key is not necessary to break the system

The third requirement is that the function must offer an algebraic shortcut that allows you to compute the $N_{th}$ term without actually invoking $f$ $N$ times. For example, you can instantiate a DH like protocol using a standard cryptographic hash function such as sh256 - but there is no way to shortcut such a function. For security, a private key is a number that is at least 128 bits in size; Using sha256 for DH would imply the need for on the order of $2^{128}$ invocations of the function.

Without an algebraic shortcut, computing a public key is computationally intractable.

There is a actually fourth requirement that may or may not be trivial to fulfill: Finding a generator for the group must be "easy". (thank you to MarquisDeSitruce for pointing this out)

If there is no generator, you cannot generate group elements, and hence no key agreement can occur

Edit in response to further questions/comments

Since $f$ can be an arbitrary function, some are indeed trivial to recover the private key from, others are not; The exact way to violate that requirement depends on the exact ff that you use. Clearly if ff is $x+1$, then recovering the private key from the public key is trivial. There must exist no algorithm that can recover the private key in less time than guessing it; It does not have to be an otherwise convenient/trivial algorithm i.e. LLL could probably break $mx+b$.

Side note about $mx + b$

Actually, I have experimented with that particular function $mx + b$. It provides a shortcut (involving modular exponentiation and a geometric series); Unfortunately, it is broken. I don't usually bother to write up attacks, I tend to perform them live in the python interpreter. I don't remember the attack offhand, if I recall correctly it was algebraic, breaking the system in negligible time/space.


What does it mean in layman's term when it states that - "An algorithm running for polynomial time can break the scheme with probability p"? For example - let's say an adversary algorithm runs for $n^{3}$ time and can break the scheme with probability 0.001. Does that mean, even after running the algorithm for $n^{3}$ time, it will only succeed in 1 out of 1000 times? So, if my understanding is correct, then the adversary algorithm need to be executed for at most 1000 * $n^{3}$ times to be successfully able to break the scheme.

The statement

  An adversary algorithm runs for $n^3$ time and can break the scheme with probability 0.001

can't be much simplified while keeping its meaning; nor can it be used to derive something useful for what happens after the algorithm is run 1000 times, beyond that this breaks the scheme with probability at least $1/1000$.

This statement is shorthand for: There exists some deterministic algorithm, designated/modeling an adversary, which when run with inputs(s) varying uniformly randomly across experiments, after running for $n^3$ time in each experiment, will break the scheme for a proportion at least $1/1000$ of the possible input combinations (in practice, if the number of input combinations is huge, for a proportion not significantly lower than $1/1000$ of experiments when enough experiments are run that the algorithm succeeds a significant number of times). Importantly: the varying inputs(s) of the algorithm might be from the problem to solve, or/and from a random source used by a randomized algorithm turned deterministic by moving its source of randomness as an input; that's left unstated.

It is not possible to conclude that $1000$ executions of the algorithm will break the scheme with odds better than $1/1000$; much less with certainty.

If the algorithm is purely deterministic, that is succeeds or fails depending only on inputs part of the problem to solve, repeating the experiment with the same inputs won't help at all, and odds of success are the same for 1 or 1000 runs: (at least) $1/1000$.

If the algorithm succeeds or fails according to inputs that are made to vary randomly across experiments concerning the same problem to solve, but independently of inputs defining the problem to solve, we can state that the scheme is broken with odds at least $1-(1-1/1000)^{1000}\approx1-1/e\approx63\%$ after 1000 experiments (raising to $\approx99.3\%$ after 5000 experiments).

Illustration: the goal is to break RSA by factoring the public modulus $N$ with $n^{5.8}<N<n^{5.9}$, which can trivially be done by trial division of $N$ in time $n^3$. Consider these two algorithms:

Algorithm $\mathcal A_0$ accepts as input $N$; it factors $N$ by trial division, and outputs the result only if $N\bmod997=42$
Algorithm $\mathcal A_1$ accepts as input $N$ and a large value $R$ randomizing the algorithm; it factors $N$ by trial division, and outputs the result only if $R\bmod997=42$

Both algorithms satisfy the stated condition. Repeating $\mathcal A_0$ 1000 times for the same random $N$ succeeds with odds just above $1/1000$; while repeating $\mathcal A_1$ 1000 times for the same random $N$ and fresh random $R$ at each run succeeds with odds just above $63\%$.

Note: if we run $\mathcal A_1$ 1000 times with incremental rather than random $R$, then success is certain.


Is $f(x) = g(x) ⊕ g(\bar{x})$ a one-way function where $g(x)$ is a OWF? Let $g$ be a one-way function, and let $f(x) = g(x) ⊕ g(\bar{x})$ (where the bar over x denotes bitwise complement). Is $f$ necessarily a one-way function?

Expanding on @Mikero's comment above: First, lets assume that a one-way function $h : \{0,1\}^n \to \{0,1\}^n$ exists.

Then assume towards contradiction that $f(x) = g(x) \oplus g(\bar{x})$ is a one-way function if $g$ is a one-way function. Then in particular $f'(x) = h(x) \oplus h(\bar{x})$ must be a one-way function. And further it follows that
\begin{align}
f''(x) =\;& f'(x) \oplus f'(\bar{x})\\ =\;& (h(x) \oplus h(\bar{x})) \oplus (h(\bar{x}) \oplus h(x))\\ =\;& (h(x) \oplus h(x)) \oplus (h(\bar{x}) \oplus h(\bar{x}))\\ =\;& 0^n
\end{align}

would be a one-way function, which it is clearly not as it is a constant function.


difference between the uniform and non-uniform probabilistic polynomial algorithms (ppt) I am reading the book "Efficient Secure Two-Party Protocol". A question came to my mind. why has the author used a probabilistic polynomial time algorithm for security definition of ideal/real model in the semi-honest model, but used a non-uniform probabilistic polynomial time algorithm in the malicious model?
Thanks for considering my question.

The non-uniformity needed for the proofs of security is in the distinguisher (in order to get advice as to which inputs the protocol breaks on in the reduction). However, if you are already assuming non-uniformity for the distinguisher, then you may as well assume it for the real adversary. But, if you assume it for the real adversary then you also need it for the simulator since the simulator needs to be as strong as the adversary in order to be able to run it.

The above is all true for the malicious case. However, in the semi-honest case, you still need non-uniformity for the distinguisher, but there is no adversary; the simulator just needs to generate the view of the semi-honest adversary in the protocol. For this, it suffices to use a uniform machine. Having said this, nothing would be lost by taking a non-uniform simulator; it’s just that we don’t need it to prove security of protocols (at least, I don't know of any protocol for semi-honest that requires a non-uniform reduction; if there is such a case, then they can just use non-uniform simulation, as I mentioned).


1-out-of-2 OT from Random 1-out-of-2 OT Last week I came upon this problem in my h.w.:

  Let $OT^m$ denote 1-out-of-2 oblivious transfer of $m$ bit inputs.

  Let $RandOT^m$ denote the following primitive:

  The sender’s input consists of two m-bit strings, $x_0, x_1$.
  The receiver has no input.
  At the end of the protocol the receiver learns $(b,x_b)$, for a randomly chosen $b$ in $\{0,1\}$, and learns nothing about $x_{1-b}$. The sender learns nothing. (Note that $b$ must be chosen at random, and neither nor the server should be able to choose the value of $b$).

  Show the following two reductions, for the semi-honest case.

  It is possible to construct $RandOT^1$ from $OT^2$.
  It is possible to construct $OT^1$ from $RandOT^1$.

I solved the first problem quite easily, but I just can't figure a way to solve the second one.

We construct $OT^1$ from $RandOT^1$ as follows. Say, the Sender (S) has messages $m_0, m_1$ and the Receiver (R) has choice bit $c$. I.e., R needs to learn $m_c$. Now we first run the random OT. S now has random $x_0, x_1$ and R has $x_b,b$. The idea is now for S to somehow OTP $m_c$ with $x_b$ and $m_{c \oplus 1}$ with $x_{b \oplus 1}$ and send these values to R.

To do this R sends $d = b \oplus c$ to S (note this hides c as a OTP). S then sends $(y_0, y_1) = (x_{d} \oplus m_0, x_{d \oplus 1} \oplus m_1)$ to R. Note that we can write $y_i = x_{d \oplus i} \oplus m_i$. R then finds $m_c = y_c \oplus x_b$. Note, $y_c = y_{d \oplus b} = x_{d \oplus d \oplus b} \oplus m_c = x_b \oplus m_c$, thus we get the correct result. Also note, R does not learn $m_{c \oplus 1}$ as it is OTP'ed with $x_{b \oplus 1}$.


Is authentication length always a subset of encryption length? Do in all the use cases, if I have to encrypt and authenticate, encrypt-then-authenticate or authenticate-then-encrypt, like in IPSEC, SSL or SSH or others, if I were to do these operations to a packet, do I always know that the cipher offset will be greater than authentication offset i.e that authentication length will always be greater or equal to cipher length. For example in IPSEC, we add an esp header and trailer, we need to start encrypting after ESP but need to authenticate starting from ESP.

When we have regions of the packet that we only authenticate but not encrypt, that happens because we have data that we want to bind to the encrypted region, but we don't need to include within the encrypted region.  Examples of this are:

For IPsec, we include the sequence number (as a part of the ESP header).  We include that within the authentication (otherwise someone in the middle could change that arbitrarily), however we don't want that to be encrypted (otherwise, the decryptor would have to decrypt the packet before processing the sequence number).
For TLS, we include the sequence number.  We include that to prevent someone from replaying a TLS record; however this is different from the IPsec case, as we don't actually include the sequence number in the packet; both sides are expected to include that implicitly.

Now, the question is: does the opposite make sense?  Do we ever have a case where we care about the privacy of a field (so we need to encrypt it), but we don't care about its integrity (so if someone changes it, we don't really care)?

Personally, I'm having problems thinking of a scenario where this makes sense; if we have an encrypted region, one would expect that we do authentication over that entire region, and not pick and choose.

I also can't think of a protocol which attempts to take advantage of that (other than protocols which don't do integrity checking on anything - we try to discourage that, but they do exist).


How to use Frobenius for finding Square Roots in $GF(2^m)$ Given a polynomial $x$ with degree $n$ in $GF(2^m)$, $1 < n < m$, will any generator of $GF(2^m)$ suffice when applying the Frobenius automorphism to determine the square root of $x$ as described in the answer to this related question?  And why? (anecdote or rigid proof are both welcome).

For example, given $f(x) = x^2 + 1$

By trial and error, $x^{2^{n-1}}$ with generators $x^{257} + x^{12} + 1$ and $x^3 + x + 1$, both yield $x + 1$.

Of course, for an efficient algorithm, the smaller the degree, the faster the $x^{2^{n-1}}$ computation.  But computing a generator for every degree that might be needed (or as needed) would be daunting.  Instead, and assuming one can rely upon the general case, i.e., "any primitive generator having degree greater than that of $x$ will do", one can use a table from a source like this (A Table of Primitive Binary Polynomials - M. Zivkovic et al).

I am very new to finite fields and haven't got all the terminology much less the understanding correct, so I hope the example clarifies my question.

EDIT: Background

Consider the Galios relationship:  $S_j = S_0 x^j mod P$, where S, x, and P are all polynomials with coefficients in GF(2).  $P$ is not irreducible in this case.  So, to determine the period of $P$, it must be factored, and by finding the derivative of $P$ to be 0, we know a square exists.  The referenced answer says that by the Frobenius automorphism, the square root of a polynomial is $x^{2^{n-1}}$.  But in this case, $n$ and an $r(t)$ are not given.  Can they be chosen specially for the case of $P$?  For instance, can $n$ be set to $degree(P) + 1$ and can $r(t)$ be chosen with $degree(n)$ from a table of known irreducibles?

No, the relation you have noticed does not work in general, and it is easy to find counterexamples. For example using the two following representations of $\mathbf F_8$.

In $\mathbf F_2[X]/(X^3+X^2+1)$, the square root of (the coset of) $X$ is $X^2+X+1$, whereas in $\mathbf F_2[X]/(X^3+X+1)$ it is $X^2+X$.


What is the best way to accurately describe this statistical probability? I am in the process of writing some information for an App. I need to express the probability of something happening but in a way that is correct but easy to understand. I'm confused on the actual math for this. I'll simplify the numbers here.
Assume a system has 1,000 possible unique codes and I have used 10. I set a computer to search for the codes at a rate of one per hour. How many hours statistically before I find a code ?
On the face of it, I am assuming 100 hours. But I have a feeling that this wouldn't be correct ?

So, the full analysis for random trials is that the initial probability of a hit is $p_0=k/n$ and $k=10,$ and $n=1000$ for your case. Define the number of trials until the first hit as $N_0$ which is a geometric random variable with expectation
$$
\mathbb{E}(N_0)=p_0^{-1}=\frac{n}{k}.
$$
This is indeed 100 as you guessed.
If you wanted  to find 2 codes your success probability would now be $$
p_1=(k-1)/n$$
and the expected time to find a second (distinct) code would be
$$
\mathbb{E}(N_0)=p_1^{-1}=\frac{n}{k-1},
$$
which is a little longer.
The expected time to find $r$ codes is thus
$$
\mathbb{E}(N_0)+ \mathbb{E}(N_1)+\cdots+ \mathbb{E}(N_{r-1})=
n\left(\frac{1}{k}+ \frac{1}{k-1}+\cdots+ \frac{1}{k-r+1}\right)
$$
which is $n(H_k-H_{k-r})$ where $H_k$ is the k_th harmonic number  (the sum of reciprocals of the first $k$ integers) and is approximately $\ln k$ for large $k$. So the overall time complexity is approximately
$$
n \ln \left(\frac{k}{k-r}\right)
$$
for $r>1.$


Is unusual (non power-of-two) RSA key size more secure? On this blog https://blog.josefsson.org/2014/06/23/offline-gnupg-master-key-and-subkeys-on-yubikey-neo-smartcard/ there is a following sentence

  Generate master key

  Below I will use a 3744 bit RSA key, where the key size is selected based on the assumption that people will focus efforts to crack RSA keys on the usual power-of-two key sizes.

But that leaves me to wonder: do unusual key sizes really pose a disadvantage to a potential attacker? After all, couldn't he just get a key size from a public key?

From this answer:

  The difficulty of factoring (thus, as far as we know, the security of RSA in the absence of side-channel and padding attacks) grows smoothly with $n$.

So, if factoring is the method of choice for breaking RSA, it doesn't seem like it really helps.


Elliptic curve brute forcing I have elliptic curve of equation $y^2 \equiv x^3 -x $. And the coordinate of points $Q$ and $P$. I want to solve $Q=[k]P$ (where $k$ is the unknown) by testing all possible $k$.

Is this the right approach to solve this problem?

Edit

I understand from comments that this is known as Elliptic curve discrete logarithm problem, So what is the best approach to attack this problem.

Pollard lambda
Pollard rho
Baby-Step, Giant-Step
The Pohlig-Hellman Method
...

PS :

I tried to factor $p-1$ and the result is $p-1=(2^2.N)^2$ where N is the order of point $P$

I also noticed from my googling that this curve isn't secure. Can any one explain why, and what that means?

In your particular case the order of the point divides $p-1$, this means that the embedding degree of your curve is 1.

You should be able to apply the MOV attack to transfer your instance of ECDLP into an instance of DLP over $\mathbb{F}_{p}^*$. This would allow you to use the Index Calculus to solve your problem.

As the Index Calculus is subexponential, it would improve the required time for your attack compared to a generic discrete logarithm attack on the elliptic curve (as the Rho or the BSGS).

To perform the MOV attack you should first find a point $R$ of order $n$ which is not a multiple of $P$. This should be easy given your curve. Proceed in the following way:

Randomly generate a point $R$ on the curve
Find its order
Most likely it will be of the form $a*n$, if not goto step 1
$R = [a]R$ will have order $n$

Then perform the Weil pairing of $P$ and $Q$ as:
$$
\begin{eqnarray}
w_1 &=& e(P, R)  \\
w_2 &=& e(Q, R) = e(kP, R) = e(P, R)^k
\end{eqnarray}
$$

If $w_1 = 1$ then goto step 1. Otherwise solve the DLP by finding the $k$ of $w_2 = w_1{^k}$ in $\mathbb{F}_{p}^*$ using Index Calculus.

The returned $k$ will be the $k$ you are looking for (the one of $Q=[k]P$)

This answer by Samuel Neves, which I've used to write this answer, links to Sage code to compute the pairing and has more details.

Edit: Thanks Maarten for finding the goto issue.


How reasonable is deriving the key a corpus of RSA-PSS signed messages? Given access to a 2048 bit public key, a large corpus of 2048 bit plain text messages and their signatures (RSA-PSS with SHA256 as the hash and MGF)  are any of the following statements correct:

Increasing the number of of messages available significantly increases the likelihood an attacker can reverse the private key
Decreasing the plain text message size significantly increases the likelihood an attacker can reverse the private key

Note: by significantly I mean "before the heat death of the universe" becomes a few hundred years. If instead it becomes half the heat death of the universe, I'm less interested.

We don't know any forgery algorithm which can do a better job if there are more signed messages available, or smaller signed messages available.

The best way we know to forge messages is to factor $n$.  The best algorithm we know to factor $n = pq$ when $2^{1023} < p < q < 2^{1024}$ are (near) uniform random primes, the general number field sieve, costs more than $e^{(\log n)^{1/3} (\log \log n)^{2/3}}$, and uses only the modulus $n$, without reference to any signed messages.

The standard PSS security theorem is that if you had an algorithm to forge signatures, then someone could use your signature forger as a subroutine in a program to invert $x \mapsto x^e \bmod n$ with essentially the same probability of success as the forger, and as many additional modular exponentiations as the forger makes hash or signing queries.  Consequently, PSS forgery can't be much cheaper than computing $e^{\mathit{th}}$ roots, but we don't know any way to actually do it besides factoring $n$ in order to compute $e^{\mathit{th}}$ roots in the first place.


Can I retrieve a re-hashed (hash) value, for instance by additional hashing? I have a double-SHA-256 of some text $$ h_2 = \operatorname{SHA256}(\operatorname{SHA256}(m)).$$ I don't need the plain text ($m$), but somehow I need to get first $$h_1 = \operatorname{SHA256}(m).$$

Can I have it ($h_1$) by keep hashing the second one ($h_2$)?
$$ h_1 = \operatorname{SHA256}(\operatorname{SHA256}(...\operatorname{SHA256}(h_2)...)).$$

Short answer; Almost NO!

Can I have it by keep hashing the second one?

There were great answers for the question; Cycles in SHA256
In short, if we model SHA256 as a uniform random function then the probability of element being on the cycle is
$$\frac{1}{\sqrt{\hspace{.03 in}2\hspace{-0.05 in}\cdot \hspace{-0.04 in}\pi} \cdot 2^{127}}$$
The average cycle length with expected value for SHA256 is $$2^{127} \sqrt{2\pi}$$
Simply consider the first hash $\operatorname{SHA256}(m)$ as the starting point;

As one can see that being on a cycle has a very low probability and you almost find none in a cycle since the probability is $\frac{1}{\sqrt{2\cdot \pi} \cdot 2^{127}}$.
Even it is on a cycle, you almost certainly can not calculate the cycle to find the pre-image since the average cycle length is $2^{127} \sqrt{2\pi}$.

These are from the result of Bernard Harris's magnificent work; Probability Distributions Related to Random Mappings in 1960.

Also, this exists in the Handbook of Applied Cryptography - Fact 2.37

tail lenght = $\sqrt{\pi n /8}$
cycle lenght = $\sqrt{\pi n /8}$
rho-lenght = $\sqrt{\pi n /2}$


Comparing the security when using fixed IV for CBC and CTR Assuming that I'm using fixed IV's for CBC mode and CTR mode. I know that in CBC, the blocks depend on the previous ones and on CTR they are all independent. Yet with the same key and fixed IV, the system wouldn't be secure in CTR and with fixed IV same plaintext would be converted to same ciphertext which causes another security issue. Even though I know these, I cannot decide which would be more secure when I use fixed IV's. Any help is appreciated.

If you reuse key&IV(nonce) in CTR mode you have almost no security.
You get a two time pad.
Xoring to messages, will eliminate the key stream and give you the XOR of the plain texts which usually gives you plenty of information.
With multiple such cipher text it gets even easier.
If you reuse IV and key in CBC mode, it isn't good, but it isn't anywhere near as bad. You can't trivially decrypt messages, even if you know parts of the message or you know a lot about the distribution of messages (e.g they are English language).
Having a predictable IV let alone a fixed one, allows you to mount a chosen plain text attack, which can verify guesses about any cipher text block. See:
Why is CBC with predictable IV considered insecure against chosen-plaintext attack?


Is it possible to make two files with the same size and the same MD5 and CRC32? I have seen a lot of different files with the same MD5s. For CRC32 is quite easy to find collision. But is is it possible to make size, and two different hashes the same?

I have seen many linux packages has only one SHA test-sum, why not to increase security with another hashing function?

(I am not asking about SHA family - answer is YES, possible, but MUCH MORE UNREALISTIC)

Is it possible to make two files with the same size and the same MD5 and CRC32?

It's straight-forward.

First off, we start with Joux's multicollision attack (PDF) to generate $2^{33}$ different same-sized files with the same MD5.  Here's how that works; the MD5 collision attack works by starting with an internal MD5 state $S$, and finding two different blocks $B_0, B_1$ such that, with the MD5 compression function, $\text{MD5Compress}( S, B_0 ) = \text{MD5Compress}( S, B_1 )$.  Finding such a $B_0, B_1$ is fairly easy.

What Joux's attack is ask us to do that 33 times to succesive states; and so we have $2^{33}$ different sequences (as there are $2^{33}$ different ways of selecting $B_0, B_1$ values) that all hash to the same final value.

Once we have that, we know that there exists a pair of files with the same CRC32 value (and actually, we don't need to search through them all, with CRC32, we can find such a pair with linear algebra)


Modulo properties of two prime numbers I am supposed to prove that $x = y \mod (pq) \iff x = y \mod p$ and $x = y \mod q$ with $p$ and $q$ are prime numbers. It somewhat sounds reasonable to me, but unfortunately I don't have any clue how to prove it.

That the left hand side implies the right hand side is easy, it follows from the following fact:

$$x\equiv y \mod{pq}\ \Leftrightarrow pq \mbox{ divides }x-y \Rightarrow p \mbox{ divides } x-y \mbox{ and } q \mbox{ divides }x-y$$

And so $x\equiv y \mod{p}$ and $x\equiv y \mod{q}$

Now, the point here is argument can be "reversed" in the case that $p$ and $q$ are relatively primes (and actually they are since we are assuming that they are different, if they're not, we can't obtain the result), it is, if $x\equiv y \mod{p}$ and $x\equiv y \mod{q}$, then p $\mbox{ divides } x-y$ and $q \mbox{ divides }x-y$, and as $p$ and $q$ are relatively prime (this is a well known theorem in number theory) we have that $pq$ divides $x-y$, thus $x\equiv y \mod{pq}$.

This is the general version of theorem I've wrote before:

Let $a,b,n\in \mathbb{Z}$ and suppose that $a$ divides $n$ and $b$ divides $n$, then $ab$ divides $n\cdot \mbox{gcd}(a,b)$. This, in the case that $a,b$ are relatively prime, gives the result i'm reffering to (because in that case $\mbox{gcd}(a,b)=1$).

Here's a small proof of this fact. Let $n=as$ and $n=bt$, write $\mbox{gcd}(a,b)=g$, we know that there exists $x,y$ integers such that $ax+by=g$ (see this post), then, multiplying this expression by $n$, we obtain $n(ax)+n(by)=ng$, replacing adequately, we have $(bt)(ax)+(as)(by)=ng$ and rearranging, we finally obtain $(ab)(xt+ys)=ng$ so $ab$ divides $ng=n\cdot \mbox{gcd}(a,b)$.


Key Committing AEADs There are multi-key attacks against some AEADs. In other words, multiple keys can be used to decrypt a message since multiple keys can be valid for an authentication tag. How would one go about adding key commitment to an AEAD like AES-GCM or ChaCha20-Poly1305? The three ways mentioned by libsodium are:

Key identifier in the nonce.
Key identifier in the additional data.
Zero padding prepended to each message that gets verified after decryption.

However, 3 could be vulnerable to timing attacks (since this verification occurs after verification of the authentication tag), and 1 makes handling the nonce more complicated. That leaves a key identifier in the additional data, but what's the best way of achieving this?
Could you just use the encryption key as additional data? Should you hash the key and use it as additional data? How about a keyed hash using the key and some other data?

How would one go about adding key commitment to an AEAD like AES-GCM or ChaCha20-Poly1305?

First off, let us start by reviewing how AES-GCM/Poly1305 works internally (and how these key commitment attacks work).
Here's a top level overview of how they work (and AES-GCM and Poly1305 work largely the same at this level): first the ciphertext and AAD are combined to form a series of field elements $M_n, M_{n-1}, ..., M_1$; the details of how they are combined differ between the two; however they both have the property that they can control the value of a specific message block $M_i$ by adjusting a specific ciphertext block.
Then, the take a key dependent value $H$, and compute in some finite field the polynomial:
$$M_n H^n + M_{n-1} H^{n-1} + ... + M_i H^i + ... + M_1 H^1 + F(key, nonce)$$
And that is the tag (well, not quite in Poly1305; the final addition is done modulo $2^{128}$, however that is only a minor complication for this attack).
The finite fields differ between the two (GCM uses $GF(2^{128})$, while Poly1305 uses the prime field $GF(2^{130}-5)$), but that doesn't matter.
Now, the attacker who is trying to find a message that has the same tag for two different keys (and hence would be accepted as valid under both keys) controls the ciphertext, and knows everything (the AAD, the key, the H values, and the values of $F(key, nonce)$.  So, what the attacker can do is fix the entire ciphertext (except for the part that contributes to $M_i$), and combine those parts of the tag computation into known constants $C, C'$, and then look for a value of the remaining ciphertext block that gives rise to an $M_i$ value that satisfies:
$$M_i H^i + C = M_iH'^i + C'$$
(where $H, H'$ are the internal $H$ values of the two keys).  This is an easily solved problem, leading to the message that would have the same tag value for both messages (and since the attacker knows everything, he can easily compute that common value).  Actually, it's a bit more complicated for Poly1305, as not all $M_i$ values can be obtained from a ciphertext block, however a nontrivial fraction can, and so the attacker can find such a value by adjusting another ciphertext block with not that much effort.
Ok, now that we have reviewed the attack, let us examine how well these three ideas would fare:

Key identifier in the nonce

In the above attack, this would modify the value $F(key, nonce)$ values to be dependent on the key; however that is already dependent on the key, and so the attack would proceed exactly as planned.

Key identifier in the additional data.

In the above attack, this would modify some $M_j$ values (the ones that are dependent on the AAD); however $j \ne i$, and because the attacker would know these $M_j$ values, this would just modify the $C, C'$ values that appear in the above attack, and so would not complicate this attack at all.

Zero padding prepended to each message that gets verified after decryption

The above attack doesn't address this at all.  Instead, this defense happens during the actual decryption step; in this step, the crucial plaintext block would be computed $P_i = C_i \oplus F( key, nonce, i )$, and to find two different keys that decrypt the $P_i$ block to all zeros (which is required for the message to be accepted with both keys), the attacker would need to find two keys where $F( key, nonce, i ) = F( key', nonce, i )$; there is no known weakness in either AES or ChaCha20 that could be exploited, hence the best attack known would be a birthday collision attack.  This indicates that to get a security strength of $2^k$ against this attack, we would need to prepend $2k$ zeroes (which may involve a collision attack across several blocks; this doesn't change the analysis).


Reasoning behind SHA-3 state array indexing I was reading through the SHA3 standard (https://dx.doi.org/10.6028/NIST.FIPS.202) and in the standard it defines how to construct 3D state array from a 1D array.
The state array is defined as follows:

For all triples (x, y, z) such that 0 ≤ x < 5, 0 ≤ y < 5, and 0 ≤ z <
w,
A[x, y, z] = S [w(5y + x) + z]

This indexing is a bit cumbersome because in some sense, y > x > z (I can clarify what I mean if requested). I think it would be more natural to swap the x and y indices and defined it as:

A[x,y,z] = S [w(5x + y) + z]

Is there a reason for the definition in the standard?

First let us have a look at the state representation.

  For all triples $(x,y,z)$ such that $0 \le x < 5$, $0 \le y < 5$, and $0 \le z < w$, $$A[x,y,z]=S[w(5y+x)+z].$$
  For example, if $b = 1600$, so that $w = 64$, then

A[0,0,0] = S[0]     A[1,0,0] = S[64]     A[4,0,0] = S[256]
A[0,0,1] = S[1]     A[1,0,1] = S[65]     A[4,0,1] = S[257]
A[0,0,2] = S[2]     A[1,0,2] = S[66]     A[4,0,2] = S[258]

A[0,0,61] = S[61]   A[1,0,61] = S[125]   A[4,0,61] = S[317]
A[0,0,62] = S[62]   A[1,0,62] = S[126]   A[4,0,62] = S[318]
A[0,0,63] = S[63]   A[1,0,63] = S[127]   A[4,0,63] = S[319]

and

A[0,1,0] = S[320]   A[1,1,0] = S[384]     A[4,1,0] = S[576]
A[0,1,1] = S[321]   A[1,1,1] = S[385]     A[4,1,1] = S[577]
A[0,1,2] = S[322]   A[1,1,2] = S[386]     A[4,1,2] = S[578]

A[0,1,61] = S[381]  A[1,1,61] = S[445]    A[4,1,61] = S[637]
A[0,1,62] = S[382]  A[1,1,62] = S[446]    A[4,1,62] = S[638]
A[0,1,63] = S[383]  A[1,1,63] = S[447]    A[4,1,63] = S[639]

If you look into the position of the bits. you notice that you can consider your state as an array of $\texttt{u_int64}$ (numbering $0 \to 63$, $64 \to 127, \ldots$), this explains the $w$ in the formula.

If you look at the ordering of the bits, you notice that we have the first plane ($y = 0$), then the second etc. Thus taking the 320 first bits select the first plane and so on.

Now if you look at the operations in Keccak:

$\iota$ operate on the lane $(0,0)$,
$\theta$ operates on column but depends on the parity of its neighbor columns,
$\pi$ and $\rho$ operates directly on the lane position
$\chi$ is applied to a row.

$\chi$ can also be seen as a 5-bits S-box that has been bit-sliced and to be applied $64$ times in parallel (see bellow).

We can thus select 320 bits and apply $\chi$ directly, the bits are grouped in such way that loading them consecutively will be fast (instead of fetching them at different positions). So we have a first reason to prefer this ordering.

Then we can have a look at $\theta$, it works mainly on columns but you can also consider doing it directly on planes (thus 320 times in parallel !).

Thus selecting the states by bloc of 320 bits and adding them from a vector point of view makes it fast.

We thus have here two operations ($\theta$ and $\chi$) which benefit greatly from the $w(5y+x)+z$ ordering.

Now if you assume the other ordering ($w(5x+y)+z$), notice that:

you have to fetch bits from 5 different position when you want to apply $\chi$.
you can only work on $\theta$ with a parallelism over the column and not the slate anymore.

TL;DR: $\chi$ and $\theta$ parallelism benefits a lot from this ordering (and also from a hardware point of view).


Zero-Knowledge Proof of a polynomial I have two secret values $L_1$, $L_2$, and two Pedersen commitments $C_1 = C(L_1)$, $C_2=C(L_2)$. The commitments $C_1$, $C_2$ are public. Given a challenge $c$, I want to output $d = c*L_1+L_2$ and prove in zero-knowledge that $d$ is formed correctly. What should the zero-knowledge proof look like?

Consider a multiplicative group of an order $q$ generated by some $g$. For simplicity, let commitment be $C_1 = g^{L_1}$. Consider a proof of knowledge of $L_1$ committed to at $C_1$. At the first step of an interactive proof, choose some $L_2$ at random and send $C_2 = g^{L_2}$ to the verifying party. Second step, receive a challenge $c$. Third step, send a response $d = c L_1 + L_2 \pmod{q}$. Now verify this response with $g^d=$ something computable by the verifying party. That is, an expression of something that was sent to verifying party before or while running the protocol.


Proving that there is no scheme which would be perfectly CPA-secure A private-key encryption scheme Π = (Gen, Enc, Dec) has perfectly indistinguishable encryptions under a chosen-plaintext attack, if for all probabilistic polynomial-time adversaries A it holds that
Pr[PrivK_cpa(n) = 1] = 1/2. I need to show that there is no encryption scheme that can satisfy this definition.

The perfect indistinguishably under a chosen-plaintext attack: Pr[PrivK_cpa = 1] = 1/2

implicates

the perfect indistinguishably in the presence of eavesdropper: Pr[PrivK_eav = 1] = 1/2.

Which, in turn, implicates perfect secrecy: Pr[Enc_K (m) = c] = Pr[Enc_K (m') = c] for all m, m' from M, c from C.

Is my argumentation correct to this point? If so, could you, please, tell how can I now find the contradiction between the scheme being perfectly secret and perfectly indistinguishable under a chosen-plaintext attack? Should I find the contradiction using the definition of the perfect secrecy (above-mentioned) or should I use the fact that |K| should be >= |M|?

I saw this post Is there such a thing as perfect CPA security? with the same question but it does not help as there the fact that Enc is probabilistic rather than deterministic is mostly discussed.

The perfect indistinguishably under a chosen-plaintext attack: Pr[PrivK_cpa = 1] = 1/2
Is my argumentation correct to this point?

No, because the question doesn't ask about 'perfect indistinguishability' (which would include computationally unbounded adversaries), just indistinguishability against probabilistic polytime adversaries.
Assuming that the adversary has access to the public key, then here is an adversary that achieves an advantage $> 1/2$:

Select a set of random coins; send them through the $Gen$ function

Compare the public key generated with the public key presented

If they are the same, use the private key generated to decrypt the ciphertext and use the resulting plaintext to make the decision.

If they are not the same, select a random bit and use that as the output.

Now, if this procedure selects a set of random coins that just happen to be the same as the coins used during the original key generation process, then this always achieves the correct answer (or, at least, with high probability if the public key system has a small probability of decryption failure); if it does not, then this gives the correct answer with probability at least 1/2 ("at least" because there may be other sets of random coins that result in the same public key; those would also give the correct answer).
Hence, if $\lambda$ random coins were used in the key generation process, this gives the correct answer with probability $2^{-\lambda} + 0.5(1 - 2^{-\lambda}) > 1/2$


What if message is longer than keystream ? I have read that stream ciphers can be used to encrypt messages/streams of arbitrary length (cf. the description of the stream cipher tag). However, there are stream ciphers that create a keystream of fixed length and XORs message and keystream bit by bit.

Therefore, I wonder, what happens if the message length is longer than the length of the keystream ? Is the keystream applied repeatedly to the remaining parts of the message in this case ?

TL,DR: “arbitrary length” primarily means “the length doesn't have to be a multiple of a certain size”.

  I have read that stream ciphers can be used to encrypt messages/streams of arbitrary length (cf. the description of the stream cipher tag).

That's generally the case, except that most stream ciphers have a maximum length. The maximum length is typically far larger than any practical message, so in practice stream ciphers can encrypt messages of arbitrary length.

The important thing about the “arbitrary length” of the message for stream ciphers is that you can stop the stream at any point. This is unlike block cipher modes, which can only encrypt a message whose length is a multiple of the size of a block. To encrypt a message with a block cipher, you need both a block cipher mode (to reach lengths larger than one block) and a padding mode (to cope with the last block, which in general is only partially filled).

For example, AES is a block cipher with a 16-byte block size. CBC is a block cipher mode (i.e. a way to turn a way to encrypt a fixed-size block into a way to encrypt a list of blocks). You can encrypt a 32-byte message with AES-CBC by running CBC for two blocks, but you can't encrypt a 31-byte message, because this isn't a whole number of blocks. You need to additionally specify a padding mode, e.g. PKCS#7 padding. You can encrypt a message of arbitrary length (in bytes — and again, up to a very large maximum) with AES-CBC-PKCS7 — first pad the message to 32 bytes with the PKCS#7 padding algorithm, then apply CBC for two blocks. In contrast, a stream cipher can encrypt a 31-byte message simply by calculating the cipherstream for 31 bytes. For example, to encrypt a 31-byte message with AES-CTR, you simply calculate 31 bytes of cipherstream and xor that with the message. Because CTR builds a stream cipher on top of a block cipher, calculating the cipherstream involves calculating two blocks (32 bytes) of ciphertext and discarding the last byte.

Padding is a reason to prefer stream ciphers to block ciphers. Padding looks simple, but it's actually subtle. In particular, bad treatment of padding on the decryption side can lead to padding oracle attacks. That being said, if the block cipher is used in a properly designed authenticated encryption algorithm, only the designer of the authenticated encryption algorithm needs to worry about this, not the end-user.

  However, there are stream ciphers that create a keystream of fixed length and XORs message and keystream bit by bit.

If the keystream is of fixed length, then it's a one-time pad, not a stream cipher. That's a matter of terminology.

  Therefore, I wonder, what happens if the message length is longer than the length of the keystream ?

Then you need a more complex protocol, with different keys for different parts of the message (i.e. key renewal). But in practice that basically never happens — if you have that much text to encrypt, it's almost always already split into separate messages.

  Is the keystream applied repeatedly to the remaining parts of the message in this case ?

Absolutely not! Applying the same keystream more than once is very insecure. It's a two-time pad and that can leak the whole message.


Why is Lamport-Diffie secure? Why is Lamport-Diffie secure? I note that there is a demonstration based on onewayness (in the book postquantum cryptography). But a one way function is not sufficient to ensure that it can not infer some bits or any feature of the key signature.

Lets assume an adversary knows one LD signature for message $M$ as well as public key $pk$ and can generate a forgery for an arbitrary different message $M'$. Clearly, there exists at least one bit position where the messages differ, i.e. $M_i \neq M'_i$, as $M \neq M'$. So, for simplicity assume there is only one bit difference. Then the adversary can take all signature values for the signature on $M'$ from the signature on $M$ besides the value for this single bit position. For the signature value of this bit it must hold that $f(sig_i) = pk_{i,M'_i}$ as otherwise verification would fail.

So if the adversary is able to generate a valid forgery it obviously is able to find a value $x$ that satisfies $f(x) = pk_{i,M'_i}$ for given $pk_{i,M'_i}$. This is per definition finding a preimage of $f$.

To get back to your question: The adversary might learn some information about $sk_{i,M'_i}$ from $pk_{i,M'_i}$. But that is not enough to produce a forgery as a forgery requires knowledge of a complete value $x$. Even more: it is not required that $x = sk_{i,M'_i}$ for the forgery to be valid.


Missing public exponent Using LUC RSA, I have a list of 8 public keys $(R_1,n_1)$ through $(R_8,n_8)$, and a list of $8$ messages $M_1\dots M_8$. The messages have all been  double encrypted. However, one of the public key exponents, $n_5$, is not given. The problem is to decrypt all of the messages, and so I must also determine the value of the missing $n$. The hint is that the exponent was constructed "poorly".

Having factored all (including $R_5$) but two of the $R$s, I have decrypted $5$ of the messages.

My question is, what exactly is a poorly constructed public exponent look like, and how can I use what I have been given to discover the missing $n$?

Given the length of one particular encrypted message ($M<R$), it is likely that it was encrypted the last time with $R_5$.

So, I suppose what I'm asking is: Can you solve for n given $E=M^n \mod R$ where only R (public modulus) and E (ciphertext) are known? I suppose that's basically the DLP...

The hint as stated in the question is that the missing public exponent $n_5$ was constructed "poorly". But it could be that some other public exponents $n_s$ were constructed similarly, and this could reveal what "poorly" is. I'd check if some pattern emerges from

the seven other $n_s$
the five possibly different $n'_s=n_s\bmod\Gamma(R_s)$ for $s$ such that, further, $R_s$ is of known factorization as $P_s^\,Q_s$ so that we can compute the quantities $\Gamma(R_s)=\operatorname{lcm}(P_s-1,P_s+1,Q_s-1,Q_s+1)$
the five $m_s={n_s}^{-1}\bmod\Gamma(R_s)$ for such $s$.

If nothing comes out of it, we can try to decrypt with guesses of $n_5$ and see if the plaintext's characteristics match those of the other plaintexts (e.g. range, padding, being composed in a certain alphabet/language..). Reasonable guesses could be:

the seven other other known $n_s$
the know $n'_s$ if different
the few smallest positive $n$ that are coprime with $\Gamma(R_5)$
$n=m^{-1}\bmod\Gamma(R_s)$ for the few smallest positive $m$ that are coprime with $\Gamma(R_5)$. This simplifies into raising the ciphertext to increasingly large powers $m$, and further speedups are possible for that by precomputing the ciphertext to small even powers.

I do not see that we could mount a discrete logarithm attack as considered in the end of the question, for lack of anything suggesting known plaintext.


What are the "natural language input messages" that were used to derive Streebog's constants? This is more "cryptography trivia" than proper cryptography, but I'm curious. In Note on Streebog constants origin, V. Rudskoy says that the constants used in the definition of the Streebog hash were derived by taking a "Streebog-like hash function" (defined in the note), and running it on "12 different natural language input messages".

These 12 messages are given in a table, but only as opaque hexadecimal strings that are presumably some kind of encoded Russian text (maybe cp1251?). What is the encoding, and what do the texts mean, for those of us who don't read Cyrillic or speak Russian?

If you reverse the bytes, and you decode in cp1251, you get a series of Cyrillic names.

$C_1$: Гребнев
$C_2$: Сергей Владимирович
$C_3$: Дмух
$C_4$: Андрей Александрович
$C_5$: Дыгин
$C_6$: Денис Михайлович
$C_7$: Матюхин
$C_8$: Дмитрий Викторович
$C_9$: Рудской
$C_{10}$: Владимир Игоревич
$C_{11}$: Шишкин
$C_{12}$: Василий Алексеевич

I leave it as an exercise for the reader to find who all these people might be.  Hint: Рудской transliterates to Rudskoy.


TLS: Risks of using a NULL cipher with encryption implemented in application? We have a browser-launched JNLP/WebStart application that is no longer able to establish client-server CORBA/IIOP communications across TLS 1.0/1.1 due to relying on a cipher suite that uses an obsolete encryption algorithm for confidentiality, now disabled in Java 8u171.  Client is Java.  Server is C++ on Solaris.

The TLS connection that relies on the compromised cipher suite is coming from inside the guts of an antiquated, unsupported ORB implementation (Visibroker 5.2.1).  It's source code is not available.  It does NOT support a stronger cipher suite.

Unfortunately, we are not able to replace/upgrade the ORB at this time, so we are looking for a safe, near-term workaround that allows for secure communication.

The ORB does support some cipher suites with a NULL EncryptionAlg where the KeyExchangeAlg and MacAlg are still considered approved in section 3.3.1 of NIST SP 800-52 Rev 2 (Draft 1/2018).

My idea is to configure the ORB to use one of these cipher suites and then rely on our application to provide confidentiality with a NIST-approved encryption algorithm.

What additional security risks exist, if any, with such an approach compared to having the cipher done by the TLS implementation?

Am I opening up a gaping hole in security by doing so or are they equally secure assuming the application code is implemented correctly?

I'm considering using the same technique described in RFC5246 (TLS 1.2) in our app's code to establish a shared secret between client and server.

Please let me know if you have any advice or suggestions.

Thank you!

EDIT 5/26/2018 attempting to provide more detail and some clarification of what I was considering:

My idea was to configure the ORB to use a cipher suite with a NULL encryption algorithm, such as TLS_ECDH_ECDSA_WITH_NULL_SHA.

I would then change our application code to encrypt any data to be sent across the ORB's unencrypted TLS socket with a NIST-approved algorithm such as AES_256_CBC.  Since our application does not directly use the ORB's TLS socket, it would encrypt fields of distributed objects before allowing the ORB to transmit them across the socket.  Likewise, it would decrypt those fields on the receiving side.

Am I losing any of the ORB's TLS session-provided guarantees besides confidentiality (i.e. client/server authentication, message integrity, replay protection)?  Here's a stackexchange answer that suggests the 1st two are kept: TLS: Is Integrity assured when using NULL cipher

If the non-confidentiality guarantees still hold, is there any security risk in sharing a symmetric key if the Java client generates the key, encrypts it with the server's public key, and then transmits that to the server across the unencrypted TLS socket (via ORB vendor API)?  The server of course is the only place that has the matching private key.

I'm unclear on the specific risks associated with this approach beyond the potential for bugs in our application logic to encrypt and decrypt every distributed object field.  Clearly this is ugly and not a long-term solution by any means, but I hoped it could be used in the short-term while we work on replacing/upgrading the ORB.  If it isn't a viable approach, then I need to find an alternative such as the tunneling that Maarten suggested.

The problem is that the session keys within TLS are bound to the TLS session. If you just generate your own keys then that particular binding is lost. You might be able to hack or retrieve information from the TLS session to bind it again, but that would be rather like hacking.

Establishing the keys yourself will very likely lead to a significantly worse protocol than using TLS itself; you'll be bound to make all mistakes in SSL 1.0 to TLS 1.2 all over again.

Instead I propose that you keep to the current TLS to the server. However, that TLS session itself can be tunneled though a much more secure TLS session, possibly using an intermediate node on the server side. Some networking tricks may be necessary of course (e.g. to allow for reverse DNS checking by the original server).


Size of $E$ over $\mathbb{F}_p$ contains $p+1$ points I am struggling to prove this claim:

I proved that the map $x\mapsto x^3+1$ is a bijection from $\mathbb{F}_p$ to itself if we have that $p\equiv 2\bmod{3}$. We have to use this fact to prove that the elliptic curve $E:y^2=x^3+1$ over $\mathbb{F}_p$ contains precisely $p+1$ points.

I don't understand how many points will be on the curve. For each value of $x\in\{0,1,2,\ldots,p-1\}$ we will get a distinct result after computing $x^3+1$. But how does that tell me how many points will be on the curve?

For each point it can be paired with either two or zero $y$ values, right? But I don't know how many squares there are that are less than $p$.

I ask either for help explaining this, or ideally resources I could use to understand the theory behind this so that I can solve it myself.

For every $y \in \mathbf F_p$, there is a unique $x \in \mathbf F_p$ such that $(x,y)$ is on the curve, namely $x = \phi^{-1}(y^2)$, where $\phi : x \mapsto x^3+1$. Adding the point at infinity, that gives $p+1$ points.


What's the truth about this "absolutely unbreakable" cipher? A story appeared on Forbes today claiming that we now have an absolutely unbreakable cipher. It cites a paper published in Nature Communications. However, I'm skeptical:

  But what if there were a method of enabling data to be sent using an "absolutely unbreakable" one-time communication technique? What if that technique could achieve perfect secrecy cryptography via correlated mixing of chaotic waves in an irreversible time-varying silicon chip?

That seems like a lot of buzzwords and doesn't sound convincing.

  With no software or code to manipulate, traditional methods of cracking computer encryption are irrelevant

  Again, Dr. Cruz reiterated that there is no code to manipulate, and the limited software is ROM based, so traditional methods of hacking encryption are irrelevant.

Don't ciphers and their weaknesses exist independent of software and code? Solitaire has neither software nor code, but has weaknesses.

  The cryptographic keys generated by the chip, which are used to unlock each message, are never stored

You need the keys to decrypt the message, so even if they're never stored, something good enough to reconstruct them must necessarily be stored.

  It is claimed that even facing an attacker with "unlimited" technological power, even if they could access the system and copy the chips, would be unable to break the encryption because it is protected by the second law of thermodynamics and the "exponential sensitivity of chaos."

I really don't like the sound of this.

  Professor Andrea di Falco of the School of Physics and Astronomy at the University of St. Andrews, another author of the study, said that "this new technique is absolutely unbreakable, as we rigorously demonstrated in our article."

A really extraordinary claim.

  The second law of thermodynamics prevents this attack. Every time Alice and Bob change the chip with an irreversible process, they increase the total entropy of the system and the environment, creating new chaotic structures exponentially different from the ones used in the communication (conditions 3 and 4). If Eve accesses the system, it is impossible to recreate the initial chips and to perform any search, as this requires reverting the transformation of Alice and Bob with an entropy decrease, thus violating the second law.

This is contrary to my understanding of the second law of thermodynamics. Can't you easily decrease entropy in systems that aren't closed (such as the chips), just by increasing it more outside the system (exhaust heat somewhere)?

So is this new cryptosystem legit, or is it just more snake oil? If it's legit, then what are the explanations for my above concerns? If it's snake oil, how did it manage to dupe both Nature Communications and Forbes?

I will go out on a limb here and say that it reeks of snake oil. I have seen the answer by @dirdi, but I am very skeptical. It is clear from the paper that the authors have almost no understanding of cryptography: they refer to algorithms used as DES, AES and RSA, and that quantum computers break them all.

We know that quantum computers only have quadratic speedup to break symmetric ciphers, to the best of everyone's knowledge. Also the reference to DES, AES and RSA together is very suspect. I quote: "Conventional cryptographic schemes based on DES, AES and RSA encode messages with public and private keys of short length." Huh???

There is no theoretical model for this, like one has for quantum computation (with all of the problems that exist there). Rather, it is more experimental in nature - and we know where that tends to end. Bottom line, this looks really bad and like a lot of other cases where people from other fields think that they can solve all of the world's hard cryptographic problems without knowing anything about cryptography.


DES with the bitwise complement of a key I was reading upon Biham and Shamir's paper and a fact has been presented over there:
if $ P_1 = \bar P_2$ and I choose a key $K_1 = \bar K_2$ then in that case
$$T_1 = DES(P_1, K_1)$$
$$T_2 = DES(P_2, K_2)$$

then $T_1 = \bar T_2$ . Does this hold for only that particular combination of S-box or it will be same for any S-box combination. I mean if I change S-boxes randomly then will it still be same?

Also there is one more thing mentioned on the paper, but I am not able to get it. PFB the image.

Here output $T$ will be $\bar T_2$ only if I $P_2$ was inserted with $\bar K$. And clearly I am entering $P_1$ (which is $\bar P_2$) hence the output can never be $T_2$. Please correct.

This is known as the complementation property of $DES$; I had thought that it actually predated Biham and Shamir's work.

In any case, your questions:

  Does this hold for only that particular combination of $S$-Box or it will be same for any $S$-Box combination?

It'd remain even if you change the $S$-Boxes arbitrarily. The reason for this is that it is not actually caused by the $S$-Boxes. $DES$ generates the inputs to the $S$-Boxes by $XOR$ing $R_i$ with $k_i$. The reason this property holds is if you complement $R_i$ with $k_i$, the result of the $XOR$ won't change, and so the input the to $S$-Box is exactly the same (and hence the output of the $S$-Box is exactly the same).

  Also there is one more thing mentioned on the paper, but I am not able to get it.

Actually, that's a fairly straight-forward exploit of this property. I'll see if I can state it more explicitly.

Suppose you knew the ciphertexts for two plaintexts, and these plaintexts happened to be the complement of each other. That is, we know the value $T_1 = E_k(P_1)$ and we also know the value $T_2 = E_k(P_2)$, where $P_1$ and $P_2$ are complements of each other (that is, wherever $P_1$ has a $0$ bit, $P_2$ has a $1$ bit, or in other words, $\overline{P_1} = P_2$

Consider further that we don't know the key $k$; and we'd like to find it.

One thing we can try is pick a random key $k'$, and do a trial encryption of $P_1$ with it.  If our $k'$ just happened to be the value $k$, then $E_{k'}(P_1)$ would be $T_1$, and so we know know that $k'$ is likely to be the correct value.

However, consider if our $k'$ is the complement of $k$ (that is, we got every bit wrong).  In that case, the key complementation property would hold, and we would have $E_{k'}(P_1) = \overline{E_{\overline{k'}}(\overline{P_1})} = \overline{E_k(P_2)} = \overline{T_2}$, that is, we would see the bitwise complement of $T_2$.  So, if we see that value, that also tells us what the key is likely to be.

Hence, by doing a single $DES$ encryption, we can actually test two keys -- that's what Biham and Shamir are pointing out.


Could eVoting on the bitcoin blockchain be done? I'm basically a crypto noob (and not an english native), so please be indulgent :)

I thought about if you could realize an eVoting system with bitcoin.

I see 2 major requirements:

each citizen can only vote once
votes musn't be traceable

I imagined the government could give each citizen a private key (with their passport for example) and make the actual voting a multisig procedure, where you need to provide the government provided signature plus your own to sign your vote.

Now for my actual question (thx for your patience so far):

Is there some kind of math magic, that makes sure those 2 requirements are met? In other words: Could you, cryptographically use two private keys to sign a transaction, ensuring that one key was issued by a certain CA (= the government) without being able to trace this to the actual user (keeping the vote anonymous).

Yes, it could be done. However, it would work a little different from what you imagine.

The government can create a new blockchain operating under zerocoin rules. The government could then distribute one satoshi per citizen. This distribution could happen for example by letting each citizen visit a government office to present their passport and receive their satoshi. This satoshi on the particular blockchain constitutes permission to vote for this election.

After distributing the satoshis, the government would then announce the candidate parties in the form of zerocoin addresses. Each citizen could then vote for the party of their liking by transferring their satoshi to the account of the party they are voting for.

Finally, when the elections are over, the blockchain can be frozen at a particular block number and each party can reveal their received amount. These amounts can then be compared to elect a winner or counted to receive seats in a parliament.

This scheme satisfies both your stated properties of double-spending prevention and vote secrecy.

However, this is not a good voting scheme, as it has many problems. One important problem is coercion; a citizen can be forced to give away their vote at gunpoint.


How is information disclosed by modular multiplication? Consider the case that

$c = a \cdot b \mod p$

where $p$ is a known prime and $0 < a < p$ and $0 < b < p$ are unknown integers numbers. Furthermore, some bits on the value of $c$ are known.

Q1: Can an attacker learn some bits of $a$ using this information?

The question is based on the following non-modular example:

$a = x_1 \cdot 2^z + x_0$

and

$b = x_2 \cdot 2^z + x_3$

gives the product:

$a \cdot b = x_1x_22^{2z} + (x_0x_2+x_1x_3)2^z + x_0x_3$

Then if anyone knows the $z$ least significant bits of $a \cdot b$ (the product $x_0x_3$), then some of the divisors of $x_0x_3$ is equal to $x_0$, allowing to bound the possible values of $x_0$ to the possible divisors of $x_0x_3$.

Q2: Can this non-modular analysis be applied to the modular one ?

Can an attacker learn some bits of a using this information?

No.  In the case of multiplication modulo a prime, we have, for any possible value of $a$, there is a unique value of $b$ that makes $a \cdot b \bmod p$ give any particular value of $c$ in the range $(1, p-1)$.

That is, even if we knew all the bits of $c$, no particular value of $a$ are any more likely than any other (assuming we have no information about $b$).  And, in particular, we have no information on any of the bits of $a$ (other than what's implied by $1 \le a < p$, which we already knew).

Any observation in the non-modular case (where this observation does not apply) doesn't apply to the modular case.