How to prove that a hash or an encrypted message was obtained from a plaintext that has a certain pattern? I have the following idea of implementing a lottery game:

we have all the numbers from 1 to 40
we generate a permutation of those numbers which will be the lottery solution
participants need to guess that permutation to win the pot.

The implementation will be in a smart contract.

The game will have a timer, let's say a couple of minutes. If the pot is not won during that timespan, that game ends, to prevent brute-force attacks; afterwards, we can reload the game with a new permutation, but this is not relevant at the moment.

Now, my question is the following: how can we make sure that a valid permutation was generated at the beginning of the game? Any participant should be able to verify that a lucky permutation exists. I was thinking of storing the permutation as a hash and then compare the participant's hash with our hash, but it does not assure that we didn't hash garbage. Furthermore, besides hashing, my ideas point to some public key cryptography algorithms, but I can't figure out how to demonstrate that the encrypted message was obtained from a plaintext that has a certain pattern.

Therefore, I ask you, my fellow crypto-enthusiasts, is there any secure possibility to achieve this?

Thanks in advance.

You are correct that a normal hash can't do what you want.  They are designed to not leak any information about the message, so given just the hash output you can't determine if the message has any particular structure.

You can use format-preserving public key encryption on your messages to produce outputs that have the same structure as the inputs no matter what that structure is.  In this way, you have defined a permutation on your legal messages so every output has a pre-image.  In fact, the person running the game doesn't even need to know the answer in order to start a round.  That is, they can set a target value without picking a solution and hashing it.

In practice, this can be easier for some message types than others.  For your permutation example, there's a natural way to map messages to the range $[0, n!)$ so that it's simple to determine if a value is legal.  On the other hand, since your message space ($40! \approx 2^{160}$ bits) is so much smaller than the block size of a reasonable ECC key, it will take a lot of encryption operations to produce a legal message.

Maybe you can use another one-way function like $f(x) = g^x \mod p$ with a $p$ close to the number of valid messages.


How to determine if padding has been used while encrypting a message with RSA? I am trying to decrypt a RSA encrypted text file. I have a 2048 bit public key.
Analyzing the public key with openssl reveals the exponent used is 3.

openssl rsa -pubin -inform PEM -text -noout < publickey.pub

Public-Key: (2048 bit)

Modulus: [..snipped..]

Exponent: 3 (0x3)

After some googling, I found out that the text can be decrypted using eth root attack, if message was not padded. Since attempts to decrypt message failed, I'm doubting my assumption that padding had not been used. Is there any way to know it for sure?

Given the public key and a single encrypted file, the only way to check is to take the integer $e$th root of the ciphertext and see if the resulting value "makes sense" (where whether or not it makes sense is very context specific to the application at hand).

If you have access to additional information you can figure it out.

Access to an encryption oracle
For example, if you have access to an encryption oracle, i.e., something that will encrypt whatever you send it. Since you know the exponent is $3$, just send it the plaintext $2$, if it returns $8$, you know it is unpadded.

More generally, you could have it encrypt the same plaintext twice and see if they are equivalent. This would work especially well if the plaintexts must be of a specific, but understood format where something like $2$ would be rejected.

Access to executable code
If you have access to the source code doing the encryption, you can reverse engineer it to figure out what it is doing.

Access to decryption oracle
Ask it to decrypt your ciphertext and see what the answer is. Then encrypt the resulting plaintext yourself with no padding.


Is there a cryptographic algorithm which is immune to side channel attacks? Is there any cryptographic algorithm immune to side channel attacks based on scan chain? In VLSI point of view.

A cryptographical algorithm can't be immune or not immune to side channel attacks; this is because a side channel attack attacks the implementation and not the actual algorithm.  Any algorithm that uses secret data can be implemented in a way that has side channel attacks, and any algorithm can be implemented in a way that may be resistant (the hard-core side channel attack guys will say that no implementation is totally immune) to side channel attacks.

That said, there are certainly algorithms that are easier to implement in a way that resists side channel attacks.


ECDSA with common nonce? I'm new to cryptography, and I've searching about ECDSA because I'm trying to solve a CTF.

I've already check this site and Google, and I think I'm in the right path, but probably I am missing something.

I have access to messages and the ECDSA signature that they generate. The format is always the same:

Example of a message:

{"session_id": "6621a96c7db568374f2885d6d135f395010e75a94ec2233a433ff8e2", "user": peter}

And the signature have always the same first half.

znnlVaDhCokfqzU5figrY2cZ1nk87rH/

Example of two signatures:

znnlVaDhCokfqzU5figrY2cZ1nk87rH/+Zc/DvAEIyjZ4pv8SVmCsWLtq+yJrtFJ
znnlVaDhCokfqzU5figrY2cZ1nk87rH/zcCHDV2rLJ6nhdjE9vzblfpkzrhqzVjY

This looks like signatures generated with NIST192p curve (because of the size) ?

There are similar CTF that used the same thing as this one, and a solution like this one: http://ropnroll.co.uk/2017/05/breaking-ecdsa/

But the new generated signature doesn't start with the same part as the above ones.

They seem to be based on this one, https://antonio-bc.blogspot.com/ (you can look for ECDSA).

Here is again another CTF with a similar issue, but with a different curve. http://itemize.no/2016/08/26/IceCTF-contract-task/

Also I've checked the video from LiveOverflow that tackle the same issue, https://www.youtube.com/watch?v=-UcCMjQab4w

Since these are solutions for previous CTF, I'm thinking the the way I'm creating the messages isn't the same as the server.

This ECDSA implementation should be vulnerable, right ?
This is the modified code that I have right now.

You are right. And this had been exploited in the past in the PS3 and Bitcoin wallet events.

The first half of the signature is the x coordinate of $k \times G$, and $k$ is the ephemeral key that must be unique to each signature generated. If it's static then the following formula would recover the private signing key:

$k = {{z_1 - z_2} \over {s_1 - s_2}}$ and $d = {{sk-z} \over r}$ where $z_1$ and $z_2$ are the truncated hash bitstring, $s_1$ and $s_2$ are the two corresponding signature component, $r$ being the fixed part in both signatures, and $d$ the private key we hunt.

For more, Wikipedia has an article covering ECDSA and its security.


Half of any bitcoin (crypto) public key - (public key half) is possible I found a topic on bitcointalk

Public key x and y == Double(Half of the Public key x and y)

half any public key is possible how that possible , in crypto there is subtraction and multiplication only then how divition

one post Sure, just multiply the point by 2^-1 (mod n).

can some one explain more which point to multiply and what is 2^-1 (mod n)

Half of any bitcoin (crypto) public key - (public key half)

ECC is cryptography over an elliptic curve group.

Firstly you have an elliptic curve, e.g. Bitcoin uses a Koblitz curve secp256k1 $y^2 = x^3 + 7$.

The group is defined over curve points over a finite field $F_p$ (integer modular $p$). The group elements are points on the curve. A point in the affine form consists of two coordinates $P =(x,y)$ where $x,y\in F_p$.

For group elements, you can do point addition $P+Q$, as well as scalar multiplication $sP$, where $s$ is an integer in $Z_n$ where $n$ is the order of the group (how many elements in the group).

A public key in bitcoin is a point $P$. To do $\frac{P}{2}$, you multiply $\frac{1}{2}$ to $P$ where $\frac{1}{2} $ is the multiplicative inverse of $2$ in $Z_n$. It is an integer that can be found using the extended Euclidean algorithm and is 57896044618658097711785492504343953926418782139537452191302581570759080747169 in the case of secp256k1.


What is perfect collision-resistence in probability terms? update: removed lots of stupidity... sorry. I didn't know I can be this stupid but I achieved it.

1. Goal

Let $\mathcal{D}$ be the universal space of our plain data. Our goal is to find a function $h:\mathcal{D} \rightarrow \{1,0\}^n$ where $n$ is some positive constant, such that:

For any $d_1,d_2 \in \mathcal{D}$, the probability that $h(d_1) = h(d_2)$ is $1/2^n$. I.e. it's very unlikely to have collisions.

Note 1: the reason I require the probability to be $1/2^n$ is because I think this is the minimum possible collision probability. I would also appreciate if anyone could correct me on this.

2. Questions

Is $1/2^n$ the minimum achievable probability for collisions on any dataset?
Any of my methods are perfect for any dataset? I.e. not just best on average, best on specific datasets as well.
Can you propose one that is perfect on all dataset? (would be great if you can describe it in probability terms too).

3. My attempt

Let $z:\mathcal{D} \rightarrow \mathcal{Z}$ be a function such that for any $d\in\mathcal{D}$:

There is a function $u$ such that, for any $d\in\mathcal{D}$, $u(z(d)) = d$.
$\texttt{len}(z(d)) = H(d)$ where $\texttt{len}(z(d))$ is number of bits in $z(d)$ and $H(d)$ is Shannon's entropy of $d$.

I.e. $z$ is a perfect lossless compression function.

Ideally, we wish if $\texttt{len}(z(d)) \le n$ is always achievable. This way we can use $z$ as a perfectly collision-free implementation of $h$.

But in reality we can't do that as some input $d$ could contain too much information to be represented losslessly in $n$ many bits.

For simplicity, we will assume that, for any $d \in \mathcal{D}$, $\texttt{len}(z(d)) \ge n$.

This way, if the perfect compression function $z$ is known, then finding the perfect collision-free hashing function $h$ is a matter of choosing which of the bits in $z(d)$ to be kept in $h(d)$.

The process of deciding which bits to be kept in $h(d)$ needs to only satisfy:

For any $d_1,d_2\in\mathcal{D}$, probability of $h(d_1)=h(d_2)$ must be kept $1/2^n$.
The process must be producible. So computing $h(d)$ now should give us the same output if we compute $h(d)$ later on in the future.

3.1. Choosing $n$ bits method 1

For any $d\in\mathcal{D}$, assume that the early bits in $z(d)$ are more important than the latter bits in helping us set  $d$ apart from others in $\mathcal{D}\setminus\{d\}$.

Therefore, since early bits are most important, we just choose the first $n$ bits. I.e. $h(d) = z(d)[1:n]$, where $z(d)[1:n]$ denotes to the first $n$ bits in $z(d)$.

Note 4: I implemented this in Python here (in case one day someone [me included] wishes to evaluate these hashes against others to see how bad they are).

3.2. Choosing $n$ bits method 2

Unlike method 1, here we assume that any bit is equally important to any other bit. So instead of choosing the first $n$ bits in $z(d)$, we choose the $n$ bits randomly from $z(d)$. In order to make this reproducible, we seed the random selection by $z(d)$ itself.

In Python-inspired notation, it looks like this:

First we set the seed of the PRNG $\texttt{random.seed}(z(d))$.
Then we $z_{\texttt{shuffled}}(d) = \texttt{random.shuffle}\big(z(d)\big)$.
Finally $h(d) = z_{\texttt{shuffled}}(d)[1:n]$.

Note 5: in my view if $z$ and the PRNG used in the random shuffling are perfect, then this method is a perfect collision-resistant hashing function under this assumption which states that all bits in $z(d)$ are equally important.

Note 6: I have coded this in Python and it can be found here.

For any fixed data set, you can spend computation up front on the data set to construct a perfect hash $h_{\mathcal D}\colon \mathcal D \to \{0,1,2,\dots,|\mathcal D| - 1\}$ which has no collisions, implemented by software such as gperf.
In cryptography, we are seldom worried about random data—we can control keys and choose them randomly and keep them secret, but we usually assume that the adversary has arbitrary control over the data and can choose the most evil, awful, worst-case data imaginable.  So there's not much in cryptography to help you with finding a cheaply computed fixed hash function $h$ such that $\Pr[h(d_1) = h(d_2)]$ is bounded for some distribution on $d_1$ and $d_2$.  There's arbitrarily much heuristic empirical literature on the subject of finding ‘good’ hash functions on particular distributions like English text, like Bob Jenkins' compendium, but that's largely outside the domain of cryptography.
A ‘cryptographic hash function’ like SHA3-256 can be treated as if it were a uniform random function that everybody can evaluate.  That may sound like exactly what the doctor ordered for a hash table, and you can use it as a hash for a hash table, and in applications like a distributed hash table or content-addressed storage system open to anyone in the world it may even be essentially the only reasonable kind of choice—but if you take only (say) the low 12 bits as the index into your bucket array or open-addressing array, an adversary can work offline to find lots of 12-bit collisions quite cheaply even if they don't have any shortcuts beyond evaluating SHA3-256.  These functions are also not very fast, because there seems to be a high cost to pay for preventing any shortcuts to finding collisions in the whole function, as we discovered the hard way with MD5 and SHA-1.
How can you set a bound on collisions in a secret hash function, e.g. in an application server that has a private in-memory cache, where the hash function need not be shared with the general public?
If you allow $h$ to vary randomly, then for any fixed $d_1 \ne d_2$, you can have $\Pr[h(d_1) = h(d_2)] \leq 1/2^n$; in this case we call $h$ a universal hash family, or an $\varepsilon$-almost universal hash family if $\Pr[h(d_1) = h(d_2)] \leq \varepsilon$, and there are various standard efficiently computed examples (paywall-free: (a), (b)).  A typical example in cryptography, for message authentication, is to choose two elements $r, s$ at random from a field of about $2^{128}$ elements, e.g. $\operatorname{GF(2^{128})}$ in GHASH or $\mathbb Z/(2^{130} - 5)\mathbb Z$ in Poly1305; interpret 128-bit chunks of a message $m$ as coefficients a polynomial in the field; and compute $h(m) = m(r) + s$.
You might consider using a universal hash family for a hash table.  For a non-adaptive adversary who sends you all input before you operate on it, a universal hash family is a good way to cheaply compute hashes with low probability of collisions.  But if the adversary can adaptively submit inputs based on the timing of your past operations, they may be able to discern whether a collision happened and exploit it to make more collisions in a denial of service attack.  In applications with an adaptive adversary, you really want a pseudorandom function family like SipHash.  More details on universal hash families vs. pseudorandom function families.
Further reading on collision-related metrics in cryptography.


Is there an advantage to storing keys split between several hashes? I have a question about the way to store a key or password that was used for encryption, so that the application can check if the user put in the right key for decryption. If I make a mistake, please advise me and I will try to avoid such a mistake in the future.

Normally, the key that was used for encryption is stored hashed on the system, so that the application can check if the user used the correct key.

Would it be better to store not the whole key hashed, but split the key into several parts and hash each of these parts? This should make cracking more difficult, because the attacker has to crack several hashes, with different salts (if used). Am I totally wrong with my line of thought?

If yes a little hint would be nice, so that I can investigate in that direction and avoid this mistake in future.

Lets take your idea to the extreme to see its weakness. For simplicity I'll scale things down. Let's assume an 8 bit key chosen randomly. Call this key $k$. If I break into your database and get $d=H(k,s)$ along with $s$ (where $H$ is a hash function and $s$ is the salt), it would take on average $2^{8-1}=2^7=128$ computations (or calls to $H$) to find $k$.

Now, using your idea, lets say the server instead splits $k$ into $(b_1,b_2,\cdots,b_8)$ (i.e., bits) and then computes $d_i=H(k_i,s_i)$ (so there is a different salt for each bit of the key). Now, the attacker who breaks into your database and steals the pairs $(d_i, s_i)$ needs to crack all $8$ hashes. More difficult? No.

The reason is, how much work does it take to break $d_1$? Well, the attacker only need compute $H(1,s_1)$ and $H(0,s_1)$ to find $b_1$. That is only two operations (one on average though since half of the time the attacker will get the right value on the first try). Do this for all $8$ bits and the attacker has to make a maximum of $16$ hash function calls to break the key $k$. The average number of hash function calls would be $12$. This is much, much less than in the normal case above.

Asymptotically speaking, the first system (which hashes the entire password) is something like $O(2^n)$ where $n$ is the number of bits in the key and the second system (your proposal) is $O(n)$.


Practical implementations of Multiparty computations Are there any practical implementations and or software platforms to prototype applications based on MPC ?

There is the Might Be Evil framework and FairplayMP. The hcrypt project also has a secure function evaluation library.

UPDATE:

Also, VIFF and SCAPI (though as of writing this, the SCAPI framework is not fully released).

March 2016:

I just came across FRESCO.


ABE (attribute based encryption) vs ABS (attribute based signature) I want to know if there is any shortcoming that ABE cannot achieve and that the ABS complete it. I mean why the ABS is included if the authentication and the authorization are already ensured by the ABE. I really need to know the real utility of the ABS and what it brings in more compared to the ABE.

Attribute-Based Encryption (ABE) schemes are a way to securely send (i.e share) a plaintext (message) amongst some particular receivers. The data owner (sender) consider an access policy to encrypt the message under this policy that a data user (receiver) is able to decrypt the ciphertext if and only if he/she satisfies the policy. So the ABE schemes just provide the confidentiality for a sensitive data because all certified users are able to calculate the ciphertext corresponding a particular policy (the data owner secret key is not an input for encryption algorithm).

In this point, the Attribute Based signature (ABS) schemes should be considered to achieve authenticity. In these schemes, the data owner who has a bunch of secret keys corresponding to his/her attributes wants to convince the other users about this claim (I am a person with some specific features, for instance, I am "Tall", "Male" and so on). The receiver authenticates this claim if and only if the signature which is produced by the sender based on her/his secret keys satisfy the published access policy with the plain message. In the other word, if the verification algorithm runs correctly then the conditions will be passed.

Overall, in the former schemes, the secret key condition is on the receiver side while the latter focus on the sender side to ensure the secret key corresponding the claimed attributes.

Also, the Attribute-Based Singcryption (ABSC) schemes follow the same target and satisfy not only the authentication but also the confidentiality properties. Precisely, ABSC schemes are the merge of ABE and ABS while are more efficient than executing both ABE and ABS, separately. [https://eprint.iacr.org/2018/263.pdf]


If we know the pre-shared key of an IPSec tunnel, can PFS help us to stay encrypted? Or if the "attacker" has the pre-shared key, then PFS won't help?

Ex.: Heard something about China that it blocks IPSec and only allows it when you give them your pre-shared key, thus they can see the traffic, even if there is PFS implemented on the ex.: IPSec?

No, knowledge of the IKE preshared key will not allow anyone to listen into the IPsec traffic (either with PFS or without).

IKE always performs a Diffie-Hellman exchange to generate the initial keying material; knowledge of the preshared keys does not tell the attacker either the Diffie-Hellman private values, or the shared secret.  The encryption keys are derived from the shared secret; hence they are secure as long as the DH exchange is.

The preshared key is present to act as a 'proof-of-identity'; what knowledge of the preshared key would do is allow you to act as an active man-in-the-middle (because to either side, the attacker is indistinguishable from the other side).  The attacker would perform an IKE negotiation with both sides, generate traffic keys, and then be able to decrypt traffic from one side, read it, and then reencrypt it to send to the other side.


Is symmetric key encrypted with server's public key secure I'm trying to implement lightweight yet secure protocol for communicating two trusted parties with each other.
Consider following scheme:

Alice wants to establish secure two-sided channel with Bob.
Alice knows Bob's public key from reliable source, so she generates random symmetric key, encrypts it with Bob's public key and sends result to Bob through untrusted channel.
Bob receives message, decrypts it with his private key and uses symmetric key found inside to write back to Alice, so they both share the same symmetric key. Alice and Bob then use any authentication scheme to verify identities of each other.
In case Mallory intercepts Alice's message, she won't be able to obtain Alice's symmetric key, but may forge her own, as Bob's public key is known. However Mallory will be unable to authenticate her, so she'll fail.

Are there any security drawbacks in this approach? Initially I've thought about Alice generating pair of asymmetric keys and using symmetric session keys for each message (GPG-style), but former seems more resource efficient to me.

The first part of the protocol – e.g. alice choosing a random secret key and sending it public-key-encrypted to Bob – is in essence the same as the usual RSA key exchange used in SSL/TLS.

As you mentioned, Mallory can't read the key, but can start her own connection to Bob pretending to be Alice, so this part only provides authentication of Bob for Alice, not the other way around. (This is okay for the common use case of HTTPS, where we have one trusted server and lots of untrusted clients).
But (assuming your symmetric encryption also includes some kind of MAC and you have some protocol measures against replay attacks, like message numbers) Bob knows that he speaks with the same entity during the whole conversation.

Mallory might be able to send messages in Alice's name (and receive the responses to these messages), but can't read messages sent by Alice or read the responses to these messages (if they arrive at Bob).

To add authentication for Alice, you add a second authentication step over the now encrypted channel. This can be whatever wanted, from a plain password to another public key signature from Alice. Both schemes are commonly used in SSH, by the way.

This looks secure, but there might be some details hidden in the details of your protocol.

As mentioned by Ricky Demer, when Bob's private key is revealed/broken for some reason, all the previous connections (which an Mallory might have recorded) can now be read by Mallory. (This is called the non-forward-secrecy.)

Using Diffie-Hellman (together with some kind of authentication, like signatures from both parties) or SRP solves this by making the session key unrecoverable from just the transcript and the long-term secrets. This is incorporated in both SSL and SSH protocols, too.

In general I would recommend to use an existing (and evaluated) protocol like SSL or SSH as the base of your communication. (You don't have to implement all options.)


Differential and Linear Cryptanalysis on Random Sbox Assume that we use the key to perform a uniform permutation to generate a sbox. The literature is rich supporting the statement that a random Sbox can make any cryptographic scheme weaker. I have tested and found the randomly permuted sboxes possess weak nonlinearity and high differential probability. We know that to perform differential and linear attack the DDT and LAT should be handy. If we make the sbox key-dependent and every distinct key results a distinct sbox(best case).
Now if someone tries to perform a differential/ linear cryptanalysis then will it be logical to consider the Bruteforce complexity of guessing the proper sbox?
If it is logical then what should be the approach to such an attack?

Typical attacks on Secret SPNs (i.e. with secret uniform S-Boxes) are integrals, see e.g. [1].
Even for AES: the S-Box is too good against differential/linear attacks (strong mixing in MixColumns is also necessary), so best attacks are of another kinds. (Not counting related-key attacks, which allow to deactivate many S-Boxes).
More to the question: in some special cases it may be indeed useful to consider differential cryptanalysis with ``random'' difference. See for example [2], where the output of the Feistel function is very small so that it does not matter which difference to choose - the differential will be sufficiently strong anyway.
[1] Biryukov, A., Khovratovich, D., & Perrin, L. (2017). Multiset-Algebraic Cryptanalysis of Reduced Kuznyechik, Khazad, and secret SPNs. IACR Transactions on Symmetric Cryptology, 2016(2), 226-247. https://doi.org/10.13154/tosc.v2016.i2.226-247
[2] Orr Dunkelman, Abhishek Kumar, Eran Lambooij, Somitra Kumar Sanadhya:
Cryptanalysis of Feistel-Based Format-Preserving Encryption. IACR Cryptol. ePrint Arch. 2020: 1311 https://eprint.iacr.org/2020/1311


Curve25519 Key Exchange Bit Security Please note I am new to Cryptography in general. Sorry if I do not use the correct terminology/my question has some fundamental flaw.

Alice and Bob want to communicate securely over an insecure channel. They decide to use Ed25519 with both an identity key (IdkAlice & IdkBob) and an ephemeral key (EpkAlice & EpkBob) for forward secrecy. Then both compute

SK1 = ECDH( IdkAlice, IdkBob )
SK2 = ECDH( EpkAlice, EpkBob )

SKEY = SHA256( SK1 | SK2 )

and use SKEY as the key in some symmetric cipher.

My question is: How many bits of security is provided in this key exchange?

My assumption is that because Ed25519 provides ~128bits the attacker would need to try $2 \cdot 2^{128}$-times but I'm not sure. (Ignoring active attacks on the key exchange)

Provided that you use the all 256 bits of SKEY as key then the bit security of this scheme is about $\sqrt2\cdot2^{125}$.

The reason behind the $2^{125}$ as opposed to the security of $2^{128}$ is because, for curve25519, $2^{128}$ is just an approximation. If we use, as it is more commonly done, the number of "operation" for this calculation, then the number of point additions required by Pollard's rho is about $\sqrt{2^{251}}\simeq2^{125}$.

The reason behind the $\sqrt2$ factor instead of $2$ is due to the fact that Pollard's rho allows to compute batch discrete logarithms faster than what would be a two separate application of the algorithm.
For details, see the section "Batch discrete logarithms" in the original curve25519 paper.


Is RSA of a random nonce with no padding safe? Consider the following protocol: Bob has a private RSA key $B_{priv}$, and Alice knows the public key $B_{pub}$. Alice wants to send confidential messages to Bob (no integrity intended). To send a message, Alice randomly generates a single-use symmetric key (say, an AES key) $K$, encrypts the message with this symmetric key, and sends this encrypted message alongside with $K$ encrypted with RSA with Bob's public key.

Suppose we use no padding for $\textrm{RSA}_{B_{pub}}(K)$ (in other words, to pad with zero bytes). The obvious (to me) problems with a lack of padding are that an attacker can guess the plaintext (not possible here, it's random) and that encrypting the same plaintext twice gives the same result (again, not happening here). What are the known weaknesses of this scheme (or is it safe)?

If you pad a 128-bit value $K$ with zeroes to the left, and interpret the value numerically with big-endian convention (as happens in PKCS#1 in general), you end up with a value which is no greater than $2^{128}$. If the public exponent is $e = 3$, then the "encrypted value" is no greater than $2^{768}$, and no actual modular reduction takes place. Consequently, a simple cube root extraction on plain integers reveals $K$.

So, that can be quite unsafe.

What is safe is the following:

you generate a random integer $x$, between $0$ and $n-1$ ($n$ is the RSA modulus);
you encrypt $x$ by simply raising it to the power $e$ modulo $n$;
the encryption key you will use with AES is $h(x)$ for some hash function $h$.

It is still relatively limiting, in that this is safe as long as you do one encryption only of $x$. If you want to "send" your symmetric key $K$ to several recipients (a common model, e.g. for email encryption), then the scheme above does not work, and, more generally, you need some per-encryption randomness inserted (as PKCS#1 does for encryption).


Polynomial division hardware implementation I am beginning the implementation of the polynomial binary division algorithm now as I understood i will be checking the MSB bit if 1 to XOR and shift the sum if 0 i will only shift.
What I am not getting well with is the numerator and denominator degree calculation and when to stop the the division
in a case of a polynomial division with M=8 and an irreducible polynomial :
X^8+X^4+X^3+X+1 will be divided by X^6+X^5+X^2+X
at first I will have to pad with zeros to obtain the same size

I have found that shifting the numerator by L and denominator by K until hitting the first '1' will give me the degree being M-L and M-K-1 of each polynomial
and the division will be of Deg(N)-Deg(D) cycles
in this example:
it will be:
Numerator: 100011011
Denominator: 01100110

Numerator MSB is 1 then degree(N) is M-0=8
Denominator MSB is 0 : then it will be shifted to the left by 1 and the Degree(D)=8-1-1=6
the needed counter is 8-6=2 steps and 8-6+1=3 XOR operations

what I would like to ask is this a correct way to start and won't the following degree calculation step includes a large hardware delay since it is done sequentially and M might get to 233

What is the best way of calculating the :
Degree of numerator and denominator
and when can i know where to stop the division

Thank you

The method you describe is called the "pencil and paper algorithm" and is well described in Knuth's Book, Semi-Numerical Algorithm II.

In fact the number of steps can be easily determined by the size of operands. If Dividend D, is m-bit and Divisor d, is n-bit, then the Quotient q, will be (m-n+1)-bit, and the remainder in case of binary division will be at most (n-1)-bit.

Under these conditions, the algorithm il like that follow:

Shift the divisor (m-n)-bit left (this is called Normalization step by Knuth), We use some registers to be initiated by the operand
Reg_D <-- D: init with D, used as an Accumulator,
Reg_d <-- d: init with divisor $2^{m-n}$d; remains unchanged during all the process iteration,
Reg_q <-- 0: init with Operand 0,

for k from (m-n) DownTo 0, Do:
   - Reg_q <-- 2.Reg_q;  //Shift Reg_q 1-bit Left (or equivalently q = 2.q)
   - Reg_D = Reg_D XOR Reg_d;   //... XORing(Reg_D, Reg_d):
   - q_k=MSB(Reg_D); //Get the bit which represent the partial bit of quotient.
   - Reg_q = Reg_q + q_k; //... Inject bit q_k in Reg_q, or
   - if( !k)
           Reg_D = 2.Reg_D;  //... Shift  1-bit Left D excepted for last step!
End For;

NB: Observe:

The Remainder is contained in  Reg_D,
To obtain the quotient, Complement the content of Reg_q.

To optimise the process, in case of multiple division with the same divisor you can try two methods described by Knuth:

Normalization of the Divisor,
Precomputation tables.

Good Luck for your project.


How do I interpret the CADO-NFS output for discrete logarithm calculation in GF(p)? I'm using CADO-NFS to calculate discrete logarithm in a finite field GF(p). The problem is when I type

./cado-nfs.py -dlp -ell 101538509534246169632617439 target=92800609832959449330691138186 191907783019725260605646959711

as described in the README.dlp file I just can't understand which of the three values (log2, log3, log(target)) is my discrete logarithm result:

Anyone with some experience with this tool could help me, please? I didn't find anything on the Internet and the documentation that came with CADO say anything about it.

ell is the largest factor of $p-1$, remember the Sophie Germain prime $p=2q+1$

All below from mail thread of [Cado-nfs-discuss] DLP and well explained with a sageMath code.

  cado-nfs is right, but maybe the printed info is scarce or misleading.

  Here's a verification script.

> sage: p=53236943330228380237618624445646085674945074907141464418703
> sage: ell=46188898894770668459
> sage: target=51415666321640196744601368459935322494639894379132878321944
> sage: logtarget=15315241815410699555
> sage: log2=39557689199984036821
> sage: redlog=ZZ(Integers(ell)(logtarget/log2))
> sage: (GF(p)(2)^redlog/target)^((p-1)//ell) 1
> sage: (GF(p)(2)^logtarget/GF(p)(target)^log2)^((p-1)//ell) 1

  cado-nfs only computes the discrete logarithm of elements of GF(p)^*
  modulo ell. And it won't tell you with respect to which base.

  So you first have to decide on which generator you want (e.g., 2),
  rescale logarithms so that this element has log 1, and then make sure
  that your target has the right log mod ell. Which is equivalent to
  saying that you have an equality in the subgroup of order ell, or in
  other words that when you take the ((p-1)/ell)-th power, you get 1.

  The last test of the script is the generic way to do pairwise
  verification of two (x,log(x)) pairs.


Why does spiped use both nonces and ephemeral keys? Colin Percival's spiped utility uses a pre-shared key and Diffie-Hellman with ephemeral keys to provide forward secrecy.  The protocol is summarized in the project's README under the section "Encrypted Protocol".

What is the purpose of the nonces (nonce_C and nonce_S)?  How are they useful when x_C and x_S are already chosen at random?

Without the nonces, one could violate explicit authentication

by replaying the group_element || MAC_tag messages.


Which element produces randomness in symmetric block ciphers encryption Talking about symmetric encryption, I have 3 elements which I keep trying to puzzle together: IV, encryption mode, and padding.

My question really is which of these elements makes the ciphertext be random?

What I believe right now:

Padding:
The padding does not "add" randomness. It only solves the problem of being able to divide the plaintext into the block size defined.

Encryption mode:
Here I have a little bit of confusion. So, lets compare ECB mode with CBC mode.
As far as I know, the problem with ECB is that, for example, if I have two plain text that I want to encrypt:

P1A, P1B
P2A, P2B

where P1A would be the first block of plain text 1.

If P1B and P2B are the same, then C1B and C2B would also be the same, even if P1A and P2A are different. ¿Am I right?
Therefore is easy to "swap" ciphertext blocks of data.

On the opposite side. CBC mode (without details) chains the ciphertext blocks one with another. Therefore, if we apply CBC mode to the last example. C1B and C2B would not be the same.

But.. And here is one of my questions. The mode "by it self", in this case CBC, does not add randomenes right? Because the  ciphertext will always be the same for the same plain text.
Am I wrong? Is there any mode that obtains randomness by itself?

IV:
And at last, the IV, which I think is actually the only element from these 3 which makes the cipher text be random.

How much wrong am I?

Thank you and sorry if I made some mistake with the technical language of crypto.

“Random” is a complicated concept and this question does not have a one-word answer.

The ciphertext is not random, in the sense that it's possible to relate it to the plaintext. Just decrypt and compare. The ciphertext is constructed deterministically from the plaintext, the key, the IV and the message.

The ciphertext appears random to someone who doesn't know the key and has plausible computational power. (Someone who has effectively infinite computational power can try all possible keys.) This is a definitional property of encryption schemes.

The block cipher algorithm (e.g. AES or DES), the chaining mode (e.g. CBR or CTR), the key and the IV all contribute to this randomness in their own way.

The key, of course, is where the randomness starts. It's directly extracted from an entropy source. It's the one element that absolutely needs to be random in the sense that an adversary has no knowledge of the key beyond its format (for symmetric encryption, an array of bits of known length).
The block cipher, given a key, makes the encryption of a plaintext block look random. That is, to someone who doesn't know the key, the block cipher acts like a random permutation — it always transforms the same input into the same output, but the outputs for distinct inputs are not related in any visible way. The job of the block cipher is to transform the “raw” randomness of the key into a structured randomness: a random-looking permutation function.
The chaining mode extends this randomness to multiple blocks. The encryption of each block may look random, but when you consider multiple blocks together, the combination is not random if there is correlation between the blocks. The job of the chaining mode is to break any correlation. This is where ECB fails: all blocks undergo exactly the same transformation. CBC and other feedback modes break the correlation by inserting a step of the block cipher between each block. CTR breaks the correlation by using different inputs for each block. In all cases the chaining mode leverages the block cipher's decorrelating action from the block level to the message level.
The IV extends this randomness to multiple messages. The encryption of a single message may look random, but the same transformation of the same plaintext would result in the same ciphertext. The job of the IV is to ensure that there is no correlation between any two uses of the same key. The chaining mode uses the IV to leverage the block cipher's decorrelating action from the message level to the multiple-message level.


Can I find a specific SHA512 for an partially-known string? I have a plain text string "I-like-drawwing", and this string has a SHA512 value, assume the SHA512 is "aabbcc".
Then I show SHA512 "aabbcc" to my friend and say:
"this is SHA512 for my string,
and my string ended with 'ing',
I bet $20 that you don’t know my string".

I don't want loose, so I must find another string ended with "ing" and also has the same SHA512 "aabbcc",
Can I find that string?

What you are describing is a second-preimage attack on SHA-512, and you will find it quite infeasible, requiring an expected $2^{512}$ hash computations.

Now, consider your friend's position.

SHA-512 is a one-way function, and knowing part of the plaintext does not help reverse it to recover the whole plaintext from the hash.

Instead, a brute-force approach is necessary. Your friend will calculate hashes of all possible inputs matching the condition you tell  him (ending with "ing"). Once he finds a match, he will conclude that he has found your string.

What does your friend know about your string? Its length? The set of characters you might use? The fact that you posted it on stackexchange? Your best hope is that your friend will not find your string, because if he does, you will be unable to lie and present another string with the same hash.


Multiparty millionaire problem where members only know if they are the richest one I'm looking for a generalisation of Yao's millionaire problem: $N$ parties want to know whether they are the richest one. If they are not, then they just know they are not the richest party - but do not know the identity of the richest one.

Ideally, in case of equality, all richest members would know they are the richest, but would not know if others are as rich.

Does such a protocol already exist?

Edit: obviously when there are only two users, then everyone knows who is the richest. I guess a formalization would be that not-richest people cannot guess who, amongst remaining users, is richest, with probability better than random.

There exist such constructions, for instance assume a FHE scheme which takes the encrypted values as input, and output for each party $p_i$ their result, encrypted with $p_i$'s key. While this should work (it may need some work for the encryption of the inputs but anyway), it is also extremely tedious.

Edit:

As the comment of Mikero correctly points out it is quite easy to make the outputs differ for most MPC protocols (for example in the 2PC case at YAO's protocol, you can tell the evaluator that output key X1 means 0 and output Y1 means 1 while you don't say anything about X2 and Y2 and make the evaluator send X2 and Y2 to the garbler, who knows the meanings of them).

In this case you just need to output 0 or 1 to every party if they are the richest or not.

Old answer:

My best idea to solve the problem is to use YAO's protocol (or any other common MPC protocol), make every party additionally input a random identifier and make the function output the identifier of the richest party. Then the richest party knows being the richest while the other parties don't know who is the richest party.

To avoid the problem that two parties input the same identifier I would think about the following (combining these ideas also makes sense):

Make the identifier large enough so that the likelyhood that two parties input the same identifier is negligible.
Expand the function such that the function outputs a fixed identifier 0 (which must not be chosen by any party) if two parties input the same identifier. If that happened, repeat the MPC computation with another random identifiers.


Security of this deterministic encryption scheme I recently came across a library that promises to do deterministic encryption with the following scheme:

  AES with 256 bit key in CBC mode with PKCS7 padding and Synthetic Initialization vector taken from the first 16 bytes of the HMACSHA256 mac of the plaintext. I use the same key for confidentiality and integrity. Ciphertext is Base64Encode( MSB(128, mac(k, plaintext)) || E(iv, k, plaintext) ) where MSB(b, v) stands for the b most significant bits (left-most) of v.

My question is: does this scheme have any security flaws? How would it compare, for example, with using SIV mode as described in RFC 5297? Specifically, does it provide the same guarantee for message authentication and integrity?

Correctly implemented, it should be secure deterministic authenticated encryption. In fact, it is SIV, in the wider sense of using the "SIV construction" as defined in Deterministic Authenticated-Encryption by Rogaway and Shrimpton (except for lacking a header input). The proof of the security of the SIV construction is that:

  We will now show that if $F$ is PRF-secure and $Π$ is IND\$-secure then $SIV[F, Π]$ is DAE-secure.

So in this case AES-CBC must be IND\$-secure and HMAC-SHA256 must be a secure PRF. With those assumptions, the mode as described is a secure deterministic authenticated encryption scheme.

Those are slightly stronger requirements than we usually use. HMAC-SHA256 is normally only required to be a secure MAC. Being a secure PRF implies it, but the converse is not implied. In practice there are other protocols that do rely on its PRF security and we have no indication that it would be insecure.

Caveat: the keys being the same actually invalidates the proof, so in the strict sense it is not proved secure. However, for key reuse between HMAC-SHA256 and AES to be exploitable would be an incredible coincidence.

Now, in practice there are some problems with the use of CBC mode. While it is provably secure, practical implementations have been known to be weak. Most relevant here is the padding oracle attack. There are ways to avoid it, but without looking at the source of the library I do not know if they are used:

Always verifying both padding and MAC in constant time avoids the side channel leak. The error returned must also be the same. This is difficult to ensure.
If the MAC is verified before the padding, the attack is not possible. I.e. the MAC is either over the ciphertext (not the case here) or over the padded message (possible here).
Ciphertext stealing avoids the need for padding. (Not used here.)

On the other hand, the choice of HMAC and CBC does also have some advantages. Namely, it breaks less badly as you get close to the birthday bound:

CMAC is gets insecure after $2^{64}$ invocations, and is recommended to be only used for $2^{48}$ blocks (see SP 800-38B, appendix B).
With CTR an IV (or block input) collision means subsequent blocks also collide. CBC usually only leaks individual, random blocks, which is potentially harder to exploit.


Can public key help attackers to break RSA encryption faster? I have two, closely related questions:

Can a really good attacker (hacker) use the public key for his advantage and break RSA encryption faster? My point is that in RSA "communication" public key is moving from server to client… If attacker will get this key and also encrypted data will be there any advantages or it is not important if attacker has public key?
If, for example, there are five users and each user has public key but with different size (2048, 2100, 2120,2250,2310bits etc.) If attacker will break one of these key all other keys are also immediatelly know for this attacker or he must start whole process of breaking again? Is there some advantages to have each RSA key with different bit size?

Can really good attacker(hacker) use public key for his advantage and break RSA encryption faster?

No; we always assume that the attacker knows the public key (that's what "public" means, after all).

  Is there some advantage to have each RSA key with different bit size?

No; the most efficient approach known to attack an RSA key is to use the Number Field Sieve algorithm; which that approach, the attacker picks one RSA key, and attacks it.  It doesn't matter if the keys he selects from has different sizes; he's likely to pick the smallest and/or the one that protects data of the most value.


Why doesn't “Classic McEliece” need scrambling? The original McEliece scheme uses two random matrices S and P to scramble the generator matrix and uses $\mathsf S·\mathsf G·\mathsf P$ as the public key. The Niederreiter variant also does about the same thing.

However, in the Classic McEliece proposal (based on Niederreiter in spite of its name), they don't do any of that.
They are giving lots of details as to why the two other modifications by Niederreiter (msg is the error instead of codeword, transmitting the Generator matrix in systematic form) don't reduce security, but they don't detail why the can just remove this scrambling. Why can they? (Can they?)

References:

Original 1978 McEliece Paper
Niederreiter (beware, very big PDF)
Classic McEliece

It seems to me that the answer is highly likely to be as follows. I only had a quick look, so buyer beware:

So, instead of the recovered permuted error vector $\sigma(e)$ ( $e$ is the plaintext, in Niederreiter and Classic McEliece) needing to be scrambled by the opponent to get the unpermuted error vector $e$, the recovery of the correct error vector (for the party holding the private key) is checked by hashing the recovered error vector $e'$ and comparing to the hashed value $h(e)$ included in the plaintext.

The opponent's additional work factor is now the work required to find a hash preimage of the right length (which may or may not be the right $e$).

See the talk here  by Tanja Lange on the project website.


Bitwise method of generating r for RSA-KEM It seems that RSA-KEM has a very troublesome method of generating the secret $r$. It seems that the random value needs to be in the range $0 \le r \le {n - 1}$.

Now most cryptographic environments don't have a random number generator that generates those kind of numbers; usually they are just provided with a seeded DRBG that outputs full bytes. Performing all kinds of integer operations on the bytes may lead to leaks of the master key within these kind of environments. Especially the $\bmod$ operation seems to be tricky in this regards.

Is there a known good way of generating $r$ that disposes of the $\bmod$ operation and possible looping?

For instance I could think of constructing $r$ as

00 | R

The | operation is of course concatenation.

In this construction $R$ is then an octet string consisting of (pseudo) random bytes. $r$ consists of the value of 00 | R when used as a big endian unsigned integer. It can be used directly as input to raw "RSA encryption" as implemented by most libraries.

That would provide $\operatorname{len}(R) * 8$ bits of entropy for the KDF. I think that would be $\lfloor (log_2(n) - 1) / 8\rfloor \cdot 8$ bits of entropy when measured against the modulus value $n$.

The scheme would otherwise be unaltered of course; there would be no explicit checks on the value of $r$ during decryption.

Would this suffice as a secure scheme of constructing $r$ instead of performing integer calculations and checks to get to $0 \le r \le {n - 1}$?

Here are a few options.  I include modular reduction and rejection sampling because I suspect they are less costly than you worry.

What you suggested, roughly: Pick $r$ uniformly in $\{0, 1, 2, \dots, 2^{\lfloor\log_2 n\rfloor} - 1\}$.

If there were an IND-CCA2 or NM-CCA2 adversary with success probability $p$ against RSA-KEM with $r$ uniform in $\{0, 1, 2, \dots, n - 1\}$, the success probability of the same adversary can't be more than $2p$ since we're removing less than half the possible space of $r$.  If $2p$ was too high, then $p$ was almost certainly too high already.  If you set the high byte to zero, as you suggested, then you remove more of the output space and it's $256p$ instead of just $2p$.

Theoretical concern: The standard security reduction to the RSA problem[1], which demonstrates how to turn an IND-CCA2 attacker into a procedure to compute $e^{\mathit{th}}$ roots modulo $n$, would no longer apply, because a little under half the space is guaranteed not to be covered.  It's a little hard to imagine that the general RSA problem is hard, but becomes easy if you restrict it to this domain; however, the more space you eliminate, the more irrelevant the reduction becomes to justifying the security, so better to set the high bit to zero than to set the high byte to zero as you suggested.
Modular reduction: Pick $r$ uniformly in $\{0, 1, 2, \dots, 2^{\lfloor\log_2 n\rfloor + k} - 1\}$ where $k$ is, say, 64, or 256 if you're paranoid or $\lfloor\log_2 n\rfloor$ if you're really paranoid, and reduce modulo $n$.

You don't need a general purpose division routine: You can easily reduce $r$ modulo $n$ in constant time with Barrett reduction using only two multiplications and a subtraction, if you precompute $2^{\lceil\log_2 n\rceil}/n$ (with bit-by-bit long division in constant time if $n$ is ever secret), as long as $r < n^2$.

This doesn't give a uniform distribution, but it's awfully close—much closer than option (1), if for no other reason than that it doesn't completely exclude any of $\mathbb Z/n\mathbb Z$ like (1) does.  (Exercise for the reader: Quantify the modulo bias in, say, total variation distance—this puts a similar bound on the advantage of an IND-CCA2 or NM-CCA2 adversary vs. a true uniform distribution.)
Rejection sampling: Pick $r$ uniformly in $\{0, 1, 2, \dots, 2^{\lceil\log_2 n\rceil} - 1\}$, and start over if $r \geq n$.

Since $2^{\lceil\log_2 n\rceil}/2 < n < 2^{\lceil\log_2 n\rceil}$, the number of trials is geometrically distributed with probability $p < 1/2$; the expected number of trials is just over 1 and well below 2.  You will obviously never see more than 128 trials—for a 4096-bit RSA modulus, you need to generate much less than 4096 KB of data.

This guarantees a uniform distribution for $r$ in $\{0, 1, 2, \dots, n - 1\}$.


What is the main limitation of DES? I know this question seems too general, not specific. Our professor asked this question today, and I have no idea how to answer it.

Maybe it's the key size, maybe another thing? Any idea?

According to Introduction to Modern Cryptography by Katz and Lindell, in the section titled Security of DES on page 218 in the second edition.

  After almost 30 years of intensive study, the best known practical attack on DES is still an exhaustive search through its key space... Unfortunately, the 56-bit key length of DES is short enough that an exhaustive search through all $2^{56}$ possible keys is now feasible.

They go on to say (a few paragraphs down):

  The insecurity of DES has nothing to do with its design per se, but rather is due to its short key length... Since DES itself seems not to have significant structural weaknesses, it makes sense to use DES as a building block for constructing block ciphers with longer keys.

So I would say that yes, the main limitation of DES is the key size.

That book goes on to state the secondary cause for concern as the short block length of 64-bits.


What is the Knowledge Of Secret Key Assumption (KOSK) From what I've read it seems to be where an entity must prove that they own the secret key. Which is done by signing a message M using said secret key.

Is this different than doing a Proof of knowledge for a secret key?
Is this different than doing a zero knowledge proof for a secret key?

According to the paper you link to in the comments:

  The security model makes the knowledge of
  secret key (KOSK) assumption. There is no dedicated key
  generation, but, when the adversary, mounting a rogue-key
  attack, provides a public key of its choice for a group member, it is required, in the model, to provide also a matching
  secret key. Of course “real” adversaries would not do any
  such thing, so what does this mean? It is explained by the
  authors as modeling the assumption that a user provides
  the certification authority (CA) with a proof of knowledge
  of its secret key before the CA certifies the corresponding
  public key.

What the above says is that the KOSK is not really an assumption in the cryptographic sense (like RSA, or discrete logarithm), but more like an hypothesis that is made about a specific security model. That is, KOSK is simply the hypothesis that when the adversary will mount an attack on the system, which is done by submitting some public key, he will also provide the matching secret key.

Now, let's explains why it matters here. Intuitively, there are situations in cryptography, such as this one, where we can prove that an attacker cannot break the security property of our scheme if he knows some specific piece of information, such as the secret key associated to the public key he submits. This might look strange at first, but it makes sense if you look at it the other way around: if the adversary is only allowed to submit public keys for which he knows the corresponding secret key, he is severely restricted in the type of attacks he can mount (e.g. he cannot provide a public key that he has stolen to some honest party, in an attempt to impersonate him).

Of course, there is a problem: in real life, no user will not provide the secret key together with the public key, that would completely break the system for them. The trick instead is to ask them to perform a zero-knowledge proof of knowledge (ZKPoK) of the secret key, which demonstrates that they know the secret key associated to the submitted public key, without leaking any further information.

Then, Bellare and Neuven go on with identifying the following problem: in real implementations of the protocol, this proof of knowledge is replaced by a signature, using the secret key as the signing key. Of course, intuitively being able to sign a document with the secret key shows that you know it. But it does not prove it, and that's all the issue. What does it mean to prove that an algorithm $A$ knows something? In cryptography, it means something very precise: it means that, given the code of $A$, it is possible to extract this value in polynomial time. This is possible by definition with a ZKPoK, but not with a signature. In the security analysis of the scheme, this extraction procedure is in general crucial: to show that the system is secure under some assumption, the security reduction will make use of the existence of an extractor that recovers this secret key, and use the extracted secret key in order to derive a contradiction to some security assumption from a successful adversary. If no such efficient extraction procedure exists, the security analysis breaks down.

Is this only a theoretical issue? This was probably the hope of the people who implemented the design. Arguably, it should be hard to mount an attack on a real-world system that uses signatures instead of ZKPoK, because a successful attack would require, at least, that the adversary somehow manages to find signatures on some documents without knowing the secret key. But can't he? Maybe the adversary can trick the real owner of the secret key into signing the document for him, mounting a man-in-the-middle attack. Or perhaps there is some more complex attack: I could easily design myself a (contrived) system which is provably secure using a ZKPoK, but which becomes completely insecure as soon as one replaces the ZKPoK bs a signature. The point is that without a security reduction, there is no way to be 100% sure that no such complete break exists.


On the Acceptability of a Naive Pseudo Random Number Generator My question is probably both philosophical and technical.
Background
I was developing a CSPRNG, and I needed to shuffle the bits in one step in the middle of the algorithm - any naive shuffle would suffice.
I had this question in my mind:
Why would be any difference if one chooses to confine to a "shuffle" algorithm (see next) instead of my whole complicated algorithm? Which terrified me, to be honest.

The Naive Method
I created a pool of $10^6$ bits where the 1's count exactly 50% and distributed consecutively.
$1111......0000$
Then used the very simple Fisher–Yates shuffle Algorithm to shuffle the bits.

Results
Trying different seeds and sequence lengths, the above-mentioned naive method passed ALL NIST and DieHarder Tests, in addition to the Next Bit Test. It was even superior to the results of urandom and Mersenne Twister (I know that the latter is not CSPRNG but it's widely used as PRNG).

The Question
I believe that if anyone proposes the above naive shuffle algorithm even if supported by its excellent results in the literature, it will be immediately rejected (though I'm open to correction here).
Then the question that is confusing me is : Why? I mean "Why" on both ways:
Why such naive and simple thing is not appealing and Why would such naive and simple method pass all tests and even surpass urandom and MT algorithm on the basis of the aforementioned tests (which are extremely used as an evidence of the proposed algorithms in the literature).
What is the "real" compass?

Why such naive and simple thing is not appealing

If you're talking about a method that internally generates 500,000 0 bits and 500,000 1 bits, shuffles them (by some method), and then outputs them, that would not be considered a CSRNG.

What is the "real" compass?

The compass is "can we devise an efficient test that distinguishes the output of the proposed CSRNG from the output of a truly random number generator (e.g. generated by someone flipping a fair coin)".  This test would take a sequence (generated by either the CSRNG or the random source) and generate a 0 or 1 answer; it is considered a distinguisher if it generates a 1 answer with a nontrivially different probability when given a sample from the CSRNG versus a sample from the random source.
In the shuffle-rng case, yes; one can ask for the output of 1,000,000 bits and count the '1' bits.  For the shuffle rng, you're get exactly 500,000 '1' bits; for the truly random source, you're get exactly 500,000 '1' bits rather rarely (with probability $c 10^{-3}$ for some $c$ not too far from 1 that I'm too lazy to look up).  That gives us a distinguisher, and hence the shuffle RNG is not a CSRNG.
In addition, you state:

the aforementioned tests [NIST, Dieharder, Next Bit Test] (which are extremely used as an evidence of the proposed algorithms in the literature).

Actually, when it comes to CSRNGs, those tests will rarely be used as evidence (and, quite frankly, when we come across a proposal which states them as evidence, that'll be taken as evidence that the authors are clueless when it comes to cryptography).  It's quite easy to make a generator that passes all those tests, but for which it is easy to make a distinguisher (and hence is not a CSRNG).
Those tests might be sufficient if you want to make sure that the RNG you're considering has good statistical properties, and so might be reasonable for noncryptographical work; however in crypto, we have considerably stricter requirements.


Can multiple Pearson permutation tables be reduced or merged? There was a recent question answered where the accepted solution was a double Pearson hash. It consisted of the following pseudo code:- h = T1[h ^ x[i]] followed immediately by h = T2[h ^ x[i]] so effectively you run one lookup table into the other. Tables T1 and T2 are unique random 8 bit permutations. Output collisions can   occur at the classic $ 1 \over e $ rate given the presence of the 2nd table, with the hash behaving as a pseudo random function.

Developing this construction further, assume that the permutation tables are $ \pi $, giving a more general form for hashing a message $m$ with multiple consecutive but unique permutations:-

$$   h_{i} =  \pi_j [h_{i-1} \oplus m[i]]; recursive   $$

creating a functional composite as in:-

$$      h = \pi_3[(\pi_2[(\pi_1 [h \oplus m[i]]) \oplus m[i])]) \oplus m[i]]     $$

if $j=3$ . And let's call each calculation of $h$ for any given $\pi$ a 'step'.  Overall, we get $ output = H_N(m) $ for this cool/weird hash consisting of $N$ tables/steps. As an example, it might be that $ H_3(3512)=110 $  for a hash with 3 permutation tables. In the linked question we used 2 tables.

Can a new $\pi$ or set of $\pi$s be constructed to arrive at an identical output for all messages with $<N$ steps? In other words can multiple $\pi$ permutations be reduced or merged somehow into new ones, even theoretically?  Clearly they can in the special and trivial case of $|m| = 1$. What about generally for $|m| > 1$?
Considering the trivial case mentioned above, is there some relationship between $N$ and $|m|$ that determines the answer?
If  a reduced set of new $\pi$s might theoretically exist, how might   it found in practice?

Notes:

Some of this question is clearly on topic here, but not sure about it's entirely.
I see small parallels with permutations and non linearity, construction of S boxes, and their combinations.
Whilst hallucinating one might assume values of $\pi_j$  be likened to multiple keys $k_j$, so the answer to Security of a block cipher if double encryption $E_{K_2} \circ E_{K_1}$ is always single encryption $E_{f(K_1,K_2)}$ comes to mind as there is an attempt at a similar(?) reduction.
I'm happy to be migrated outa here.

Claim: A $\pi$ permutation table can be found such that applying it to a message $m$ will yield the same output as applying multiple, different permutations to that message $m$.

i.e. For any number of permutation steps $\phi_n$, $m_{initial}\rightarrow\phi_1\rightarrow\phi_2\rightarrow...\rightarrow\phi_n\rightarrow m_{permuted}$

$\exists$ a single permutation $\pi$ such that: $m_{initial}\rightarrow\pi\rightarrow m_{permuted}$

Where both $m_{permuted}$'s are identical.

Proof:

Assume we have two permutation tables, $\phi_1$ and $\phi_2$ s.t.

$\phi_1=
\begin{bmatrix}
    m_{1} & m_{2} & m_{3} & m_{4} \\
    a & b & c & d
\end{bmatrix} $
$\phi_2=
\begin{bmatrix}
    m_{1\phi_1} & m_{2\phi_1} & m_{3\phi_1} & m_{4\phi_1} \\
    e & f & g & h
\end{bmatrix} $

Where the first row contains the input broken into bits and the second row contains the positions that each bit will be mapped to. (For $\phi_2$ notice that each bit of $m$ is now $m_{0\phi_1}$, indicating that it is the first bit of the message after being permuted by $\phi_1$). For example:

$
m=3512
$

\begin{bmatrix}
    3 & 5 & 1 & 2 \\
    4 & 2 & 3 & 1
\end{bmatrix}

yields a $m_{permuted}=2513$, and then this new permuted message can be permuted again (as many times as desired).

Right, so back to our earlier example using $m$, $\phi$, and $a,b,c,...$.

Going through the first permutation, we will have the message $m_{\phi_1}=m_{a}m_{b}m_{c}m_{d}$

Going through the second permutation, we will have the message
$m_{\phi_2}=m_em_fm_gm_h$

So, it is sufficient to find a permutation matrix that directly maps $m_1,m_2$ etc. to the locations that $m_1,m_2,...$ end up in the final permutation matrix. Finding such a permutation matrix is quite simple, as you can pass a message $m$ through the multiple permutations $\phi_n$, observe where they end up, and create the mapping based on that. This is best illustrated by and example, but proof by example is not acceptable, so I added the other info in before this. Also note that this works for any size of $m$ assuming the permutation has mappings that include all bits in $m$ (So each bit gets assigned a new place).

Example:

$m=m_1m_2m_3m_4$

$\rightarrow$$\phi_1=
\begin{bmatrix}
    m_{1} & m_{2} & m_{3} & m_{4} \\
    3 & 2 & 4 & 1
\end{bmatrix} $$\rightarrow m_{\phi_1}=m_3m_2m_4m_1$

$\rightarrow$$\phi_2=
\begin{bmatrix}
    m_{3} & m_{2} & m_{4} & m_{1} \\
    4 & 2 & 3 & 1
\end{bmatrix} $$\rightarrow m_{\phi_2}=m_1m_2m_4m_3$

$\therefore$ It is sufficient to have a permutation table to complete the mapping $m_1m_2m_3m_4 \rightarrow m_1m_2m_4m_3$

This matrix is
$\pi=
\begin{bmatrix}
    m_{1} & m_{2} & m_{3} & m_{4} \\
    1 & 2 & 4 & 3
\end{bmatrix} $$\rightarrow \pi(m)=m_1m_2m_4m_3$

And $\phi_2(\phi_1(m))=\pi(m)$


Can I use PKCS#5 with CBC? As far as I know there are two padding mechanisms, which are PKCS 5 and 7. Which one should be used for CBC?

They are, effectively, the same thing.

PKCS#5 describes a padding that wrote down 8-n padding bytes, but was only valid for DES and RC2.

PKCS#7 described a padding scheme which wrote down k-n bytes for a k-byte block cipher.

Most libraries call the scheme PKCS#7 padding, since that’s the more generalized one (and is defined for AES), but some decided that “7 fixed 5, so credit really goes to 5”.


Can cycle finding techniques reduce the memory usage of the MitM attack against 2DES and 3DES? A 2DES like cipher $c=E^{(2)}_{K_2}(E^{(1)}_{K_1}(p))$ where both halves have an $n$ bit key is vulnerable to a meet-in-the-middle attack.

Meet-in-the-middle using a big table

Create a table containing $E^{(1)}_{K_1}(p)$ for all possible $K_1$ and computing $D^{(2)}_{K_2}(c)$ for all values of $K_2$, looking for a matching result.

This approach requires a big table with about $2^n$ entries.

Meet-in-the-middle using cycle finding

An alternative approach would be to define a hash function that maps an $n+1$ bit value to another $n+1$ value:

Use $1$ bit of the input to decide between $E^{(1)}_{K}(p)$ and $D^{(2)}_{K}(c)$ and the remaining $n$ bits as key for this function.

A collision of this hash function can either have the same discriminator bit, in which case it's useless for our purposes, or different discriminator bits, in which case it's a successful meeting.

Now search for collisions of this hash function, applying the usual memory reduction techniques like cycle-finding and/or distinguished points. This should require only around $2^{n/2}$ table entries instead of $2^{n}$ table entries, while increasing computation cost only my a small constant factor.

Does this approach work?

Let $b$ be the width of $E^{(1)}_{K_1}(p)$ and $D^{(2)}_{K_2}(p)$. For the block cipher DES that would be $b=64$, with $n=56$. I'll assume $n+4<b<2n-4$, which holds in this case and simplifies some approximations.

Let $w$ be the width of the function iterated. The question as worded proposes $w=n+1=57$, and thus finds collisions fast, but with $w<b$ only a fraction (like $2^{w-b}=2^{-7}$ with $w<b-4$) are such that they reveal $K_1$ and $K_2$ such that $c=E^{(2)}_{K_2}(E^{(1)}_{K_1}(p))$.

Let's first increase $w$ from $n+1=57$ to $w=b=64$. The collision condition is now precisely such that, when the discriminator bits are different, $c=E^{(2)}_{K_2}(E^{(1)}_{K_1}(p))$ where $K_1$ and $K_2$ are derived from the colliding inputs, and the common output is $E^{(1)}_{K_1}(p)=D^{(2)}_{K_2}(c)$. We expect a find of $(K_1,K_2)$ to have odds about $2^{b-2n}=2^{-48}$ to be the correct one, and that's determined with negligible extra cost, just as in the normal MitM.

I see no reason why the proposed method would not find collision with a usable discriminator bit as expected for a random function, at an expected cost of about $2^{w/2+1}$ evaluations of the function (only a little more with cycle-finding using distinguished points, given the modest $w$; I neglect that). So the expected cost in DES operations is like $2^{2n-w/2+1}=2^{81}$.

Using little RAM by the above technique thus comes at the price of making about $2^{n-w/2+0.4}=2^{24.4}$ times more evaluations of $E^{(1)}$ or $D^{(2)}$ than in basic MitM, which is expected to perform about $2^{n+0.6}$ evaluations (I'm discounting cycle-finding overhead).

Even though, this is an improvement over the obvious time-memory tradeoff for MitM on a memory-bound system, where we split the problem into (at most) $2^r$ runs with $r$ fixed bits in $K_1$, each using all available RAM for $2^{n-r}$ entries, for an expected cost dominated (for $r>4$) by $2^{n+r-1}$ evaluations of $D^{(2)}$ and searches of that in the table. With $r=n-w/2+2=26$, the two techniques make the same $2^{2n-w/2+1}=2^{81}$ number of DES operations, but the MitM makes as many accesses in $2^{n-r}=2^{30}$ values, while cycle-finding using distinguished points makes much less memory accesses (which are more costly than a DES is an ASIC), and requires significantly less memory.

The above calculation suggests to increase the width $w$ of the function we search collisions for, above $w=b$ considered above, up to something closer to $2n$ (this is possible if we have several plaintext-ciphertext pairs, but beware that when $w$ is not a multiple of the native block size we are not sure that the candidate $(K_1,K_2)$ found by collision really works for the full block forming $p$ and $c$ that we used, and when $w$ goes from $b$ to $b+1$ we abruptly need two block cipher operations per evaluation of the iterated function, rather than one; independently, the above cost calculations become invalid for $w$ approaching $2n$).

With that change, the proposed method seems closer to what's studied in section 5.3 on MitM in Paul C. van Oorschot and Michael J. Wiener: Parallel Collision Search with Cryptanalytic Applications (in Journal of Cryptology, January 1999, Volume 12, Issue 1), which seems to use $w=1.5b$ when applied to 2DES (section 6.3); that refines their earlier Improving Implementable Meet-in-the-Middle Attacks by Orders of Magnitude (in proceedings of Crypto 1996).

So yes, cycle-finding techniques can reduce the memory usage (size, and number of accesses) of the MitM attack against 2DES. And it does so with a lesser increase of the number of cipher operations (which has an influence on time) than plain partitioning of the problem, which keeps the product $\;$memory size × cipher operations$\;$ about constant.

It remains that the expected number of cipher operations rises significantly above $2^{n+1}$ in the best (thus complex) improvements in the literature; it seems they are far from achieving what's quantitatively envisioned in this comment (much more RAM and/or DES operations is needed). The advantages (pointed by that comment) of cycle-finding with distinguished points hold:

Thanks to distinguished points, most DES computations need no memory accesses; this is the biggest cost saver when DES is implemented in ASIC.
Because collision detection is made only on distinguished points, the RAM requirement is much lower;
There is little communication required compared to basic MitM distributed on multiple nodes with memory (but more than for the obvious time-memory tradeoff of MitM, where the $2^r$ jobs are entirely independent, at the cost of computing all $D^{(2)}_{K_2}(c)$ in each job).

I wish I had a graph visualizing, on a $\log_2$ scale, the time complexity (in DES operations, and separately memory searches) and memory size achieved by the most obvious time-memory trade-off for MitM, and cycle-finding with a few parameterizations.


Hashing a password with SHA256 on the client then bcrypt on the server I'm trying to implement a cryptographically secured storage site (not Mega, or anything similar) and am trying to prevent the user's password from ever touching the server. The password is used to both log in and generate a PBKDF2 key for AES in Javascript, so the plaintext password should never leave the client machine.

What I'm thinking of doing is getting the client to generate a SHA256 hash of the password and send it to the server, which will then use bcrypt on that hash to create final hash to be stored on the server. My concern is that after hashing the user's password client-side and server-side with two different algorithms, I might either a) be losing entropy in the password or b) opening myself up to attacks due to the mixed hashing methods. Are my concerns based in reality?

Thanks

[edit] all communication will be secured over 2048bit SSL so MITM or sniffing are not a primary concern.

A problem with your proposed solution is that the digest of the password is now "password equivalent". So, what does hashing it before sending it gain you?

That said, I don't think either of your concerns are concerning (or should be concerning). For the first, see this. If anything, most passwords will have less than 256 bits of entropy anyways. For mixing hashes, see this and this.

A better solution would be to use SRP for which a javascript version already exists.

That said, you are aware of the problems with doing crypto in javascript, right?


Contruct a protocol to determine if three secret keys are different, without revealing any of them? I am trying to find a protocol for this problem:

Three persons, $A$, $B$, and $C$, know secret numbers $s_{A}, s_{B}$, and $s_{C}$, respectively. They want to know whether their numbers are all different, but none of them wants to reveal his number to any of the others.

If there are equal numbers between the three, this fact should be known, but no one shall discover which numbers are equal.

There is no trusted center (i.e. they can't use a fourth party doing calculations or similar), they only can communicate with each other.

You should easily be able to do this using a generic multi-party computation framework. For more info on what frameworks are available see Practical implementations of Multiparty computations.

From what I have seen, VIFF is pretty easy to get up and running to experiment with.


Cryptocurrency for quantum computers that is physically impossible to double-spend? Could a cryptocurrency running (at least partially) on a quantum computer (and/or on a quantum network) be developed in which it is physically impossible to double-spend? In other words, a coin in which it would be physically impossible to create two transactions that transfer the same coin from one address to two different addresses? Is there any published work on the subject, peer-reviewed or not? For example, if a coin is represented by an uncollapsed quantum state then according to No-cloning theorem it would be physically impossible (or only unlikely?) to transfer said coin to two different recipients, correct?

Edit: accepted the only answer. I don't think it applies here but at least this question shouldn't get deleted automatically...

I'm not sure how developed the idea is, but it sounds like you are describing the idea of quantum money.

Also, as it would be a new cryptocurrency, it would not be Bitcoin; Bitcoin is a particular cryptocurrency, and not all cryptocurrencies are Bitcoin in the same way that not all normal currency is US dollars.


How does PKCS 1.5 solve the insecureness of Textbook RSA? As we know, Textbook RSA is not enough safe to use because of the following issues;

Guessable plaintext problem
Small $e$ issue

I want to know how PKCS 1.5 solved these problems.

PKCS#1 v1.5 describes a method (formally known as RSAES-PKCS1-v1_5) that turns textbook RSA into a (heuristically) secure encryption scheme for small messages (PKCS#1 v1.5 also describes a signature scheme, which the question and this answer do not consider).

For a $k$-byte ($8k-7$ to $8k$-bit) public modulus part of public key $(N,e)$, the message to be encrypted $M$ is a $\mathrm{mLen}$-byte bytestring with $\mathrm{mLen}\le k-11$. Message $M$ is turned into
$\mathrm{EM}=\mathtt{0x00}\mathbin\|\mathtt{0x02}\mathbin\|\mathrm{PS}\mathbin\|\mathtt{0x00}\mathbin\|M$, where $\mathrm{PS}$ is drawn as a $k-\mathrm{mLen}-3$-byte bytestring consisting of fresh near-uniformly-random non-zero bytes. Then (with big-endian conversion between bytestring and  integer left implicit) the ciphertext is $C\gets\mathrm{EM}^e\bmod N$. That's textbook RSA encryption of $\mathrm{EM}$.

While plaintext $M$ might still be easily guessable, verifying such guess becomes much harder. A brute-force method becomes: try all the possible $\mathrm{PS}$ and compute the corresponding $C$, until one matches. That strategy requires $255^{k-\mathrm{mLen}-3}/2$ try on average (for each possible $M$). That's next to $2^{63}$ at least, and growing by a factor of $255$ for each byte of message capacity that we remove. That's believed to solve the guessable plaintext problem; but we have no formal proof that it does.

Thanks to $\mathtt{0x02}$ at the second byte of $\mathrm{EM}$, it holds that $\mathrm{EM}>2^{8k-15}$. It follows that for $e\ge3$, $\mathrm{EM}^e\gg N^2$ for all practical $k$, and that's more than enough to solve a number of small $e$ issues :

any known extension of the $e^\text{th}$ root attack (in this attack against textbook RSA, where $C\gets M^e\bmod N$, it is used that for $M<N^{1/e}$, we can compute back $M$ from $C$ as $M\gets\sqrt[e]C$ )
Coppersmith's Short Pad Attack (which extends the Franklin-Reiter related messages attack to random padding).

RSAES-PKCS1-v1_5 also practically thwarts Hastad's broadcast attack. In this attack against textbook RSA, sending the same message to at least $e$ recipients allows decryption. The random $\mathrm{PS}$ makes $\mathrm{EM}$ for the same $M$ potentially different. Even for $e=3$, $\mathrm{PS}$ at the 8-byte minimum, and $2^{36}$ recipients of the same message $M$, probability that $e$ padded messages $\mathrm{EM}$ are identical is lower than one in a million, if I got the math right.

However, many RSAES-PKCS1-v1_5 implementations are vulnerable when used with small $e$, such as $e=3$. That's because implementations often check that the first two bytes of $C^d\bmod N$ are $\mathtt{0x00}\mathbin\|\mathtt{0x02}$, and/or parse what follows in order to find the first $\mathtt{0x00}$, indicating the start of $M$ and allowing recovery of $\mathrm{mLen}$. When the result of such check is made available in a way leaking where the failure occurred (by a detailed error code, or timing, or some other side channel) to adversaries able to submit cryptograms for decryption, then Bleichenbacher's padding oracle attack applies. It turns a moderate number of queries to a decrypting entity into an RSA private-key operation for arbitrary argument, allowing decryption of one message, or computing one signature if the same key is used for encryption and signature.

That's not a fatality, though: RSAES-PKCS1-v1_5 padding can be checked in constant time, with a single error code regardless of the particular failure. Another possible strategy is to not check the left 10 bytes; or when $\mathrm{mLen}$ is known in advance, make no padding check and simply extract $M$ as the rightmost $\mathrm{mLen}$ bytes of $C^d\bmod N$.


How do I use AES-256-CTR correctly? Is there any specific method to use AES-256-CTR correctly? I heard a Playstation 3 security vulnerability was exploited due to a CTR error. I would like to avoid this.

How Do I Use AES-256-CTR Correctly?

Currently I am using PHP with OpenSSL. I have a key specified as well as the contents of the unencrypted data but I feel there is something else I should add. If it makes a difference, the key and the data will be different each time.

Use the PHP libsodium extension or the PHP encryption library.  Both are high-quality libraries that provide well-documented functions that allow you to do what you need.  They also includes automatic integrity check (this is crucial!), and their operations are protected against timing attacks.

AES256-CTR provides only unauthenticated encryption, which is almost never what you want.  You need authenticated encryption.

The libsodium extension has the advantage of being faster in most cases, but it depends on an extension module written in C, so it might not be available everywhere.  php-encryption is slower, but it only uses PHP’s built-in OpenSSL binding, so it runs everywhere.

Note that nonces must never be loaded from disk and then used for encryption.  It’s way too easy to have a collision that way.  Instead, you should generate a fresh encryption key from a master key each time your program starts (using a KDF and some secure random bytes.)


RSA algorithm private key extraction Decrypting messages can be done by using the following formula:

$$M = C^d \mod n$$

Where $M$ is the decrypted message, $C$ is the encrypted message and $d$ is the private key

Theoretically speaking, Assuming $M$, $C$ and $n$ are known, is it possible for one to calculate $d$ easily? Even for say, large numbers (more than 80 digits etc)?

Solving for $D$ in this case is known as the discrete logarithm problem. This is a known hard problem, as there are no known algorithms to calculate it in polynomial time. In other words, as the size (i.e. the number of digits) of the numbers increase, the time it takes to calculate gets higher exponentially. For this reason, it's used in cryptography as a one-way function for many things including RSA and Diffie-Hellman.


Encrypt-then-MAC: Do I need to authenticate the IV? In the setting of Encrypt-then-MAC, do I need to include the IV in what I'm HMACing, or is authenticating just the AES-encrypted data sufficient?

In short: You must authenticate the IV.
Which particular attacks apply if you don't depends on the block cipher mode; I will give two common examples.

In CTR mode, an attacker who fiddles with the IV can forge authenticated messages, but the content of the corresponding plaintext is beyond his control (since he doesn't know the key). Depending on the encrypted data, this may or may not be a real problem (as random binary garbage may be caught by subsequent validations in the protocol), but it certainly is an unnecessary security risk in any case.
CBC mode breaks horribly, as the following diagram shows:

Clearly, the IV is exclusively XORed into the first plaintext block after decryption and discarded afterwards, enabling an attacker to introduce arbitrary differentials in the first block without changing anything else by XORing them into the IV. Depending on the payload's structure, this could, for example, be used to toggle some important flag in a protocol header or change a length field.


One-way functions and P=NP This site contains various discussions of one-way functions and their relation to P versus NP.

Some of these discussions use a language
$L=\{(x',y) ~\mid~ x'\le x \text{ and } f(x)=y \}$, where $f:\Sigma^*\to\Sigma^*$ is the one-way function and $x'\le x$ is the prefix relation.
Now one central claim is that this language $L$ is contained in NP, since the word $x$ is a YES-certificate for $(x',y)\in L$.

I do not see why this claim is justified.
Why is the length of the certificate $x$ polynomially bounded in the length of $(x',y)$?

Couldn't it be possible that $x$ is exponentially long in $y$ and $x'$, but $f(x)$ is short and quickly computable from $x$?

Yes, it could be that in the language you give, $x$ is exponentially long in $(y,x')$, and $f$ is an efficiently computable one-way function (note that it only has to run in time polynomial in its input length, so $f(x)$ needs not be computable in time polynomial in $(y,x')$).

However, this is really a minor issue: the answers to this question that you read are simply a bit informal, and only give an intuition of the proof that OWF implies $P \neq NP$. Intuitively, to fix this, modify your language as follows:

$L=\{(1^n, x',y) ~\mid~ \exists x, |x| = n, x'\le x, \text{ and } f(x)=y \}$,

where $1^n$ means a sequence of $n$ consecutive one, which exactly allows to fix the issue you point out (note that here $x'\le x$ means $x'$ is a prefix of $x$).

Note: the second answer to the question you link to does provide a link to an exercise sheet which contains the more formal solution.


Deniability of OTR messaging I've been looking at the off-the-record messaging protocol, and there is something about its deniability property that seems strange to me.

Consider the following scenario:

  In the course of an OTR conversation, Alice decides to break Bob's deniability, e.g. she wants to be able to prove to
  some third party that Bob indeed sent one or more of the following messages without any
  way for him to plausibly deny the fact.

  According to the OTR protocol, Bob will publish his old MAC only as
  soon as he gets a positive confirmation of Alice having received his
  newest key by way of Alice using a newer key than the one associated
  with that MAC. This is so that Bob won't publish the old MAC before
  Alice can verify any messages in transit that are authenticated by it.

  But what keeps Alice from just ignoring all of Bob's newer keys starting at a certain point in the conversation,
  thereby making it impossible for him to discard any old key and also
  to publish any of the old MAC keys? If Alice were able to prove that
  she indeed never enabled Bob to publish the old MAC values, wouldn't
  that break his deniability?

Is there some safeguard against that attack, e.g. a timeout of
old keys, that encourages implementations to automatically publish
any remaining old MAC keys, even if the other party never
acknowledges their receipt or just leaves the conversation entirely?

Or is OTR messaging vulnerable against this (admittedly pretty specific) attack?

It does not break Bob's deniability since MAC keys are symmetric. Bob still has plausible deniability as Alice could have just as easily forged any message she claims was from Bob.

Also, remember that OTR uses malleable encryption (a stream cipher mode) and has a forgeability property, which makes deniability even easier for Bob.


How can I do minus on plaintexts in the Paillier cryptosystem? We have $E(a)$, $E(b)$ encrypted under the same Paillier key.

As we all know, we can get $E(a+b)$ by calculating $E(a)*E(b)$.

But can we get $E(a-b)$, by calculating $E(a)/E(b)$?

I tried to calculate $E(a)/E(b)$ by using the mpz_divexact function in the GMP library. But I cannot get the correct result.

In Paillier, as you note, multiplication in the ciphertext domain translates to addition in the plaintext domain. Thanks to the algebraic structure behind Paillier what you can do to get subtraction is use the multiplicative. This works fine when the result is positive. When the result is negative, however, you would like to return that value, but what decryption will return is something between $0$ and $n-1$. For example, if the result is $-1$, you will see $n-1$. To deal with this, we can set some threshold (will depend on the application). If the decrypted value is greater than that threshold, return that value minus $n$. For example, if we see $n-1$ on decryption, we will return $n-1-n=-1$.


FIPS 202/SHAKE: insecure 3DES key derivation example I'm trying to understand the following passage from FIPS 202 (the SHA-3 standard), discussing the SHAKE functions' correlated outputs for different output lengths and the risks they induce in some protocols.  The example they give is this (appendix A.2, "Additional Consideration for Extendable-Output Functions," p. 25):

  [A] naïve (and non-approved) way for two parties to agree to derive a 112-bit Triple DES key from a message designated as $keymaterial$ would be to compute $SHAKE128(keymaterial, keylength)$, where $keylength$ is 112. However, if an attacker is able to induce one of the parties to use a different value for $keylength$, say 168 bits, but the same value for $keymaterial$, then the two parties will end up with the following keys:

  $SHAKE128(keymaterial, 112) = \mathbf{fg}$
  $SHAKE128(keymaterial, 168) = \mathbf{fgh}$,

  where the bolded letters of the digest represent 56-bit strings, e.g., the parts of a Triple DES key.

  Because of the structure of Triple DES, these keys are vulnerable to attack.

I'm trying to understand this example more concretely.  So far what I can make out is this scenario:

Alice and Bob have established a shared secret $keymaterial$, and are now supposed to both compute $SHAKE128(keymaterial, 112) = fg$, and instantiate 3DES with keys $f, g, f$.
Eve however tricks Alice into computing $SHAKE128(keymaterial, 168)$.  So now:

Alice's encryption function is $E^{3DES}_{f, g, h} = E^{DES}_f \circ D^{DES}_g \circ E^{DES}_h$;
Bob's decryption function is $D^{3DES}_{f, g, f} = D^{DES}_f \circ E^{DES}_g \circ D^{DES}_f$.

The composition of Alice's encryption and Bob's decryption functions is $D^{3DES}_{f, g, f} \circ E^{3DES}_{f, g, h} = (D^{DES}_f \circ E^{DES}_g \circ D^{DES}_f) \circ (E^{DES}_f \circ D^{DES}_g \circ E^{DES}_h)$.
Simplifying adjacent inverses in that equation, we get $D^{3DES}_{f, g, f} \circ E^{3DES}_{f, g, h} = D^{DES}_f \circ E^{DES}_h$.
This function is vulnerable to a meet-in-the-middle attack.

If I'm on the right track here at all, where I'm getting stuck is: what larger scenario allows Eve to take advantage of this?  I can picture this scenario:

Eve has these powers:

Trick Alice and Bob into misderiving their 3DES keys as described;
Choose messages for Alice to encrypt and observe Bob's decryptions of them.

Eve uses these to mount a meet-in-the-middle attack that recovers $f$ and $h$ in $2^{57}$ time.

So now Eve knows that $SHAKE128(keymaterial, 168) = fgh$ for some unknown $g \in \{0, 1\}^{56}$.  This certainly allows Eve to bruteforce $g$ within an additional $2^{56}$ tries, but if $SHAKE128$ is preimage-resistant it should still be difficult for Eve to recover $keymaterial$.  So are the dangerous scenarios those where $keymaterial$ is a long-term key, so that Alice and Bob will communicate many times with the same derived $f$ and $g$?

(I worry this might be a bit of a yes/no question, but I figure I must have something wrong above...)

There may well be situations where Eve does not have to trick anybody; in the scenario in FIPS 202 the parties badly use the XOF so the mistake is not necessarily triggered by Eve.

The equations in your question are really not needed. My guess is that you're making it more complex than it needs to be.

Say that Alice and Bob use 3DES with 2 keys $f$ and $g$ then attacking that two-key 3DES key means overcoming a security strength of ~80 bits (given that the chosen plaintext attacks on 2 key 3DES are possible, but hey, we're not excluding any attack here).

Once key $f$ and $g$ are known the key $h$ can simply be brute forced, as single DES only has a strength of 56 bits - the strength of DES itself. However, that means a maximum number of operations of $2^{80} + 2^{56}$, not $2^{80} \times 2^{56}$. In other words, the resulting scheme has a strength of ~80 bits instead of the promised 112 bits offered by three-key 3DES. Removing 32 bits of security certainly counts as a break in any scheme.

The final conclusion that you've written down: that this would be mainly an issue with long-term (or at least often used) keys seems correct.

The point that the FIPS document tries to make is that you should not ever reuse output of the XOF, even if the output size differs - for example when used as underlying function of a Key Derivation Function (KDF).

This indeed has nothing to do with the security of the XOF itself.


request for data to test deterministic ecdsa signature algorithm for secp256k1 I’m implementing the RFC 6979 procedure to compute a message signature. I want to test my program on the secp256k1 elliptic curve. Note the “k” in secp256k1, i.e. the Koblitz curve.

If you have the reliable implementation of RFC 6979 on your machine, I would like you to post data that I could use to test my code.

The data should look like this:

The private key in hexadecimal form that you use.
The message in plain text or in hexadecimal form that you use before it’s hashed. I will use SHA256 to obtain the hash of the message.
The value of “k” in hexadecimal form that your software produces.
The value of “r” in hexadecimal form that your software produces.
The value of “s” in hexadecimal form that your software produces.
Optionally, the complete signature in hexadecimal form that your software produces.


Secret key out of sha-512 This is a setup to produce a secret key for symmetrical encryption with TweetNaCl:

1) K1 consists of 32 random bytes

2) K2 consists of 32 random bytes

(By "random" I mean "obtained from /dev/urandom")

3) KC is the concatenation of K1 and K2

4) K consists of the first 32 bytes of the SHA-512 sum of KC

Questions:

a) Is it safe to use K as a secret key? ("safe" meaning "as safe as using 32 random bytes"; it is assumed that K1, K2 and K are kept secret)

b) If an attacker gets his hands on K1 or K2 (but not on both), does he obtain any real advantage?

Rationale: keep K1 and K2 in separate media (e.g., K1 on a pen and K2 on disk)

a) Is it safe to use K as a secret key? ("safe" meaning "as safe as using 32 random bytes"; it is assumed that K1, K2 and K are kept secret)

Although SHA-512 is not a KDF, and although it is required that the hash has properties that are not mandatory to be used as KDF, most people assume it is secure, yes.

  b) If an attacker gets his hands on K1 or K2 (but not on both), does he obtain any real advantage?

No, the attacker shouldn't gain advantage that way.

Kind of related is the security of KDF1 and KDF2. Hash should be considered a poor mans KDF. For a better KDF, use HKDF or just HKDF-expand.


Why is the NIST recommendation for the private key exponent so much smaller than the modulus? NIST recommends a 256-bit private key exponent for DLP with a 3072-bit modulus. This question answered how the modulus was chosen/calculated, however, why isn't the private key size closer to the modulus size? It would seem that if one achieves order equal to $2^{256}$, this would be a sufficient number of random private key exponent possibilities to make a brute force attack computationally infeasible? So why the disparity between $2^{256}$ private key and $2^{3072}$ modulus?

Generic algorithms for solving the DLP, like Shanks baby step-giant step or pollard rho are of complexity of order $\mathcal{O}(|G|^{0.5})$. That is, for $|G|=2^{256}$ you get a complexity of $\mathcal{O}(2^{128})$. However, for the index calculus method, that is operated on the modulus, for complexity of $\mathcal{O}(2^{128})$ you would need a modulus of size 3072 bits. You may use larger exponent, but this will result in more complex calculations, while the security remains $\mathcal{O}(2^{128})$


Are there any attacks on the key exchange when the client and the server are using the same private key? Assume the same key pair is securely installed on a server and a single client and that the private key exists nowhere else. Can someone eavesdropping on a TLS handshake between the client and server learn anything about the private key or the session key that they wouldn't be able to learn if the client and server were using separate keys?

No, there shouldn't be any weaknesses. The server key and client key don't interact within the protocol in such a way that relationships between the two matter.

Key exchange is done either using the server key (EG:TLS_(server key algo)_WITH_(cipher suite) modes) with the client encrypting a secret which only the server key can decrypt. Or with ephemeral keys (EG:TLS_(DHE/ECDHE)_(server key algo)_(cipher suite)). In both cases, relationships between the server and client keys do not matter.

Client certificate authentication is done separately from key exchange(step 5). The client signs a digest created from messages previously sent in the protocol.

An attacker with access to a client cannot get the client to perform the private operation on arbitrary data. They only control messages which contribute to the hash which the client signs.
An attacker with access to a server cannot use the server as a decryption oracle. They can submit arbitrary encrypted messages to the server as an "encrypted session key" the server will perform the private operation and attempt to use the result to derive a session key. The intermediate result, the result of the private operation is not accessible to the attacker in any useful way.
If TLS is configured to use an ephemeral key exchange, the client authentication is the same but the server is completely useless to an attacker since it just signs an ephemeral public key which the attacker does not influence.

In all cases, the keys never interact in the way you worry about (EG:DH mixing)

SSH is similarly immune. It uses ephemeral keys and client and server keys are used differently so that the client cannot hand back the signature supplied by the server.