Why the following attack in common modulus RSA works? Suppose that i share a common modulus  $N$ with two users $u_1$ and $u_2$ with public, secret keys ($e_a,d_a$), ($e_b,d_b$).
Why then  $gcd(V,e_b)=1$ where $V=d_a*e_a-1/$W and $W=gcd(e_b,d_a*e_a-1)$  and as a consequence with extended euclidena algorithm i compute $α,β$ such that $α*e_b+β*V=1$ and it comes that $α=d_b$

One correction to your question: it's not necessarily true that your procedure will give you $\alpha = d_b$; however, the $\alpha$ you do get will work as a private key corresponding to $e_b$, just not necessarily the exact value that the user $u_2$ has.

With that in mind, here's an outline of why that is so:

First of all, two keys $(e, d)$ will work as corresponding public/secret exponents with an RSA modulus $N$ if and only if $e \cdot d \equiv 1 \space ( \bmod \space\lambda(N) )$, where $\lambda(N) = lcm(p-1, q-1)$.

So, we can restate the problem as: given values $(e_a, d_a)$ with $e_a \cdot d_a \equiv 1 \space ( \bmod \space\lambda(N) )$, and a value $e_b$, find a value $\alpha$ such that $e_b \cdot \alpha \equiv 1 \space ( \bmod \space\lambda(N) )$ (even if we don't know the value of $\lambda(N)$)

Now, the condition $e_a \cdot d_a \equiv 1 \space ( \bmod \space\lambda(N) )$ is precisely equivalent to the statement that there exists an integer $k$ such that $e_a \cdot d_a - 1 = k \cdot \lambda(N)$; let us call the value $k \cdot \lambda(N) = V$.  Note that, even though we don't know the values of either $k$ or $\lambda(N)$, we can compute $V$.

Now, given that we know the values $e_b, V$, we can certainly run the Extended Euclidean algorithm, and find values $\alpha, \beta$ with $\alpha \cdot e_b + \beta \cdot V = 1$.  Now, if reduce both sides modulo $\lambda(N)$, we find that $(\alpha \cdot e_b + \beta \cdot V) \bmod \lambda(N) = (\alpha \cdot e_b) \bmod \lambda(N) + 0 = 1$ (because $V$ is a multiple of $\lambda(N)$), and so $\alpha$ does meet the requirements of a private key corresponding to $e_b$.

Now, a few notes:

The above argument shows that the result is correct, however it doesn't say why someone would happen to stumble upon it in the first place.  Actually, it's not nearly as mysterious as it would seem; what we want is $e_b^{-1} \bmod V$, that is, the multiplicative inverse of $e_b$ modulo $V$, and the Extended Euclidean method is the standard way to compute that.
The algorithm you have divides $V$ by $W$.  It turns out that doesn't change anything; $W$ will be relatively prime to $\lambda(N)$; we know this because $W$ is a divisor of $e_b$, and $e_b$ must be relatively prime to $\lambda(N)$.  So, dividing $V$ by $W$ effectively makes $V = (k/W) \cdot \lambda(N)$; $(k/W)$ is an integer (which is all we cared about $k$ anyways), and so it doesn't change the above argument.
If someone does have a $(e,d)$ public/private key pair for a modulus $N$, it turns out that they can also efficiently factor $N$; however, the explination for how to do that would require a bit more work to explain.


Is there a studied notion of "party independent transfer"? I've been thinking about the following set-up involving three parties, Alice, Bob and Charlie:

Bob and Charlie decide among themselves who is going to receive a bit from Alice (perhaps by a coin toss)
Some protocol is then executed in which Alice transfers a bit to the decided on person.

The protocol is defined as secure if:

Alice cannot change her bit based on which of Bob or Charlie it is that receives the bit (the transfer is "party independent")
Supposing Bob was decided on to receive the bit, Charlie cannot learn the value of the bit handed over by Alice, and vice versa.

My question is this: is there a studied task which is similar to what is described above? Or is this perhaps secretly equivalent to some apparently distinct task? (it sounds a bit like some form of oblivious transfer)

You can get active security in cryptographic setting, but it seems that you also need broadcast.

Bob and Charlie both create an asymmetric key.
Bob commits to his public key a broadcasts the commitment.
Bob sends its public key to Charlie and opens the commitment to him. If these do not match, Charlie complains.
Charlie broadcasts both keys (in random order). If Bob's isn't one of them, he complains by opening the commitment.
Alice picks one key at random, encrypts the message, and broadcasts the result. Only one of them is able to decrypt, and Alice doesn't know who.

Note that the message space should be large, otherwise Bob can just try to encrypt all possible messages with Charlie's key and see which one was broadcast. To remedy this, apply some random padding to the message.

Also note that in step 3, the accusation does not lead to identification of the culprit.


Question on the Quadratic Residuosity Assumption I am reading the Handbook of Applied Cryptography and on page 99 the authors write
, after showing that $QRP \le_P FACTORING$:

  It is believed that the $QRP$ is as difﬁcult as the problem of factoring integers, although no proof of this is known.

I am not quite sure what "as difficult" means, do they say that it is assumed that $QRP \ge_P FACTORING$?

I would put it as "it is conjectured" rather than "it is assumed", but otherwise, yeah...


Canonical inclusion map in subfield attack on overstretched NTRU I'm trying to understand subfield attacks on overstretched NTRU. In the paper https://eprint.iacr.org/2016/127.pdf  authors used "canonical inclusion map" to lift  vector to full lattice. What does the canonical inclusion map relative to finite fields mean? And where can I read more about this construction?

When $\mathbb{L}$ is a subset (or can be view as a subset) of $\mathbb{K}$, the canonical inclusion map just means
"take an element of $\mathbb{L}$ and treat it as element of $\mathbb{K}$".

In general, we do it implicitly and it is not necessary to think about it. For example, when we multiply a real number $r$ by a complex number $a + bi$, we are actually representing $r$ as $r + 0i$ and using the complex number multiplication.

Most probably, the authors defined this map explicitly to keep things formal and because $\mathbb{L}$ and $\mathbb{K}$ have different dimensions when view as vector spaces over $\mathbb{Q}$, so they want to make sure that there would be no confusion about how to compute the norms and other quantities of elements of $\mathbb{L}$ when we use them as elements of $\mathbb{K}$.

For exemple, if $\mathbb{L} := \mathbb{Q}(\sqrt 2)$ and $\mathbb{K} = \mathbb{Q}(\sqrt 2, \sqrt 5)$, then, the elements of $\mathbb{L}$ are of the form $a_0 + a_1\sqrt 2$ and those of $\mathbb{Q}$ are
$a_0 + a_1\sqrt 2 + a_2\sqrt 5 + a_3\sqrt{10}$.
Moreover, $\mathbb{L}$ can be seen as a vector space of dimension $2$ and $\mathbb{K}$ as a vector space of dimension $4$ over $\mathbb{Q}$.

Thus, it is clear that we can see elements of $\mathbb{L}$ as elements of $\mathbb{K}$ with $a_2 = a_3 = 0$. Thus, when you use the canonical inclusion map from $\mathbb{L}$ to $\mathbb{K}$, you are also taking vectors of dimension $2$ and using them as vectors of dimension $4$.

All that said, notice that the authors do not simply use the canonical inclusion map to  lift elements of $\mathcal{O}_{\mathbb{L}}$ to $\mathcal{O}_{\mathbb{K}}$, as they want to guarantee some properties after lifting (like lifted elements being multiples of the secret NTRU vector $(f, g)$ and being small).


ECC keys vulnerable to brute force attack? I have started learning about Elliptic Curve Cryptography (ECC). Since the key size required in ECC is relatively smaller than the key size in RSA (to provide the same encryption strength), I wonder whether the smaller key size of ECC makes it vulnerable to brute force attack.  Does it?

I'm not very knowledgeable about the ways in which a key can be cracked.  But, basically, fewer bits means the number of possibilities can be more quickly guessed or tried!

Yes a brute force key-guessing attack would be faster, but:

It would be ridiculously slow for either. E.g. see this for 256-bit keys.
There are faster attacks on both and those attacks break larger RSA sizes than ECC sizes.

Related: Why can ECC key sizes be smaller than RSA keys for similar security?


Is OMEMO vulnerable in case of compromised jabber server? As I've understand OMEMO protocol specification, the initial key exchange between Alice and Bob can be stored on server and in future used for message decryption.

Also the phrase from Conversations, Jabber Android client, official site:

  This way, not only your messages are safe but more importantly it is impossible for an outside attacker to intercept your meta data (with whom you are chatting) without attacking your server first.

So, does this means that OMEMO is secure only if server and its administration can be 100% trusted?

Does this mean that OTR with its worse usability has better security?

Suppose Alice has never met Bob before—never in her life heard of this ‘Bob’ personage.

Bob initiates a chat with Alice over a Jabber server, which facilitates (a) sending the messages along, and (b) giving Alice and Bob each others' public keys for the first time.

They do a Diffie–Hellman key agreement, of course, so that a passive eavesdropper has no hope of finding the conversation key from the network transcript (more details of how it works).  But Mallory, a NITM (enby-in-the-middle) may have compromised the server.  Here are three possibilities:

The server is honest and uncompromised.  In this case, Alice and Bob get to have a secret conversation about how many Nazis are on Twitter and how many statist tools advocate state surveillance and censorship to suppress the Nazis without realizing—or perhaps without saying—how dangerous state censorship regimes are for marginalized groups like queer people.
The server is compromised by the NSA.  In this case, Alice is actually having a conversation with her personal FBI agent Mallory, who is collecting dossiers on anarchist agitators like me who threaten authoritarian state surveillance regimes.
The server is honest and uncompromised, but Bob is Alice's personal FBI agent Mallory who is collecting dossiers, etc.

If Alice has no prior information about Bob, she has no way to distinguish these cases, no matter how secure the protocol is.  It's the same for OTR, OMEMO, WhatsApp, Signal, the post, or Twitter.


Increasing rounds in DES, increases or decreases the security? I was wondering whether in DES,
if we used more than 16 rounds, the security of the message was increased or actually decreased?
(disregarding the decreased speed of execution / computation.)
Thanks in advance!

Short answer, it increases the security.

The fundamental problem with regular DES is the number of bytes used for the key. It is too low to be considered secure* (with the level of computational power it currently exist, it is feasible to brute force through DES encryption).

Try checking out 3DES article on wikipedia for more info on a better implementation of DES:

https://en.wikipedia.org/wiki/Triple_DES


Agglomerate zksnarks Let a, b be two statements. Given succinct (fixed size) zero-knowledge proofs z(a), z(b) that a, b are true, how easy is it to build z(a AND b)?

One way to do this is to construct two pairing-friendly curves such that the scalar field of the "outer" curve efficiently supports arithmetic for the "inner" curve. Then you can define a circuit for a zk-SNARK over the outer curve, that can verify proofs of a zk-SNARK over the inner curve. This can be done by constructing the outer curve using the Cocks-Pinch method, as in Zexe. In this case you would use an efficient zk-SNARK proving system such as Groth16, to reduce the cost of verifying the inner proofs.

Since I first wrote this answer, another approach has become available using $2$-cycles of non-pairing-friendly curves, as in Halo. (I'm a codesigner of Halo, with Sean Bowe and Jack Grigg.)

The #zcash-wizards channel of the Zcash community chat is a good place to ask about such things.

(This answer previously included a suggestion to use a nested pair of curves with the inner curve as BLS12 and the outer curve as BN. In fact there's no known method of matching up the base field of the BLS12 curve with the scalar field of the BN curve, and there are good reasons to believe that it is not possible to do so.)

Note that any of these approaches will only pay off if the number of proofs being aggregated is large.


Speeding up partially known plaintext preimage recovery attack on MD5 Suppose there are three messages A, B and C of different length, that are 16 DWORDs in length when combined. I know the plaintext and length of A and C, and only length of B. Is it possible to take any advantage of this knowledge when trying to recover a preimage of MD5(A || B || C)? I'm targeting "raw" MD5 transform, as C is in fact padding and bitlength, so I feed it with 16 DWORDs of input and expect to get 4 DWORDs of digest back.

A is 8 DWORDs in length, and B and C are 4 DWORDs in length each.

I can only think of precomputing first round as much as possible as long A message is used, but that does not give that much speedup. Any metacompilation techniques?

UPD1: I have the following idea, but I'm unsure if it has any value in this context and in general. I would greatly appreciate review of it.

It's possible to express each DWORD as collection of independent bits, each possibly being in three states - set (0), unset (1) and upset unknown. All unknown bits have their unique ID, and hold up their creation history - as result of XORing two unknown bits is also unknown, we spawn more unique unknown bits when necessary. It's possible for unknown bit to be "determined" by ANDing it to 0 or ORing to 1, so the outcome is no longer unknown. Also XORing it to itself would make it 0, while XORing unknown bit to it's inverted counterpart will make it 1, and so on.

Rotation has no effect on bits themselves, only on their order in the "DWORD collection". Bitwise operations for DWORDs scale down to bits in obvious manner, and addition is expressed through ADD operation, which returns result and carry bit, which is in turn ignored when adder's result is the MSB.

After such tracing or 'metacomputation' we will end up in directed graph having 128 unknown input bits (message B) and 128 output bits of digest hardly twisted and entangled with input bits. Each node of graph is operation (XOR, AND, OR, NAND, NOR, NOT, ADD etc), incoming edges will be arguments to these functions, outgoing edges are results. Symmetrical transitive binary operations can be extended to arbitrary arity using behavioral definition like 'if any of the arguments is set, result is also set' for OR, or 'invert result of XORing all the unknown argument bits if XORing known bits together produces 1' for XOR.

So first idea is to try to simplify this graph using rules expressed above as much as possible, then unwind each bit's history, revealing long expression of AND/OR/XORs making use of initial unknown bits from B message, and try to find common chains of operations that may be computed at once. Problem with this approach is that I overcomplexify calculations 32 times, as DWORDs are breaked down into bits... Maybe there is way to somehow bond them back, producing some function taking B message candidate and returning single DWORD in most compact way? I don't know. Also I don't know if I can use the same approach but with DWORDs instead of bits at the lowest level.

Second idea is to try to reverse this graph, feeding desired MD5 output into "output unknown bits" and trying to figure out what arguments were to produce such results - for example, if OR(A, B, C, ...) == X, while X being unknown bit revealed to be zero, it's impossible for A, B and C (and others) to be anything but zero, so propagation can proceed. Same applies to AND(A, B, C, ...) == X, where X is set - A, B and C have to be all set. For ambigous cases branching should occur, pushing current graph state into stack, selecting one of possible argument layouts and proceeding until first conflict - e.g. for example according to one expression unknown bit should be unset, and according to other expression same bit should be set, this means one of possible paths previously selected was wrong and next should be tried.

So, as this hadn't implemented already, something is wrong with it. What exactly is wrong? I think it may figure out that time needed for walking through all the branches exceed bruteforce time, but I'm not sure.

It sounds like you're pretty much out of luck.

Yes, there are a few tricks you could use to speed up a brute force search; for example, if we fix everything other than DWORD 3 of B, we can precompute everything up to round 10 of MD5, and compute what the value of the internal 'b' variable of round 52 of MD5 must be to generate the expected hash; this reduces the total number of rounds we compute to 42 (plus a few extra checks that we occasionally do if 'b' happens to be the value we expect, plus redoing the precomputation when we've gone through all possible values of DWORD 3 of B, and we need to try another value for DWORD 1,2,4).

However, such tricks don't come anywhere close to giving you a practical solution.  In fact, even if we were to optimize the time to test a value of 'B' to one CPU clock cycle, and ran the test on one billion CPUs, find a value of B that gives the specified hash would take an expected time considerably longer than the age of the universe.

What you would need is to have a cryptographical weakness in MD5 which would allow you to find such a value without doing an exhaustive search.  Yes, there are a number of weaknesses known with MD5; there's none that gives you this.


MAC in SSH packet encryption, benefits to not including it? What are the benefits to not including MAC in a SSH packet encryption?  I understand what the MAC is there for, but if it was not included would there be an advantage?  Is the MAC somewhat redundant considering  the server host key is used during key exchange to authenticate?

The MAC is NOT redundant.

As alluded to by Paŭlo Ebermann's comment, the word authentication has a different meaning in the two scenarios you mentioned.

In the key exchange phase of SSH, the purpose of authentication is to ensure to both parties that they are indeed talking to the right peer (if using mutual authentication). Typically, the server authenticates itself using its public key and the client uses a username and password.

In the SSH record layer phase (i.e., the sending of the actual application data), the purpose of authentication is to protect each individual data packet from tampering. This is achieved using the MAC. To encrypt application data SSH typically uses either AES in counter mode or in CBC mode. Neither of these modes of operation provides protection against tampering of the ciphertext. Thus they need to be accompanied with a MAC in order to detect this.

Consider e.g., the silly example where Alice sends the following message encrypted using AES in counter mode, but without any MAC:
Transfer 100 USD from Alice to Bob. Then someone (Bob?) could flip a few strategically placed bits in the ciphertext, so that it would actually decrypt to Transfer 10 000 USD from Alice to Bob. instead. Note that without any MAC, it would be impossible for the recipient to notice that this ciphertext had been tampered with. Also, observe that this fact is completely independent of any key exchange that has been done prior to the tampering.

There is of course one obvious "advantage" to skipping the MAC: you save the 80-128 bits of overhead needed to transfer it for each data packet you send. But this is not safe and should not be done!


How do I safely anonymize/hash a unique identifier to protect privacy? I am building a system to collect a unique identifier (MAC addresses from 802.11 probe requests). The system will have several collection points over a large area, submitting to a central database. I want to do traffic analysis without allowing a known MAC address to be mapped to the points where it was seen.

My goals:

Anonymize the MAC addresses the same way for each device, to allow tracking of an anonymous device over time, regardless of which collection point sees the device.
Anonymize in such a way that an attacker with a user's MAC address and a copy of the database can't trace the user's movements.
Ideally, the addresses are secret from shortly after the moment of collection and unknown even to me (I can be considered an attacker, especially by the users being collected).

It's like I'm designing a web service where the username and password are the same. Anywhere I store instructions for generating the hashed MAC address (either a per-address salt or a general hashing instruction) I'm providing an attacker with the means to de-anonymize users.

Could I encrypt the MAC addresses using a public key for which I don't have the private key? That's really just a fancy way of hashing, and considering there are only 334 billion addresses in the registered IEEE namespace (considerably fewer for common manufacturers like Samsung and Apple), it's only partly resistant to attack.

I'm just not sure where to go from here, except to start making security tradeoffs.

Few answers to your questions

Storing per address salt (assuming you are using it for encryption) is not same as storing the mapping with the hash. Salt could be public.
You could encrypt anything with a public key for which there is no private key yet, Checkout more on Identity based encryption techniques.

Few additional inputs for anonymization

Any anonymization technique for the MAC Address (either encryption, hashing or tokenization) could be broken through inferential attacks based on rest of the parameters that are not anonymized. Since you intend to do traffic analysis, you would need to deterministically anonymize (retain the one-one mapping either through hash or deterministic encryption), any adversary who has access to same anonymized database can identify the same patterns!
Other than inferential attacks on the logs/database, attacks based on implementation, key management, poor entropy etc also used in practice.
Micro anonymization techniques (say MAC addresses, IP Address and other field level anonymization alone ) are recommended only when any analytic s needs to be performed on the data, else it is better to encrypt the whole record.

Few references

*T. Farah, “Algorithms and tools for anonymization of the internet
traffic,” Ph.D. dissertation, SIMON FRASER UNIVERSITY, 2013

R. Pang, M. Allman, V. Paxson, and J. Lee, “The devil and packet trace
anonymization,” ACM SIGCOMM Computer Communication Review,
vol. 36, no. 1, pp. 29–38, 2006.

A. Narayanan and V. Shmatikov, “Robust de-anonymization of large
sparse datasets,” in Security and Privacy, 2008. SP 2008. IEEE Sym-
posium on. IEEE, 2008, pp. 111–125.*

Of course there are tonnes of other papers written on this topic over years.
You can read our recent paper published in IEEE- CCEM 2014
http://www.researchgate.net/publication/265598254_Network_Telemetry_Anonymization_for_Cloud_Based_Security_Analysis_-Best_Practices


Why do 5G, 4G, etc., use non-conventional algorithms? Looking up information about 5G and the previous 3GPP standards, why have they been incorporating non-conventional algorithms into the standards? For example, AES has been considered secure for ages and there is lots of support for hardware acceleration, but what was the rationale behind, for example, adding ZUC and SNOW 3G too? Does adding more algorithms make it easier for network operators in any way?

These decisions are driven by silicon.  Most specifications for hardware are built around a minimally viable CMOS implementation (ex: MPEG-1, lightweight cryptography via NIST 8114).  This is particularly true in commodity parts, such as cell phones.
When you make wireless ICs, you have two clocks in the system at a minimum, which are the carrier frequency and then the baseband frequency.  As an example, for the 900MHz RFID tags that are used for inventory control, you have a 900MHz frequency and then a 1MHz-ish clock (programmable) that handles bit stream generation to  give you about 100kbs of throughput.  When I make RFID tags, I use a feistel cipher in a bit serial mode because I can use the carrier clock run the cipher in a way that I do not have to wait for data to be ready.  By the time that the slow data has been encrypted, it's ready to send.
In the case of AES, I need to fill 128-bits into the register, and then add a buffer to hold the result.  You need to do this with the feistel ciphers as well, but AES is rather large in silicon and slow compared most feistel ciphers in this specific context.   Not using AES allows me to use less silicon, which then helps keep costs down.
update:
Looking at my GDS files for layout and simulations on an ancient process (GF 180nm), SIMON 128/256 was 30% of the area and 50% of the power compared to AES256 for an RFID tag. The sboxs were not done with a lookup table, but explicitly calculated in circuits.  A note, I do not believe that this would scale well due to metals at sub-14nm nodes (sadly, my lectures from Georgia Tech are all no longer online, as I spent a week on this.  Stanford  has some lithography notes.  I'm still looking for a good public facing document).  I would expect the feistel to be a little larger, but AES to scale the same due to colored metals; however, the power should be similar. (I cannot share specific details on modern processes.)


With OpenSSL and ECDHE, how to show the actual curve being used? Using

openssl s_client -host myserver.net -port 443

I can see the cipher negotiated is indeed using ECDHE for session key exchange:

SSL handshake has read 5894 bytes and written 447 bytes
---
New, TLSv1/SSLv3, Cipher is ECDHE-RSA-AES256-GCM-SHA384
Server public key is 2048 bit
Secure Renegotiation IS supported
Compression: NONE
Expansion: NONE
SSL-Session:
    Protocol  : TLSv1.2
    Cipher    : ECDHE-RSA-AES256-GCM-SHA384

Both the client and the server use exactly the same OpenSSL version "OpenSSL 1.0.1e 11 Feb 2013" and I can get the list of available, builtin curves using:

openssl ecparam -list_curves

However, how do I find out which elliptic curve is actually being used in the session?

For completeness, here are the TLS handshake messages relevant to curve negotiation from a real-world session (using the openssl command given by Thomas):

ClientHello:

>>> TLS 1.2 Handshake [length 013c], ClientHello
    01 00 01 38 03 03 52 6c 53 04 fb 32 94 d4 f4 91
    53 fe 59 5c d1 58 7f e0 67 e0 22 db da f4 8d ac
    dc 15 68 21 3d ec 00 00 a0 c0 30 c0 2c c0 28 c0
    24 c0 14 c0 0a c0 22 c0 21 00 a3 00 9f 00 6b 00
    6a 00 39 00 38 00 88 00 87 c0 32 c0 2e c0 2a c0
    26 c0 0f c0 05 00 9d 00 3d 00 35 00 84 c0 12 c0
    08 c0 1c c0 1b 00 16 00 13 c0 0d c0 03 00 0a c0
    2f c0 2b c0 27 c0 23 c0 13 c0 09 c0 1f c0 1e 00
    a2 00 9e 00 67 00 40 00 33 00 32 00 9a 00 99 00
    45 00 44 c0 31 c0 2d c0 29 c0 25 c0 0e c0 04 00
    9c 00 3c 00 2f 00 96 00 41 00 07 c0 11 c0 07 c0
    0c c0 02 00 05 00 04 00 15 00 12 00 09 00 14 00
    11 00 08 00 06 00 03 00 ff 01 00 00 6f 00 0b 00
    04 03 00 01 02[00 0a 00 34 00 32 00 0e 00 0d 00 [>>  ?
    19 00 0b 00 0c 00 18 00 09 00 0a 00 16 00 17 00
    08 00 06 00 07 00 14 00 15 00 04 00 05]00 12 00  <<] ?
    13 00 01 00 02 00 03 00 0f 00 10 00 11 00 23 00
    00 00 0d 00 22 00 20 06 01 06 02 06 03 05 01 05
    02 05 03 04 01 04 02 04 03 03 01 03 02 03 03 02
    01 02 02 02 03 01 01 00 0f 00 01 01

ServerKeyExchange:

<<< TLS 1.2 Handshake [length 014d], ServerKeyExchange
    0c 00 01 49 03 00 17 41 04 7e 74 d7 ed f4 7b 2f
    ...

You can make OpenSSL print out the handshake messages with the -msg parameter:

openssl s_client -msg -connect myserver.net:443

Then look for the ServerKeyExchange message. Here is an example:

<<< TLS 1.2 Handshake [length 014d], ServerKeyExchange
    0c 00 01 49 03 00 17 41 04 6b d8 6e 14 1c 9b 12
    4d 58 29 20 e8 e2 1a 24 0d da 8f 38 1a 5d 85 2b
    2b 70 61 97 3b a7 5b fd b6 14 b3 5d f0 dd ea 7b
    68 d9 eb bc b2 59 32 52 9d 8e 9c 97 c0 d4 45 4c
    (...)

This can be analyzed, using RFC 5246 and RFC 4492 as references. In this case:

0c: this is a ServerKeyExchange message (described in section 5.4 of RFC 4492)
00 01 49: of length 0x000149 bytes (329 bytes)
03: the curve type is "named_curve"
00 17: the curve is secp256r1 (curve identifiers are in section 5.1.1, identifier 0x0017 is 23 in decimal).

secp256r1 is also known as P-256, one of the 15 curves standardized by NIST in FIPS 186-4. In fact this is the curve that almost everybody uses.


How to prove that the Permutation cipher is not CPA secure? Encryption scheme is called a permutation cipher if every plaintext string with letters
$a_1,\ldots, a_n$ is encrypted as $a_{\pi(1)}, \ldots, a_{\pi(n)}$ for some (not necessarily uniform) permutation $\pi$.

To break this cipher, one has to distinguish two messages based on their encryptions. I'm trying to solve this by playing a game.

Two players A and U.

A: send a plaintext message to U (in this example A sends followashore)

U: Encrypt this message and send the cipher text to A

Input size of $\pi$: m = 6
$\pi$: $\begin{array}2 &1 &2 &3 &4 &5 &6 \\ &3 &5 &1 &6 &4 &2\end{array}$
Ciphertext: LEFOOLHEARSO

A: Changes this ciphertext by appending text $p$ of length $l$, which is a multiple of the length of the original plaintext. Let's say A sends LEFOOLHEARSOLEFOOLHEARSO (concatenated the ciphertext with itself)

U: Encrypt this message using the previous permutation?

I'm not sure where to go from here.

If $a_i = c$ for all $i$, then clearly $a_{\pi(i)} = c$ for all $i$ as well, regardless of the permutation $\pi$.

Thus, you can choose your two messages $a$ and $b$ such that, say, $a_i = 0$ and $b_i = 1$ for all $i$.  This will then also be true for their encryptions under any permutation cipher, allowing you to trivially distinguish the encrypted messages with 100% certainty.


What papers describe the rationale behind cryptography algorithms I am trying to introduce myself to cryptographic hashing and encryption. I am looking for original papers of sorts, to describe the inspiration behind why they choose certain numbers, if they are relevant, and why they choose certain algorithm features. But every paper I have found so far is like this which just describes the algorithm like encyclopedic metadata. Where can I find the meat on the bones, the why they chose certain features?
I assume starting at earlier algorithms (like SHA1) is probably better because they may specify the reasoning in more detail. But as they get to more recent (and secure) algorithms, they just cite the old algorithms for the meaning behind the decisions.
I am looking for things like SHA256 or other secure algorithms, but perhaps simpler nonsecure ones are better to start. For example, why does the SHA1 algorithm use 5 prime numbers? Why not 4, or 8, or non-primes?
Before processing any blocks, the H's are initialized as follows: in
   hex,
      H0 = 67452301
      H1 = EFCDAB89
      H2 = 98BADCFE
      H3 = 10325476
      H4 = C3D2E1F0.

That's all that is said.

First, I understand your question and the frustration that comes along with it, and it is not uncommon. I will warn you that from my perspective, there isn't really an easy answer that provides quick satisfaction. But let me try to point you in the right direction.
For a simple beginning path, I will point you to Jean-Philippe Aumasson's book, "Serious Cryptography" in Chapter 6 page 111 there is a section on "Building Hash Functions" but also notice that the section BEFORE this one talks about the characteristics of hash functions. If you read the "Building Hash Functions" section you won't really get the answer I think you are looking for asking (i.e. Why these constants?), however you will get some clues to constructions.
Looking into the characteristics of what hash functions need to provide (i.e pre-image resistance, 2nd pre-image resistance, and collision resistance) you see the goal that is trying to be achieved by a hash function. Until you study attacks on these goals, and deep security proofs of the functions, you will not come close to answering the questions you are asking. They are not easy question.
Two papers I will recommend. Bellare, Kilian and Rogaway "The Security of the Cipher Block Chaining Message Authentication Code" gives a formalism for MACs, PRFs and PRPs which is essential for your deeper understanding. Also Bellare, Canetti and Krawczyk "Pseudorandom Functions Revisited: The Cascade Construction and its Concrete Security" which discusses the iterative construction used in hash functions. These will give you some of the formal basis used in constructing hash functions (IMHO). Another paper that I believe is absolutely fundamental for going to this deeper level in cryptography is Bellare, Desai, Jokipii and Rogaway "A concrete security treatment of symmetric encryption"
Once you really consume these papers, and you get a handle on the simulation games used to prove security, and the attacks that you need to present, certain things will become more transparent. In addition, you will be able to read some proofs and attacks on algorithms with more clarity.
I would then recommend some reading on the Random Oracle Model, which is often used in proofs that use hash functions, and then look at papers around the SHA3 competition. I think it is really illuminating to read papers on SHA3 and thesis on hash functions - I will recommend one though I won't make any claim that it is the best (Ozgul Kucuk "Design and Analysis of Cryptographic Hash Functions" 2012).
These references should start you in your journey to acquire the knowledge you want so you can answer the questions you posed. I hope you find this direction useful.


How to pad messages with large amount of padding I'm playing around with an application for secure email-like communication and I want to perform length hiding padding on the plaintext messages so they always have a consistent size before encrypting with AES.

I would like to do PKCS7 style padding (if possible), because it's easy to figure out how much to strip from the decrypted output, but how would you do such a padding if the amount of padding exceeds what can be described with one byte? i.e. if I have a message that is 2.000 bytes in size and I want to pad it to become 16.000 bytes in size. This requires a padding size of 14.000 bytes which is 0x36B0 in hex, how would the padding look like for such a value and how can I know that I should take the last two bytes instead of the last byte to find the padding size?

Thanks in advance!

As you note, PKCS7 padding isn't designed to do exactly what you want; it's really designed to allow you to pad up to the next multiple of the block size, that is, to the next multiple of 8 or 16.  That it does rather well; however, it's not designed to do what you want with it.

I would note that for block ciphers, as long as you also include a good Message Authentication Code or some other way of ensuring integrity, that the actual padding method isn't critical to security; the AES encryption itself will ensure that there is no information leakage other than message length, and the MAC will ensure that, if the attacker tries to play games with modifying the message, well, that'll always result in a MAC failure, and so that attacker won't learn anything).  This is true even if you try to design a padding scheme specifically to leak information (assuming, of course, that your padding method doesn't use the key).

Hence, the only real constraints on your padding scheme is:

Not to leak any information do to the message length (that's the one thing AES does not disguise)
Be able to remove the padding to obtain the original message without ambiguity

As long as you follow those two constraints, you're golden.  One obvious way to meet both goals is to pad the message out to a fixed length; and then add a 2 (or 4) byte 'original message length' at either the beginning or the end of the message.

I'm assuming that you aren't concerned about interoperability with existing systems; if you are, then you'll need to live within whatever system they are using.

And, the above answer "the padding method is not critical" applies only to block ciphers along with some MAC); when you consider other cryptographical primitives (say, RSA), the padding method does become important in those cases.


Steganography - How many bytes of information can you hide in a $1024 \times 768$ photo? I have a photo with a resolution of $1024 \times 768$ which means $786432$ pixels in total. Let's suppose it's a 24-bit color RGB image (so 1 pixel = 3 bytes = 24 bits) and I want to hide information by only modifying the last bit of a color value. What is the maximum number of bytes that I can hide in this photo?

This is one of those answers that - depends.

The amount of data that can be hidden inside an image depends on the image.  This is one of the concepts that most steganographers miss.  We have to go to the definition of steganography.  Hiding a secret message with emphasis on the hiding part. That means that a message may or may not be contained within the pixels of an image, creating plausible deniability.  If you overtly don't bother to hide it, you might as well traditionally encrypt the message with AES, append it to an email and add "Secret message attached" to the subject heading.

It is also a requirement that the message is compressed /encrypted or generally whitened.  Whist encryption is not absolutely necessary for steganography to be successful, the message has to be converted to almost randomly distributed bits.  Any uncompressed /unencypted pattern can be easily discovered via heuristic or frequency analysis of the image. After all, image noise is almost uniformly random.  If compression is used, the amount of data is becomes contingent on it's type and therefore it depends.

From a capacity and mathematical deniability perspective, the following type of image is optimum:-

It's just random noise in all three colour channels.  If the least significant bit contained the compressed message, and the message was textual, you might expect 9 Mbits of capacity£.  You may have issues of plausible deniability though if you're sending many of these images without a really good excuse.  And they'd have to be in the form of a lossless format, which again is uncommon.  Tools like OpenPuff can use lossy formats but that then reduces the message capacity.

This is also a problem image:-

Here the whole mountain side is blown out.  Image analysis would easily identify manipulation of the least significant bits of the mountainside as they're all meant to be exactly 255,255,255. Almost half of the image can't be used.  The steganographic tool would have to determine this.  An image with deep shade presents the same problem featuring an expected RGB of 0,0,0 for that part of the image.  So again the message size depends.

So you're left with using images like:-

In this instance you might get 9-18 Mbits of text$, but you're reduced to sending grainy images all the time for this message capacity. The sensor noise will mask the whitened message, especially if you use less than 1 bit per channel per pixel.  And they have to be lossless formats like BMP /JPEG2000 /TIFF or PNG.  None of these are particularly common in the social Facebook world, compromising the plausible deniability argument.  A lossy format will reduce the message size again.

Algebraically, you can form an equation like:-

capacity = (usable %age) X (encoded bits) x (no.pixels)

which represents the difficult relationship of:-

capacity = F(artistic composition, SNR, image size)

In summary, the message size is very difficult to quantify without a detailed analysis of your photo.  Why don't you post it?  The most important take away here is that the issue with steganography is not encrypting a message in an image, but being able to deny that there is one in the first place. This is similar to the deniability issues with disc encryption software like TrueCrypt.

£ I'm assuming that a large sample of English prose can be compressed to 2 bits /byte.  Capacity = 1024*768*3*4 =~ 9e6 bits where 4 is the compression ratio.

$ In an image this noisy (low SNR), it might be possible to utilise 2 bits per image byte for the message.  Or even more?


Understanding a variant of Shamir's cryptosystem with authorization levels I am having problems understanding this implementation of Shamir's secret sharing with confidentially levels (in this case 3).

I will give the context and then my problem to make it more clear.

Context:

in some security system, to share a secret S, they use Shamir's secret sharing. the users in the system are divided to 3 levels of authorization: A, B, and C. To recover S, we need:

A) two users from A

OR

B) one user from A in addition to three users from B and 5 users from C

Problem:

Assuming that in level A there are only 2 users, and one of them decided to resign. His part of the secret, X, he shares with all of the participants, except the other user from level A, so to recover X we need 4 participants from B and one participant from C. Describe the new secret sharing cryptosystem. What does each participants hold and how to recover S?

Questions:

I am having a real hard time understanding this cryptosystem variant of Shamir's secret sharing. There are a lot of variants here.

I really don't understand what each participant hold and how to recover the secret S in this complicated scenario.

Could you please elaborate on it to help me understand it better? I feel totally lost.

I really don't understand what each participant hold and how to recover the secret s in this complicated scenario.

Part of the issue you're running into is that the method to implement the original scheme is not uniquely defined, and so what the various parties hold (and how they would recover the secret) would vary based on things not specified in the question.

The most straight-forward way you would do this is to share the secret two ways:

Once with a $(2,2)$ scheme (and which you would give a share to each of the A parties)
Once with a $(3, 3)$ scheme

For the three shares generated by the latter scheme, you would give them out as:

One would go to each of the A parties (and so both parties would get the exact same share).
One you would secret share with a $(3, n)$ scheme (and each of the B parties would get a share)
One you would secret share with a $(5, n)$ scheme (and each of the C parties would get a share).

In this method, each of the A parties get a "share" which consists of two separate lower level Shamir shares, while each of the B, C parties get a single Shamir share.

If we assume that this is the method used, then it should be straightforward to write out what everyone would hold if the A party leaving were to reveal his share, and how that would allow 3 B parties and 5 C parties to recover the secret.

Note: with these requirements, it is possible to design an alternate scheme where every party holds a single Shamir share; you might find it educational if you were to find that yourself.


generate hash of all handshake messages for verify data (DTLS) I am trying to create a DTLS client finished packet, where I need to generate verify data for handshake hash is need. And here I want to know how to generate handshake hash. As of now I am doing like this:

memcpy(hs_msg, client_hello_with_cookie+13, client_hello_with_cookie_len-13);
len = client_hello_with_cookie_len-13;
memcpy(hs_msg+len, server_hello+13, server_hello_len-13);
len += (server_hello_len-13);
memcpy(hs_msg+len, server_hello_done+13, server_hello_done_len-13);
len += (server_hello_done_len-13);
memcpy(hs_msg+len, client_key_exchange+13, client_key_exchange_len-13);

But the hash of handshakes seems to be wrong while comparing with openssl. (I am using sha1).

Need help to solve this...

Thank you very much.

First, I am assuming, per https://security.stackexchange.com/questions/29172/what-changed-between-tls-and-dtls, that the client handshake protocol in DTLS is not different from that in TLS over TCP.  This seems a safe bet since the client/server encrypted handshake protocol in OpenVPN's UDP implementation is the same as in standard TLS over TCP.

I am not sure what you mean by "using sha1", since the client encrypted handshake message hash $V$ use a concatenation of MD5 and SHA1 hashes of the concatenated handshake (TLS opcode 0x22) messages.  Details are in Davies' "Implementing SSL/TLS," pp. 345-350:

$$V= \text{PRF}(\text{master secret},\text{"client finished"},\text{MD5}(H)\|\text{SHA-1}(H),12)$$

$H$ is the concatenation of the handshake messages; "PRF" is TLS-PRF, a Python implementation of which follows:

def TLS_PRF(secret,label,seed,length):
    def P_HASH(secret,seed,length,h):
            i = 1
            A = [seed]
            out = ''
            while len(out) < length:
                    A.append(HMAC(A[i-1],secret,hasher=h))
                    out += HMAC(A[i]+seed,secret,hasher=h)
                    i += 1
            return out[:length]
    f=''
    md5 = P_HASH(secret[:len(secret)/2],label+seed,length,hashlib.md5)
    sha1= P_HASH(secret[len(secret)/2:],label+seed,length,hashlib.sha1)
    for m,s in zip(md5,sha1):
            f += "%c"%(ord(m)^ord(s))
    return f

If you run the concatenated 0x22 messages through the complicated process noted above, you should get agreement with at least the hash in the client's plaintext EHM.

Calculation of the server EHM hash is slightly trickier.  To $H$, the extant concatenated 0x22 messages, you will need to concatenate the decrypted 12 byte value $V$ contained in the client EHM.  Do not forget, per the RFC, to prepend this 12 byte value with the message type (probably 0x14) and three byte length value (0xc) - so add 14 00 00 0c <12 bytes of V> to the $H$ used for the client EHM, run that through the PRF (using "server finished" for your label), and you should have your final hash value.

Calculation of DTLS Application Data MACs

This is in response to an additional question posed by OP in comments to this answer, concerning calculation of the Application Data (DTLS packet type 0x17) MAC values.  According to RFC 4347:

  The DTLS MAC is the same as that of TLS 1.1. However, rather than
     using TLS's implicit sequence number, the sequence number used to
     compute the MAC is the 64-bit value formed by concatenating the epoch
     and the sequence number in the order they appear on the wire.  Note
     that the DTLS epoch + sequence number is the same length as the TLS
     sequence number.

Here is some Python code that implements this for a packet at the beginning of the DTLS session, with the starting SeqNum and EpochNum values.  $D$ is the decrypted application data including the "decrypted" IV at the start of the message, and the MAC and padding at end of message (basing all of on this on how Wireshark dissects DTLS traffic).

    SeqNum="000000000001".decode("hex")    #passed over wire
    EpochNum="0001".decode("hex")          #passed over wire
    PacketType="17".decode("hex")          #Application Data
    ProtocolVersion="feff".decode("hex")   #DTLS 1.0
    PacketLength="0400".decode("hex")      #Tricky - the length of AppData (as passed in clear over the wire) minus 0x20 bytes of SHA-1 MAC and padding
    D="0xf00ba..."                         #The decrypted blob

Then the HMAC will be:

HMAC(EpochNum+SeqNum+PacketType+ProtocolVersion+PacketLength+D[0x10:-0x20],hmacKey)

Don't forget the exclude the first 0x10 bytes (which will be the meaningless, "decrypted" IV) and the last 0x20 bytes (MAC+padding).  Apart from not including/ordering EpochNum and SeqNum correctly, the only other big pitfall, as previously noted, is forgetting to adjust the PacketLength to reflect the fact that the MAC obviously doesn't include itself as part of the message (see Davies, p. 376 for a discussion of this point in traditional TLS context).


KEA assumption details In order to understand the construction of a zK-SNARK, I have recently been trying to understand the KEA1 assumption in The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols by Mihir Bellare and Adriana Palacioy.

I do not understand the meaning of this assumption. For example, why is this "hard problem" used in cryptography?

On page three of the paper, the authors roughly outlined the assumption, but this didn't clarify things for me. I have a strong math background, so if someone could explain the KEA1 assumption to me in a mathematical way, that would be great.

I think why this assumption is hard is that in the prime field $F_p$, you can't find directly $a$ from $g^a \bmod p$ , where $g$ is generator.
So if prime is too large it takes a lot of time to find $a$, because you need to try all the elements in $1..p$.

that is based on DLP(Discrete Logarithm Problem).


Solutions to $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ with $|x_i| < \ell$ Are there any clear conditions on $p,\ell$ and $m$ under which the equation $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ has at most one solution with $|x_i|<\ell$ with high probability over a random choice of $\gamma$ and the $\xi_i$?

This is closely related to the SIS problem, but instead of having several equations this only involves one.
Also, the question is not about the hardness of finding such solutions, but about the conditions on which at most one solution exists.

As an example, if $\ell = 2$, then the problems looks much like the Knapsack problem, and is likely to have one solution at most. However, as $\ell$ grows larger, the chances there are more than one solution also grow.

Are there any clear conditions on $p,\ell$ and $m$ under which the equation $\gamma \equiv \sum_{i=1}^m \xi_i\cdot x_i\bmod p$ has at most one solution with $|x_i|<\ell$, where $\gamma$ and the $\xi_i$ are uniformly random?

For any $\ell \ge 2$, there will be values of $\gamma$ and $\xi_i$ for which there are multiple solutions; one such set of values would be $\gamma = 0$ and $\xi_1 = 0$.  Hence, any condition that forbids multiple solutions would necessarily have $\ell < 2$ (which isn't very interesting)

Perhaps you mean to ask "yields more than one solution with probability $< \epsilon$"; that is a rather harder question, but might give you a more useful answer.


How to calculate active s-boxes from branch number? If MDS in AES has branch number 5 (so 5 active s-boxes in 2 rounds), wouldn't that mean 4 rounds of AES has $5*2=10$ active s-boxes?

AES paper says it has 25 ($5^2$?) active s-boxes in 4 rounds.

How to calculate minimal active s-boxes from branch number for any given number of rounds?

Edit: J.D. noted that you can't calculate the minimum number of active s-boxes from the branch number of MixColumns, because MixColumns isn't the only operation. So let's assume cipher has full state MDS like SHARK and Khazad.

Khazad has an $8\times 8$ MDS matrix $A$ used as the diffusion layer. The augmented matrix $[I|A]$ generates a $[n,k,d]=[16,8,9]$ MDS code over $GF(2^8).$ The implications are:

The minimum number of active Sboxes, i.e., the minimum branch number across 2 rounds is $9,$ the minimum weight of the MDS code.
MDS codes have a fully known weight distribution, so the full branch number distribution is also known, assuming a uniform input distribution into the Sboxes.

See here for the weight distribution. Briefly,
$A_i$ denotes number of codewords of weight $i$, thus also the number of occurrences of branch number $i.$ In this case
$A_0=1,$ and $A_i=0,$ for $1\leq i \leq d-1.$ The other nonzero weights are
$$
A_i= \binom{n}{i} \sum_{j=0}^{i-d} (-1)^{j}\binom{i}{j} \left( q^{i+1-d-j}-1\right),
$$
for $d\leq i \leq n.$

Here $q=2^8, d=9.$


What encryption schemes to hide the plaintext length exist besides padding? From this answers comments a statement came up about padding that I don't understand: "If we need to keep the length of the plaintext confidential to some degree, there are better methods."

Are there any methods of hiding the plaintext length besides padding?

Assuming:

The data to be sent is incompressible.
If Steganography is used then leaving random data unchanged is equivalent to padding with random data.
Plaintext length and plaintext rate are related, |2x| every hour is equivalent to |4x| every two hours.

There are two basic ways to hide the length of a message. And one probably bad way.

Expand (pad with non-message bytes) the message to a constant length. Or multiple of a large constant.
Shrink the length of a message to a constant or multiple of a large constant.
(Bad) Pad all messages with a random number of bits.

Fgrieu is definitely talking about padding on a block cipher level. CBC mode leaks the length of a message accurate to within one multiple of the block size (say 128 bits). CTR mode leaks the length accurate to within one byte (normally) or (potentially) one bit. 128 bits is too accurate a level to hide the plaintext length well.

There are a lot of parts to the conversation. What you're thinking of is probably what I listed as method one. That's a different type of padding. Over a low bandwidth channel this method is likely unusable. With unconstrained bandwidth or for data at rest this type of padding works fine. There are just the obvious problems of wasted bytes and what to do if you go over a constant length.

Method 2 seems impossible. You can't shrink a message that's uncompressible. If you can compress data, though, and then you use method 1 to pad the compressed data, then this doesn't leak any more information about the message than not compressing/padding does. Uncompressed unpadded messages leak the length of a message's encoding in bytes and puts an upper bound on what the entropy of the message is. Using compression and padding leaks only an upper bound on the entropy of the message.

Where he notes that compression can be dangerous he's referring to things like VOIP that do not use constant bit rate compression. If you use variable bit rate  with real time audio then you leak how compressible the audio data is. Silence is highly compressible so a passive observer would notice short packets and conclude that the person is probably silent. (Or if the packets are frequent and shorter the silence between words/syllables.) And it's possible that harder entropy/packet-length analysis could reveal something more valuable. It's probably harder to do a distinguishing attack on someone saying spoken digits. One might be able to steal ID numbers or credit card information sent through the channel that way.

A constant bit rate encrypted protocol can either use no compression (and use more bandwidth) or use lossy compression that keeps only a constant amount of information. Constant bit rate compression will discard information if a signal contains more information than can fit in a constant signal-bandwidth (meaning a symphony would not sound right) and it transmits more data than necessary when a signal is less complex. (For good bit rates you won't notice a difference in quality between no compression, lossless compression, and constant bit rate compression of voice audio data.)

Note fgrieu also says "duration of encryption/decryption will leak some indication about the nature of plaintext". This is another problem. If your constant bit rate compression algorithm isn't also a constant time algorithm, then data related to message entropy is leaked via packet timing unless you transmit infrequently enough to transfer at fixed intervals.

If you're transmitting say HTTP data instead of a signal you can reduce to constant bandwidth, then compression can be dangerous. BREACH and CRIME are examples. Both are active attacks that exploit partial known plaintext data and partial chosen plaintext data. You could steal cookies if the attacks work.

Those types of attacks are a good reason to disable compression on the protocol level. Not all compression is bad. If you're a website serving static constant and send no cookies to steal, then it doesn't make a difference whether you serve compressed data or not. (It's still probably safer to recommend compressing at a file level.) For a public, crawlable, static websites that don't perform message length padding (specifically to defeat message length leaks) it's simple for a passive observer of a network to eliminate the secrecy you expect from encryption. Such an attacker can crawl every page of the static website, build a database that relates paths on a website to the length of the pages returned by a query for that path. If there is one file on the website that is about 25.33 megabytes and you see the server send about 25.33 megabytes to the client over a short period of time, this will give them a big clue concerning what specific content you are viewing on the website. This type of attack works whether you're sending an uncompressed file, an uncompressed file compressed at the protocol level, or a pre-compressed gzip file; as long as the stream lengths are fairly distinct.

There are two more, more advanced, methods you could use that are a combination of methods 1 and 2. If you don't want to leak metadata such as when you're communicating with other computers, the length of the message you want to send, or the messages entropy, then you can build a communications channel that sends fixed size packets at fixed intervals regardless of how the channel is being used. You put message data into a first in first out queue. When its time to send a packet, then take out as much as you can up to the packet length minus say a byte, set the first byte of a packet to the number of message bytes, set the remaining packet bytes to zero, and encrypt the entire packet, including the length field and the zero padding. This scheme pads when you're transmitting less data than there is available bandwidth and chops messages into smaller constant size segments when you're transmitting faster than bandwidth allows. This is analogous to the purpose number stations probably serve.

The second advanced scheme I can think of is to get together a group of friends you trust and agree to send your message data all at the same time from the same computer. Each sender uses their own personal secret key but the entire aggregate of encrypted messages gets sent to every recipient. The recipients try decrypting every message addressed to them and throw out data they can't decrypt. If Alice and Bob trust each other not to leak their personal message length and they're addressing two recipients they trust not to leak their message length, then instead of leaking $|M_A|$ and $|M_B|$ only the value $|M_A| + |M_B|$ leaks. The RetroShare and ZCash projects may do something with a similar philosophy, but for anonymity purposes instead. I'm not sure about them.


Sample RSA-style signature confusion I'm trying to study a simplified TLS-style protocol, including verifying RSA signatures. It's an attempt to verify using only a valid certificate. However, I can't manage to get anything to verify properly. I have a modulus, exponent, signature, and hash of the message. With the following parameters:

  modulus = 28459 = n
  exponent = 7 = e
  signature = 5128 = s
  hash(m) = 4085 = x

As I see it, I should be able to take the following

  s^e mod n = 5128^7 mod 28459

and see if it equals

  x mod n = 4085 mod 28459

If the equations are equal, I'm all set. However, they're not equal! I get 18044 != 4085. Am I missing something here?

Your parameters are incorrect.  I don't know how you got them, so I don't know which one is in error; however at least one of them is wrong.

You have $n = 149 \times 191$. The decryption exponent satisfies: $$ed \equiv 1 \pmod{\operatorname{lcm}(p-1, q-1)},$$that is, $7d \equiv 1 \pmod{14060}$; the minimal $d$ that satisfies this is $d = 10043$.

Now, if the hash is 4085 (and we'll assume you aren't doing any padding; for a normal sized RSA modulus, you would, however things are too small in this toy example), and so we have:

$S = 4085^{10043} \bmod 28459 = 5023$

With this value of $S$, we see that the signature verifies:

$5023^7 \bmod 28459 = 4085 = X$

Hence, assuming that you got the modulus, exponent and the hash correct, this is the correct value for the signature, not the value you have listed.


Why is PerfectForwardSecrecy considered OK, when it has same defects as salt-less password hashing? PFS suites suffer from the same defects as any other salt-less password hashing scheme.
Why is everyone promoting Perfect Forward Secrecy (PFS) ciphersuites so fiercely?

Namely, when the group/hash weakens, then the attacker can invests into a massive pre-computation, after which individual connections/hashes can be broken with minimal additional cost. This property allows the big players to amortize the cost of the massive pre-computation over the massive ammount of cracked connections. Consequentially, it promotes mass snooping over targetted attacks.

This question is motivated by the WeakDH/LogJam paper.

EDIT, thanks @steffen-ullrich, It does not make sense to include the salt in "the secret", so the DHE equivalent of salt-less is "everyone uses the (few) same groups".

Salt-less password hashing is only a problem since the amount of passwords actually used in practice is comparably small and also not evenly distributed. Thus it is both in terms of time and memory possible to generate a table with pre-computed hashes and then check the salt-less hashes against this table to reverse the hash. The protection against this are thus salts (increase of time and memory needed for pre-computation) and slow hashes (increase of time).

But, this pre-computing will no longer be feasible if the choice of passwords is not biased against "few" often chosen passwords but if instead there would be a huge amount of possible passwords and none of these would be more likely than the other. It would simply not be practically possible in terms of time and memory to pre-compute and store the hash for all possible passwords. And that's exact the case you have with PFS - it is simply impossible to pre-compute even a relevant small part of all the possible values.


Using an alternative to shamir's secret sharing I was wondering about the following as an alternative to secret sharing(shamir): Assuming that in order to gain access to some theoretical system, we'd be saving secrets on the system and we will monitor all the access attempts, in the following way: Every participant will get a different "secret", and the system will check if the conditions are valid.

For instance: If 3 out of 5 participants from a level 1, or one from level 1 and one from level 2 and similar.

Cryptographically speaking, what are the disadvantages of it? Isn't it a simpler way instead of shamirs secret sharing?

It would help me the most if you could explain it to me mathematically, so I can understand the how and why to better understand the words.

Thank you for helping me understand it better.

Many problems (if not all) in cryptography can be made "trivial" if you have a mutually trusted third party. The argument is something along the lines of:

Multi-party Computation can describe many (if not all) primitives within Cryptography as jointly computing some functionality
MPC is made trivial in the presence of a mutually trusted third party (this is the basis for the "ideal vs. real" proof strategy)
If given a mutually trusted third party, one can securely implement any function which can be implemented using Multi-Party Computation

Implementing access control as you describe is simply implementing access control with a mutually trusted third party.
If you believe this exists in your situation then you can gain efficiency by using it.
But if you are "wrong", and someone manages to corrupt your server, you "lose everything".

Note that this is somewhat the case for secret sharing already.
Generally secret sharing schemes can be written as two functions: $\mathsf{MakeShares}$ and $\mathsf{Reconstruct}$.
If a server which is running the $\mathsf{Reconstruct}$ protocol is compromised during reconstruction, you "lose everything" (under naive Shamir's secret sharing).

You're (essentially) suggesting implementing $\mathsf{Reconstruct}$ with a stateful trusted third party. You could even make this explicit by having your server first run Shamir's secret sharing on the secret, then "renaming" the Shamir's shares using some arbitrary encoding (which you "store" in a table on the Server to be able to undo later).
But as your solution requires the state for correct reconstruction, if your server is ever compromised, you "lose everything" immediately.

Another application your algorithm can't replace Shamir's in is when the protocol participants don't trust eachother.
Someone has to "have all the shares" to be able to implement the access control, and if there's no natural candidate then your protocol doesn't work, but Shamir's still does.

That all being said, for implementing access control where all participants are part of the same organization, you could use non-cryptographic techniques (such as yours) due to the presence of a mutually trusted third party.


How many rounds is needed to implementing Schnorr Non-Interactive zero-knowledge protocol We can use Fiat-Shamir heuristic to replace 3-move Schnorr's protocol with 1-move non-interactive protocol.

When I implement this non-interactive protocol( ref. https://en.wikipedia.org/wiki/Fiat%E2%80%93Shamir_heuristic): That is

Let $G$ be a cyclic group with order $q$.

Peggy needs to prove that she knows $x$ which is the discrete logarithm of $y =g^x$ to a fixed base $g$.

She randomly chooses an element $v \in [1,q-1]$ and computes $t = g^v$.
She computes $c = H(g,y,t)$, where $H$ is a cryptographic hash function (implementing random oracle).
She computes $r = v-cx \pmod q$. The proof is the pair $(t,r)$.
Anyone can check this proof by $t = g^r \cdot y^c$.

My question is that:

Assume that Peggy is prover and Victor is verifier.
Can Peggy send $y =g^x$ and a proof $(t,r)$ in the same round?

Or it should be divided it into two rounds:

The first round is that Peggy sends $y=g^x$ to Victor.
The second round is that a proof $(t,r)$ to Victor.

Does it arise any risk if we combine two rounds?

Thanks

No, sending both parts of the proof together does not create any additional risk.

Notice that at the end of the protocol, Victor knows the same set of values, regardless of whether it has been split into two rounds or not. So whatever he would be able to achieve in "one-round" version, he can still achieve after the second round of the two phase protocol.


Cryptography elements needed for a story Note: following Maarten Bodewes's answer, I edited this post to make it clearer.
I'm writing something partly driven by the need to crack a few encrypted files.
This is what needs to happen in the story:
There are two parties involved that are trying to crack them, party A and party B. Party A has had them for four years, and despite all attempts, they failed. Party B got the files later on and managed to crack them in less than two months of non-stop trying.
Party A has available state-of the-art tech, but party B are the good guys and this is a sci-fi story, so they have far, far better tech that nobody else has. The details of the technology aren't relevant to the story so I don't need to establish them.
Party B will eventually succeed; still, to keep a modicum of suspense up, it must still be possible for them to fail. By this I don't mean that something throws a spanner in their works; I mean that their decryption attempt, however more advanced than party B's, isn't guaranteed to work. In other words, party B can't just sit and wait until whatever they're doing is done knowing that at that point they will have the decrypted file.
This is what I need:

An algorithm such that, if you encrypt a file with it using a high-entropy password, is beyond any brute-force attempts using known methods and tech. (This is why party A fails.) I understand that AES-256 might be what I'm looking for.
An approach that will allow party B to succeed nonetheless. The fact that party B has much faster computers available than anyone on Earth is central to the story so you can assume that. However, if brute-forcing these files required ridiculous amounts of energy or other very unrealistic things, I'm not prepared to claim party B has any of that. Other approaches or situations that would give party B an edge—such knowing what algorithm was used, being able to guess details about the password, or knowing about possible key files—are certainly options I would consider. If quantum computers could plausibly break AES, that's another option I would consider because it's not too far-fetched for party B to have them. I just don't know if QC could actually do that.

Though quantum computers fit the requirements, I'm not sure they are the best option. A general purpose quantum computer capable of attacking modern encryption (RSA, AES) would have serious ramifications on society. It's not only applicable to this one cipher you are breaking.
Does it have to be the superior computing resources which gives the good guys the edge? Because I can think of several plausible storylines where the edge comes from a bright idea.
Option 1: Information about the passphrase.
If the good guys learn something about how the passphrase used to derive the encryption key was chosen they could easily reduce the search space time from millennia to months. For example the passwords are always lines from a book where some of the words are replaced with the first letter. Or something else. One way to learn such a pattern is they crack some other password picked by the same person which was encrypted with weaker encryption. The hero recognizes the pattern in this other password hypothesizes it may be a common method of selecting passwords and starts a brute force dictionary attack on the reduced space.
Option 2: General Cryptanalytic improvement.
Our hero is a master cryptographer. And uses an unknown but plausible cryptanalytic attack on AES to greatly improve speed. This attack could have greatly reduced runtime and it could work on only a fraction of the keys. It could be discovered that a sizeable fraction of keys have some undesired property which makes a superior attack possible (which still requires great computational resources) and they are unsure if the key happens to be such a weak key, they are likely to be able to quantify their success probability in advance.
Option 3: Identifying a flaw in how the data was encrypted
Whoever encrypted the data may have messed up. And accidentally left an easier route to attack it. It could be something like applying error correction after compression before encryption (the flaw in GSM). Or something which more directly leads to an attack like keeping a simple hash of the password. The heroes find this flaw and launch a more efficient brute force based on it.
Option 4: Attack the message not the key
Out heroes don't try to crack the encryption at all. They utilize knowledge of message and compression system used. and find what possible messages would result in desired size. Though if it's only size it's only viable if we had a small collection of possible messages and the attack will be quick. There are attacks on voice for example where we use size and timing to decipher words and phrases without breaking the encryption.


ElGamal in $Z^*_{p^n}$ If $p$ is an odd prime and $n$ natural,it is known that the group $Z^*_{p^n}$ is cyclic.Explain why the selection-choice of the group $Z^*_{{3^{1000}}}$ for the construction of a cryptosystem ElGamal it's not good.

Can anyone explain me why this happens?

The order of $(\mathbf{Z}/3^{1000}\mathbf{Z})^*$ is $\varphi(3^{1000}) = 2\times 3^{999}$, which is a highly composite number, and hence the discrete logarithm in this group is highly vulnerable to the Pohlig-Hellman algorithm.

If you are not familiar with the Pohlig-Hellman algorithm, you can peruse for example Section 2.9 of the book by Hoffstein, Pipher and Silverman. Sadly, the Wikipedia article about it is of quite low quality.


Are there ready-to-use software that can try many decryption techniques on a ciphertext, with no information? Let's say I receive a 1 MB encrypted file, but I get no information about the encryption method, and no password.

The only thing I can guess is that the person probably used a weak encryption method on a text file.

Are there ready-to-use software that will perform automatically a huge number of attacks on the ciphertext, from the simplest methods to the most complicated?

i.e. it would start with ROT13 / Vigenere, frequency analysis, etc., then Hill cipher or other easy-to-crack methods, then RC4 (I read in many places it is considered as weak, but I still don't know if one can easily break it if I don't give any other information than just the ciphertext), etc. and it would stop if some text is found (let's say at least 20% of the words are in a big dictionary)

(I can imagine such software would be used by intelligence agencies, etc. because it would speed up decryption.)

The project Cryptool does some if not all of what you want. I have not used it extensively, but it seems quite well documented. Below from the webpage:

CrypTool 1 (CT1) was the first version of CrypTool. It was released in 1998 and allows to experiment with different cryptographic algorithms. CT1 runs under Windows and has two successors: CT2 and JCT.
CrypTool 2 (CT2) supports visual programming and execution of cascades of cryptographic procedures. CT2 contains an especially large number of cryptanalysis methods and also runs under Windows.
JCrypTool (JCT) is platform-independent and runs under Linux, Mac and Windows. One focus are post-quantum (signature) algorithms.
CrypTool-Online (CTO) was released in spring 2009. Here you can try out in a browser (on a PC or a smartphone) different algorithms.

The current version of CrypTool 1 offers numerous classic and modern cryptographic algorithms (encryption and decryption, key generation, secure passwords, authentication, secure protocols, etc.)

Visualization of several algorithms (Caesar, Enigma, RSA, Diffie-Hellman, digital signatures, AES, etc.)

Cryptanalysis of several algorithms (Vigenère, RSA, AES, etc.)

Cryptanalytical measurement methods (entropy, n-grams, autocorrelation, etc.)

Related auxiliary methods (primality tests, factorization, base64 encoding, etc.)

Number theory tutorial

Comprehensive online help


Property of a good cipher system In the "Introduction to Cryptography: With Coding Theory" by Trappe and Washington, in the chapter about DES algorithm the authors say that:

  "In a good cipher system, each bit of the ciphertext should depend on
  all bits of the plaintext"

Since it's not said why, are you able to explain it to me ?
Thanks

"In a good cipher system, each bit of the ciphertext should depend on all bits of the plaintext"

This property is also called the "avalanche effect" and is usually an explicit design guidance when designing novel block ciphers whereby flipping any input bit gives about a 50% chance to also flipping all output bits, ensuring maximal dependence of all outputs bits on all input bits.

The standard (formal) security definition of a block cipher is that of a pseudo-random permutation where an efficient, probabilistic adversary has to distinguish whether they're looking at a fully random permutation (where each unique requests gets a random previously unseed response sampled on request) or at the keyed permutation with an unknown key.

It is widely believed that modern ciphers like AES satisfy the above definition.

Now if not every bit of the output depends on the input, you can find two distinct inputs that give related outputs, something that wouldn't happen for an ideal permutation and allowing an adversary to find out whether they're looking at the non-ideal permutation.

The practical application could for example be a bias in the output where one bit doesn't e.g. depend on the least significant bit of the input. Then when you're using the cipher in counter mode you'd get that bit to be the same twice in a row, leaking information about the plaintext at these points, like with a reused one-time-pad.


Distinguishing attack on stream cipher created from a block cipher in counter mode A block cipher in counter mode creates a key stream by:

$$z_i = E_K(IV || i)$$

Where $IV$ is some chosen initialisation vector (with some length $l$ less that $n$ bits) and $i$ is the binary representation of the number $i$ in $n-l$ bits. The keystream is then $z_1 || z_2 || z_3 || \cdot \cdot \cdot$

How can we distinguish between such a key stream and a truly random bit sequence?

For a truly random stream, since there are $2^n$ possible $n$-bit blocks, we expect a repeated n-bit block after looking at (roughly) the first $2^{n/2}$ blocks, by the birthday paradox argument.

For the stream generated by this block cipher, provided that each input block is distinct (i.e. the counter does not start repeating) , the output blocks are distinct (since the block cipher is a permutation). So choosing the IV length small enough (or indeed taking the whole block for the counter and not using an IV), we are guaranteed that no block is repeated for the first $2^k$ blocks, where $k \leq n$ is the length of the counter.

This way, provided $k$ is large enough, we can distinguish between two such streams by searching for a repeated block.


Is this a typo/error in the Galois/Counter mode specification or have I misunderstood? I've been reading the following document describing Galois Counter Mode:
The Galois/Counter Mode of Operation

On page 7 of the document, the following diagram describes the GHASH function used to authenticate data.  GHASH is defined as GHASH(H, A, C) where H is a 128-bit unsigned integer and A and C are two bit strings representing the authenticated data $A$ and ciphertext $C$.  $m$ and $n$ are used to represent the number of 128 bit blocks of data in $A$ and $C$ respectively.

Equation 4 and 5 look incorrect to me.  Is $C_i$ correct on line 4?  Won't $i$ already be larger than $m$ and thus this won't include the correct blocks of $C$?  Shouldn't this be $C_{i-m}$?

And the fifth equation, is this meant to be $C^{*}_{n}$ and not $C^{*}_{m}$?

Examining the document, it seems that you are correct on both equations. Thus

$$
C_i ~~\textrm{should be}~~C_{i-m},
$$

and

$$
C_m^* ~~\textrm{should be }C_n^*.
$$


Collision-Resistance Hash Function PRF I am trying to solve the following question with an example/proof. The question is from Introduction to Modern Cryptography by Katz and Lindell. Any help would be appreciated.

Hints:

For (a), suppose you had a collision with $\hat{H}$; how could you use that to demonstrate a collision with $H$?  What does that imply?

For (b), could you construct a collision with $\hat{H}$, that is, find two different messages $x_1||x_2$ and $x'_1||x'_2$ with $\hat{H}(x_1||x_2) = \hat{H}(x'_1||x'_2)$?


Can a raw ECDH shared secret be used directly for encryption? If two parties calculate an ECDH shared secret can they (with no security weakness) use this raw value directly as an encryption key, assuming the underlying key and ECDH sizes match?

Also the situation I'm specifically looking at using static ECC keys, not ephemeral ones, but I would also be curious if using the raw ECDH value for encryption may be OK when using ephemeral keys.  I do understand that it is ~trivial to apply a KDF to the ECDH secret but I am evaluating an existing system.  The system uses p256r1 and is using the resulting x-coordinate as the shared secret.

If two parties calculate an ECDH shared secret can they (with no security weakness) use this raw value directly as an encryption key?

If the ECDH curve size is large enough, then yes, there is no immediate security weakness.  It would cause the theoreticians heartburn (as the symmetric key is supposed to be chosen uniformly,  and it isn't in this case), however there is no practical way for an attacker to exploit this.

To give an example: suppose the ECDH is done over P256, and you use the x-coordinate as the shared secret; and you use that shared secret to key AES-256.

Then, the attacker knows that (approximately) half the possible AES-256 keys are impossible (as they cannot be the x-coordinate of a P256 point); however there still are approximately $2^{255}$ possible values the key could be, and it would still be impractical to search over that large of a space.


Encrypted counter as IV in CBC mode encryption using same key I'm currently working with a secure transport protocol that defines the IV to be a counter (incremental nonce) to be encrypted with the same key. This is a followup to a protocol that did not provide any kind of IV.

Could you please describe the possible attack vectors on CBC encryption using this encrypted nonce?

Furthermore, the protocol has the following characteristics:

a MAC is calculated over each encrypted message and verified before decryption (including any parameters send)
session keys are used that are recalculated each time the protocol is initiated
the session is lost when any error is detected in the protocol
the protocol is half duplex, with the attacker having full capabilities on the communication layer, but limited (if any) influence on the sender and receiver
the cipher used is AES with sufficiently random session keys

Would these characteristics alleviate any of the concerns of using an encrypted counter using the same key?

Related question: What are the constraints for an IV using AES in CBC mode?

[EDIT]

Note that for this case the counter and IV are not send or included in the MAC calculation - which seems to be the main issue with the protocol.

Just to be sure we're on the same page, I interpret your question as defining encryption of a string $P_1 P_2 \cdots P_\ell$ with a counter $\mathsf{ctr}$, key $K$, and an $n$-bit blockcipher $E$ as follows:
$$ \mathcal{E}_K(\mathsf{ctr}, P_1P_2\cdots P_\ell) = C_0 C_1 C_2 \cdots C_\ell$$
where $C_0 = E_K(\mathsf{ctr})$, $C_{i+1} = E_K(C_i \oplus P_{i+1})$, and each $P_i$ is an $n$-bit string. (So I'm assuming plaintexts have already been padded as necessary.) I'm assuming the values that will be used for $\mathsf{ctr}$ are determined ahead of time. If this is incorrect, attacks become possible.

The scheme above is secure in the sense of real-or-random security under chosen-plaintext attacks (this is a somewhat stronger condition than semantic security). That is, an adversary cannot distinguish between $\mathcal{E}_K$ and an oracle that given an nonce and an $nm$-bit plaintext returns $(m+1)n$ random bits. This is true as long as $E$ is secure (in the sense of being a pseudo-random permutation), $K$ is random, and the total length of all the ciphertexts encrypted under a given key is much less than $2^{n/2}$ bits (the birthday bound).

Proof sketech. A standard game-hopping security proof might proceed like this:

Change the scheme to use a random permutation $\pi$ in place of $E_K$ (this is reasonable if $E$ is secure and $K$ is random).
Change $\pi$ to a random function $\rho$ (this is reasonable as long as long as the number of queries to $\pi$ is much less than $2^{n/2}$; see the PRP-PRF switching lemma).

As long as no input to $\rho$ is ever repeated, all its outputs are uniformly random and independent. Therefore using the encryption scheme over $\rho$ is indistinguishable from an oracle that outputs random strings, as long as this condition holds. So we need to bound the probability that an input to $\rho$ is repeated.

From here the proof proceeds like the standard CBC security proof, with the caveat that instead of looking for collisions just among the $\rho$ inputs we've already seen, we also need to worry about one of the inputs being equal to a counter value we'll need in the future. (This is where the assumption that counter values are pre-determined comes into play.) Since barring a repeated input, each $C_i$ and therefore each $C_i \oplus P_{i+1}$ is a uniform random value independent of previous queries, the probability that a given $C_i \oplus P_{i+1}$ is equal to a counter value is at most $q / 2^n$, where $q$ is the number of queries the adversary will make (and hence the number of counter values we require).

Using a union bound, the probability that such a collision will ever occur is at most $q^2 M /2^n$, where $Mn$ is the length of the longest plaintext. This probability is negligible as long as $(qM) \ll 2^{n/2}$. And note that $qMn$ is an upper bound for the total number of bits encrypted.

So. The encryption scheme $\mathcal{E}$ is not significantly less secure than CBC with a random IV. The larger question of whether the protocol as a whole is secure as a much more difficult question, and one that I can't answer without knowing more about it (and probably couldn't answer even if I did). But you are authenticating the counter, right? :)


Apple CryptoKit - Understanding its portability I've been playing with Apple's CryptoKit (their effort to make their old CommonCrypto lib more modern and easy to use via Swift, their programming language).

I'm interested to see how portable it is...

They use boxes, similar to libsodium.

Interestingly they only support AES-GCM and ChaChaPoly for authSym, and a handful of curves for Asym (P-256 & Curve25519 being most notable).

Anyway, I'm just trying to decrypt some test data manually (using OpenSSL or whatever) using the raw outputs I've extracted from the debug code I wrote, and whilst I can encrypt and decrypt in Swift I'd love to test this elsewhere to check portability.

This is AES-GCM-256,

Key Base64: nUSfBvhz2HSSo575uCOK3ewTibD7jXsp6f2aPfP3dTo=

Nonce:m2A7P8c5r7wmczXD

Ciphertext:uEU5otv81AMjG9wCxg==

Tag:w1lj7fumWRQ7hdJCXwkqCw==

Can anyone help me use OpenSSL on command line to decrypt?

I've been trying OpenSSL enc aes-gcm-256 -a -d without getting it working (-a for base64, -d for decrypt)...

OpenSSL cli doesn't support authenticated encryption modes like CCM and GCM. The reason behind that is the lack of security if the IV/nonce is reused. Using OpenSSL cli, IV management totally rely on the user, who tend to make mistakes... In order to avoid catastrophic failures, they simply decided to not allow AEAD.

I guess the easiest way is to do a simple Python script. I would advice PyCryptodome, you can even find an example which suite your needs.


is coin-tossing an instance of secure computation (MPC, 2PC, etc.)? Coin-tossing protocol is defined as a protocol between at least 2 non-trusting parties that allows them to obtain an unbias random bit in such a way that no involved party can influence the output. Hence, does it pertains to the notion of secure computation?

Yes it does.
Here is a brief summary from https://eprint.iacr.org/2009/214.pdf:
When a majority of the parties are honest, efficient and completely fair coin-flipping protocols are known as a special case of secure multiparty computation with an honest majority (assuming a broadcast channel) as in

M. Ben-Or, S. Goldwasser, and A. Wigderson Completeness theorems for non-cryptographic fault-tolerant distributed computation. STOC 1988.

When an honest majority is not available, and in particular when there
are only two parties, the situation is more complex. Blum’s two-party coin-flipping protocol from 1982

M. Blum. Coin flipping by telephone - A protocol for solving impossible problems. 25th IEEE Computer Society International Conference, 1982.

guarantees that the output of the honest party is unbiased only if the malicious party does not abort prematurely (note that the malicious party can decide to abort after learning the result of the coin
flip).
This satisfies a rather weak notion of fairness in which once the malicious party is labeled as a “cheater” the honest party is allowed to halt without outputting any value. Blum’s protocol relies on any one-way function and Impagliazzo and Luby (see linked paper) later on showed that one-way functions are in fact essential even for such a seemingly weak notion.


If the order of g is a prime number, is Pollard-rho the best? If the bit size is 128 bits, I know that BSGS is not possible due to memory issues.

I know that the complexity of Pollard-rho for 128 bits is 2^64.

and I know that it is not possible to do 2 ^ 64 operations on a typical computer.

Is there any other way? do solve 128bit ECDLP when ord(G)=prime number

Yes, Pollard-rho is the best algorithm known for solving hard instances of ECDLP (those where the generator is of prime order).

The current (public) record seems to be order $2^{117.35}$ for sect113r2 by Daniel J. Bernstein, Susanne Engels, Tanja Lange, Ruben Niederhagen, Christof Paar,  Peter Schwabe and Ralf Zimmermann in Faster elliptic-curve discrete logarithms on FPGAs (eprint, 2016). Notice that this is for a curve over a binary field, and prime fields are noticeably harder at equal size (because cary-less arithmetic is cheaper).


How does generating random numbers "remove entropy from your system"? In a previous question, I quoted the --gen-random entry in the GPG Man Pages. At the end it says:

  PLEASE, don’t use this command unless you know what you are doing; it may remove precious entropy from the system!

How does that work? I understand entropy to be the "randomness" of a system (i.e. the amount of information it contains).  How can generating random numbers steal randomness from your computer such that it noticeably hurts the computer's ability to perform cryptologic operations in the future?

I'm no mathematician, so plain english answers would be appreciated.

As others have stated, the problem is the entropy pool. The operating system maintains a count of entropy in the pool that it decreases every time random numbers are generated from it and increases when it adds some timing or other information that is assumed to have entropy.

Requesting numbers does not actually remove randomness from the pool in practice, unless it is severely broken. The state will still be unknown and the numbers received cannot be used to derive future numbers.

However, the /dev/random interface on Linux blocks if the count is zero. This means that requesting a lot of random numbers from the OS may starve any programs that use the blocking interface. This is the practical issue with using the command, since especially on server machines that have no input devices the entropy count can be slow to increase.

The usual advice is to use the non-blocking pool in most applications so that they cannot get starved, but not every program out there does that.


Computational complexity of RSA What's the computational complexity or RSA? One can assume it's O(prime length^2) it you consider multiplication by column, but speed tests slightly differ on slow operations with private key and differ a lot on public key. Why?

> openssl speed rsa1024 rsa2048 rsa4096

                  sign    verify    sign/s verify/s
rsa 1024 bits 0.002544s 0.000124s    393.1   8049.2
rsa 2048 bits 0.017023s 0.000467s     58.7   2140.7
rsa 4096 bits 0.121189s 0.001824s      8.3    548.2

A more concrete answer for the data observed from OpenSSL:

naive bignum multiplication is $O(n^2)$ and so is modular multiplication (which is what is actually needed here). However OpenSSL (for these sizes) uses Karatsuba multiplication which lowers this to roughly $O(n^{1.6})$ (thanks frgieu) and also Montgomery reduction which is only a constant factor.
for publickey the number of multiplications is fixed (and small) so the total operation is the same big-O as one multiplication.
for privatekey the number of multiplications also scales with $n$ giving a total roughly $O(n^{2.6})$ . OpenSSL also uses CRT which halves the size of the multiplications and doubles their number (plus wrap-up and sanity check), and windowing which reduces the number of multiplications by about 1/3, but those are both constant factors and ignored for big-O.

OpenSSL doesn't 1.1.1 does implement the imprecisely named 'multi-prime' form of PKCS1, which changes the privatekey benefit from CRT, but to get speed results for it you must specify -primes N and a sufficiently large (total) size.


Proving RSA is a permutation I am trying to prove that RSA is a permutation. All I can find is places where it is stated that it is a permutation because the function is bijective. I know that it is, but would like to see a detailed proof.

For clarity, we have $N = p \cdot q$, where $p$ and $q$ are prime and $e$ such that $1 = \gcd(e, (p-1)\cdot(q-1))$. We want to show that $f(x) = x^e \pmod N$ is a permutation. I am thinking we must use Fermat's little theorem somewhere but I cannot complete a detailed proof myself.

First let's clarify notations. $f(x)=x^e \pmod N$ is non-standard, hesitating between

$f(x)\equiv x^e\pmod N$ , meaning $N$ divides $x^e-f(x)$
$f(x)=x^e\bmod N$ , additionally specifying that $0\le f(x)<N$.

What's meant in RSA encryption is the later.

A permutation  of a set is a bijection from that set to that same set. Any injective function from a finite set to a set with the same cardinality (number of elements) is a bijection. Thus we only need to prove that for any integers $x$ and $y$ in $[0,N)$ , if $f(x)=f(y)$ , then $x=y$. We do that in the following.

We assume $f(x)=f(y)$. By definition of $f$ that means $(x^e\bmod N)=(y^e\bmod N)$. That implies $N$ divides $x^e-y^e$. That implies any prime factor $p$ of $N$ divides $x^e-y^e$, that is $x^e\equiv y^e\pmod p$.

It is hypothesized $1=\gcd(e,(p-1)\cdot(q-1))$. Therefore $e$ and $p-1$ are coprime, the multiplicative inverse of $e$ in $\mathbb Z_{p-1}$ is well defined, and there exists a positive integer $d_p$ and a non-negative integer $k$ such that $e\cdot d_p=1+k\cdot(p-1)$.

Raising $x^e\equiv y^e\pmod p$ to that power $d_p$, we get that $(x^e)^{d_p}\equiv (y^e)^{d_p}\pmod p$; thus $x^{e\cdot d_p}\equiv y^{e\cdot d_p}\pmod p$; thus $x^{1+k\cdot(p-1)}\equiv y^{1+k\cdot(p-1)}\pmod p$.

For any prime $p$ and any integer $x$, Fermat's little theorem states that $x^p\equiv x\pmod p$. That allows to prove by induction on $k$ that for any non-negative integer $k$, $x^{1+k\cdot(p-1)}\equiv x\pmod p$.

Thus $x^{1+k\cdot(p-1)}\equiv y^{1+k\cdot(p-1)}\pmod p$ becomes $x\equiv y\pmod p$, that is $p$ divides $x-y$. Similarly, $q$ divides $x-y$.

Here we hypothesize that $p\ne q$ (which is unstated in the question). If distinct primes divide an integer, their product does. It follows that $p\cdot q$ divides $x-y$, that is $x\equiv y\pmod N$, that is $x=y$ given that both belong to the set $[0,N)$; that completes our proof.

Note: the hypothesis $p\ne q$ is necessary. Illustration: $p=q=e=3$, $f(3)=f(6)$.