How multiplicative property of RSA can be exploited It is known that RSA has the multiplicative property

$E(m_1) \cdot E(m_2) = E(m_1 \cdot m_2)$

because

$m_1^e \cdot m_2^e = (m_1 \cdot m_2)^e  \pmod n$

But how can this property be used to break the RSA system?

What are the attacks that use this property?

Using this property, you can't fully break RSA (meaning you can't get the private key).

However there are a few attacks.

If you're using RSA for public-key encryption, there's an adaptive chosen ciphertext attack. Suppose you want to decrypt $c$ and A is decrypting everything but $c$ for you. Now you can chose your $c_1=x^e*c$ with $x\in Z_n^*$. Now you you send $c_1$ to A, he decrypts this. Now you'll have $m_1=c_1^d=c^d*(x^e)^d=m*x$ $(mod$ $n)$, now you simply compute $m=m_1*x^{-1}$ $(mod$ $n)$ and decrypted an arbitrary ciphertext
If you're using RSA for digital signature with message recovery you can basically mount the same attack as above, by basically using blind signatures so you can get arbitrary data signed. (If not using proper methods to protect)


Explanation of openssl ciphersuites I'm looking for a detailed explanation of the ciphersuites available in openssl.

openssl already offers the ciphers command which can be used to output, for example, the following:

$ openssl ciphers -v "HIGH,-SHA,-AES256"
DH-DSS-AES128-GCM-SHA256 TLSv1.2 Kx=DH/DSS   Au=DH   Enc=AESGCM(128) Mac=AEAD
DHE-DSS-AES128-GCM-SHA256 TLSv1.2 Kx=DH       Au=DSS  Enc=AESGCM(128) Mac=AEAD
DH-RSA-AES128-GCM-SHA256 TLSv1.2 Kx=DH/RSA   Au=DH   Enc=AESGCM(128) Mac=AEAD
DHE-RSA-AES128-GCM-SHA256 TLSv1.2 Kx=DH       Au=RSA  Enc=AESGCM(128) Mac=AEAD
DHE-RSA-AES128-SHA256   TLSv1.2 Kx=DH       Au=RSA  Enc=AES(128)  Mac=SHA256
DHE-DSS-AES128-SHA256   TLSv1.2 Kx=DH       Au=DSS  Enc=AES(128)  Mac=SHA256
DH-RSA-AES128-SHA256    TLSv1.2 Kx=DH/RSA   Au=DH   Enc=AES(128)  Mac=SHA256
DH-DSS-AES128-SHA256    TLSv1.2 Kx=DH/DSS   Au=DH   Enc=AES(128)  Mac=SHA256
ADH-AES128-GCM-SHA256   TLSv1.2 Kx=DH       Au=None Enc=AESGCM(128) Mac=AEAD
ADH-AES128-SHA256       TLSv1.2 Kx=DH       Au=None Enc=AES(128)  Mac=SHA256
AES128-GCM-SHA256       TLSv1.2 Kx=RSA      Au=RSA  Enc=AESGCM(128) Mac=AEAD
AES128-SHA256           TLSv1.2 Kx=RSA      Au=RSA  Enc=AES(128)  Mac=SHA256

It seems that ADH stands for "Anonymous Diffie-Hellman" but also implies specific groups and bit sizes.

I am interested in detailed explanations of what all the abbreviations are and generally which of these ciphersuites are considered secure.

Specifically:

What is ADH? Where is it standardized?
The listed MAC algorithms are hash functions. Is it using HMAC?
What does "Au" mean?

What is ADH? Where is it standardized?

ADH stands for Anonymous Diffie-Hellman, ie unauthenticated Diffie-Hellman, also called "opportunistic encryption". It has been part of the SSL/TLS standards at least since SSLv3. It was also extended to ECDHE in RFC4492.

  The listed MAC algorithms are hash functions. Is it using HMAC?

Yes indeed.

  What does "Au" mean?

It most likely means something like Authentication mechanism. This clearly covers with the given ciphersuites as ADH suites have none there, RSA key-transport and DHE+RSA suites have RSA there (server authenticated via RSA signature), DHE+DSS suites have DSS there (server authenticated via DSA) and suites using static DH ones have DH there (server authenticated via his static DH public key).


How secure is a 128 bit ideal substitution cipher A 128 bit ideal substitution block cipher substitutes 128 bit blocks with randomly assigned 128 bit blocks using a key table.

How secure is this type of algorithm?

Is this practical?

Thanks!

A block cipher is a keyed permutation. The number of possible permutations is quite high. There are of course $2^{128}$ ways of mapping a single 128 bit plaintext block to a 128 bit ciphertext block. Actually, the number of ways of mapping all possible plaintext blocks to each and every ciphertext blocks is $2^n!$ where $n$ is the block size in bits.

The key is used to choose one of these possible permutations. That means that your key table would have more than $10^{10.000.000.000.000.000.000.000.000.000.000.000.000.000}$ entries. That's a gargantuan number; there are a lots of ways how to map $2^{128}$ values to $2^{128}$ after all.

Is a 128 bit ideal block cipher secure? Sure, it's ideal - so it is secure, by definition, for any block size.

Is a 128 bit ideal block cipher practical? No, the key space is ever so slightly too large for life.

An ideal block cipher is possible up to a block size of about 4 bits, however that block size is way too small to be usable in any block cipher mode of operation (such as CBC) for any kind of data. It's therefore a theoretical construction rather than a practical construction.


How to show that Cx is a commitment to a integer of length lm With reference to Jan Camenisch and Anna Lysyanskaya's paper A Signature Scheme with Efficient Protocols, in proceedings of SCN 2002, I need some help to understand How to verify that $C_x$ is a commitment to an integer of length $l_m$.
$$C_x = g^x * h^r$$, where $x$ is the secret and  $r$ is the randomness; $g$ and $h$ are known parameters

You want to prove knowledge of an opening $(x,r)$ to a Pedersen commitment, such that $x$ belongs to the range $[0,2^{l_m}]$. Such a proof is called a range proofs, and many methods exist, using bit-decomposition (commit to $x$ bit by bit, prove that the sum of the $x_i\cdot 2^i$ is indeed $x$, and prove that each committed value is a bit) or square decomposition techniques over hidden order groups. I discussed some of these methods in several answers, see here and here. The latest state-of-the-art method for range proofs is Bulletproof, which achieves relatively impressive efficiency guarantees, to the point that it's actually used in several real-world applications (e.g. the cryptocurrencies Monero and Mimblewimble, among others).


Is symmetric encryption with a key containing the userId passes as authentication? The scenario:

There is a web application where ownership check is time expensive so during the development all users were able to access all other user's objects (let's say apples) by changing the ids in the REST urls.

The user is authenticated by issuing a signed (not encrypted) JWT to the client in which one of the claims is a userId.

There was an initial attempt to make proper ownership checks on the server, but since it was very slow now everyone is looking for workarounds.

The team has made a decision - which I was against - to implement a following solution instead:

Instead of sending the user the ids of his apples, the user receives the ids encrypted symmetrically on the server. This should prevent the user to randomly guess ids (ids are autoincremented numbers).
When the user requests a specific apple, he requests it with the encrypted id he received, and the server decrypts the id and fetches the resource by it.
To prevent one user to reuse other users' ids, the encryption and decryption is done with a secret key that has the userId coming from the JWT token concatenated to it. This way you have to have a matching JWT token for your token to be decryptable.
The encryption is done by Jasypt's BasicBinaryEncryptor, where the plaintext id is converted to bytes and the resulting bytes are base64 encoded. Decryption is the same backwards.

My problem:

I do not have the knowledge to properly argue against this, apart from reciting things like "do not invent your own security", but this seems like a horrible disaster waiting to happen.

The JWT tokens for signed claims part is something that does not seem too fishy to me. They are stored in localstorage, the signature algorithm is set by the server, the secret is very long, there is expiration in them.

What seems problematic to me is that the cyphertext is not signed so if the user can forge the request somehow he still has access to all other user data.

Is it possible to somehow forge a request here? For example by messing around with the bits and see if the server throws an error (or what kind of error).

I'm looking for easy-to-understand reasons on why it is a bad idea to do this to present a solid argument to my colleagues (or be convinced that it is not).

First and foremost: Stop using JWT for sessions and why your cannot hack it into working.

  I do not have the knowledge to properly argue against this, apart from reciting things like "do not invent your own security", but this seems like a horrible disaster waiting to happen.

So your primary question is how to convince your coworkers that this is a bad scheme?

If telling them they shouldn't be writing their own cryptography isn't enough, tell them instead how their custom solution is more expensive, complex and less secure than the alternatives. See below for alternatives.

  What seems problematic to me is that the ciphertext is not signed so if the user can forge the request somehow he still has access to all other user data.

Signatures are asymmetric (expensive) and are (generally) larger than symmetric MACs. You'll be better off using symmetric solutions instead. Similarly encrypting is not authenticating and copy-pasting a ciphertext is not demonstrating an authority.

  Is it possible to somehow forge a request here? For example by messing around with the bits and see if the server throws an error (or what kind of error).

If these object IDs are encrypted using CTR mode, then incrementing the ciphertext still gives you the next ID. If instead the object ID is encrypted using a PRP, then you can guess a random ID in $2^{b/2}/n$ guesses assuming a $b$-bit block-size and $n$ valid IDs exist. If you have 1 billion IDs, then this is only $18446744 \approx 2^{24}$ attempts. (can someone verify?)

Cryptographically this is weak. In practice you should have rate limiting and should slow down users who make repeated attempts for invalid IDs so this might not be too bad, but with only $18$ million guesses for $1$ billion possibilities this really depends on how sensitive you think these apples are. If they have no value, no one will try. If they are sensitive, it'll be only a matter of time.

  I'm looking for easy-to-understand reasons on why it is a bad idea to do this to present a solid argument to my colleagues (or be convinced that it is not).

It is custom, slow, expensive, unverified and unnecessary!

Alternative 1: per-user isolated sets of apples

If apples cannot be shared between users then only display the ID relative to the user in question. I.e. If Alice has $3$ apples, they are $0$, $1$, and $2$. If Bob has $2$ apples, they are $0$, and $1$.

Additionally this can be bound to HTTP cookies such that malicious JavaScript cannot exfiltrate the JWT stored in LocalStorage. Better yet, this doesn't rely on JavaScript at all.

Alternative 2: capability-based sharing of apples

If apples can be shared between users, look into capabilities and macaroons.

A capability is an unforgeable, unguessable and communicable token of authority. You can only acquire a capability from someone who already holds it. Capabilities are stronger than cryptography, but they rely on trusted systems. Using keys-as-caps, cryptography can emulate a weaker form of capabilities based on knowledge (not possession). Macaroons are a cryptographic capability relying only on a secure keyed-hash (HMAC). No expensive asymmetric encryption or signatures.

Example macaroon (approximate example, see the paper for better definitions):

$$\begin{aligned}
s &= \text{new_macaroon}(\text{server_secret}, \text{nonce})\\
  &= (nonce, \text{HMAC}(\text{server_secret}, n))\\
a &= \text{add_caveat}(\text{authority}, \text{caveat})\\
  &= (\text{authority}_0, \text{authority}_{n-1}, \dots, 0 \| \text{caveat}, \text{HMAC}(\text{authority}_n, 0 \| \text{caveat})\\
i &= \text{invoke}(\text{authority}, \text{message})\\
  &= (\text{authority}_0, \text{authority}_{n-1}, \dots, 1 \| \text{message},\text{HMAC}(\text{authority}_n, 1 \| \text{message})
\end{aligned}$$

$s$ is an unrestricted credential. It is always valid. Technically the server could revoke it by the $nonce$, but this is not assumed. $a$ has additional caveats added. I.e. To expire the credential after some time, or to limit the objects or functions that may be reached or called. And finally $i$ invokes the authority to send some message to the server. If all caveats evaluate without failure, then the message is approved and evaluated.

Any time the un-invoked authority is shared we must use a secure transport to prevent a MiTM from learning the secret key. When invoking we reveal only public information and a proof binding the authority to the message. Conveniently this also makes CSRF tokens obsolete, but it does not prevent replays as-is.

Notice that macaroons do not assume the system has "users" or that revocation or expiration are required. The server is responsible to selecting the initial caveats, and the user may add any caveats they want when they share the credential. If Alice shares her credential with Bob to access an $\text{apple}_5$, then Bob can access only this apple and not any of Alice' other apples. Nor does this credential assume signatures.

Signatures only make sense when a large (or unknown) audience needs to verify the integrity offline. Your server is the only one producing and verifying these credentials correct? If your users need to authorize a third party service to perform some actions on their behalf, they share a provisioned credential with any caveats they want. Additionally, the user can include a special kind of caveat that pings back to their own server to ask for permission to perform some action. This enables the user to revoke the capabilities.

The users can add caveats and distribute them offline without interacting with your servers.


Is there a quantum-safe time lock? Most successive squaring time lock puzzles I've seen appear to be broken by Shor's algorithm. Is there another practical and efficient time lock protocol that is not broken by Shor's algorithm? If not, what will I need to make one?
time lock requirements
What I mean as a time lock puzzle is something that balances being cheap to crack, but requires a lot of time to crack. This is achievable by requiring that a solver computes a long, non-parallelizable function. However, it has to be very cheap (less than a minute of modern CPU time) to make. In order to encrypt something with the puzzle, the creator probably needs to know the outcome of the puzzle when creating it. If there is a way to encrypt something with out knowing the solution (via asymmetric encryption) that will also be acceptable.
known research
I have read that as of 2014 there were no (at least practical) alternatives to successive squaring. A lot has happened since then. One more recent creation, verifiable delay functions(VDF), are very similar to time lock puzzles but has a different purpose. It may be worth looking in to to see if VDFs can be converted to time locks.

A similar construct to a time-lock puzzle is a verifiable delay function. They have a similar notion of "inherent sequentially". They have an unrelated "public verifiability" property which you do not care about.

Boneh et al. build verifiable delay function from a construct called ``Incrementally Verifiable Computation'', which they can instantiate from certain SNARKs/SNARGs. There exist lattice based SNARGS, which I imagine are post-quantum.

I have not checked if all of these notions line up to directly give someone post-quantum VDFs (and therefore post-quantum Time-Lock Puzzles), but this seems like an excellent candidate for what you're looking for.


how to use these hash functions in python? In this article https://www.mdpi.com/2073-8994/12/10/1687/htm, specifically in the section 4.1 of the initialization phase,the following cryptographic hash functions have been chosen:
\begin{align}
h_1&:   \mathbb G\to\mathbb Z_q^*\\
h_2&:  \{0,1\}^*\times\{0,1\}^*\times\mathbb G\to\mathbb Z_q^*\\
h_3&:  \{0,1\}^*\to\mathbb Z_q^*
\end{align}
where G is an additive group with order q.
Can anyone explain to me what's the meaning of their notations and how to use them for example in SHA algortihm? Or maybe give me a simple example with real inputs?

The $q$ is defined as the order of the ECC is used. Therefore we need to use a hash function that has at least 256-bit output since the secure curves use at least around that. Let choose SHA256.

$h_1 : \mathbb G\to\mathbb Z_q^*$
Given $g \in \mathbb G$ represent it in binary and hash with SHA256. Note that the $Z_q^*$ means $Z_q - \{0\}$ so you need to discard if the hash value is zero. Wait, if you luckily hit zero, publish a short paper.

$h_2:  \{0,1\}^*\times\{0,1\}^*\times\mathbb G\to\mathbb Z_q^*$
The $\times$ is used as the function takes input from 3 spaces. You can concatenate the inputs from them, however, two distinct delimiters are required since the first two spaces are not bound (Kleine star). This unboundedness can cause simple collisions, like $aab||ba$ and $aa||bba$ are two distinct inputs from two different input spaces, however, both have the same hash, and this is a collision since the inputs are from different spaces.
You may need to use 3 inputs like $$String1||\text{delimeter1} || String2 || \text{delimeter1} || g$$ where $String1$ from the first space, $String2$ from the second space and $g \in \mathbb G$.

$h_3:  \{0,1\}^*\to\mathbb Z_q^*$
Nothing special from the above cases.

They say you need 3 distinct hash functions. It is not clear that you may benefit from domain separation like below.
\begin{align}
h_1(x)&:  \operatorname{SHA256}(\texttt{"Hash-one"}||x)\\
h_2(x)&:  \operatorname{SHA256}(\texttt{"Hash-two"}||x)\\
h_3(x)&:  \operatorname{SHA256}(\texttt{"Hash-threee"}||x)
\end{align}
If it is not this case you may need 3 different hash functions.
Also note that, if the $q > 256$ you cannot use SHA256 directly then use SHA512, Blake2, etc. and trim the result whenever needed.


Why not use OAEP for signatures? There seems to be a distinct lack of implementations of RSA signatures using OAEP to pad the digest. Other than the old, funky, padding schemes, it's PSS all the way.

PSS seems to have the whiff of patents about it. OAEP, on the other hand, is accompanied by long diversions about its theoretical safety presented as claim and counterclaim.

Is it, in principle, very wrong to use OAEP with RSA for signatures? How wrong? As bad as those first generation padding schemes? Has the stench of patents lifted from PSS? If there's one thing more confusing than the underlying maths, it's the organisation of crypto standards: is this combination actually rather common, detailed well in a PKCS or RFC, and I've just missed it?

One good reason not to use RSAES-OAEP for signature is because as it stands, it can't do signature! RSAES-OAEP performs encryption of a message (of limited length) with optional label into a cryptogram, and decryption thereof. There is no way to turn some RSAES-OAEP black box into a signing machine.

OK, we could define an RSA signature scheme with a signature procedure that

hashes the message $M$ to be signed into $H$
applies OAEP padding on $H$ rather than $M$, with lHash (the hash of) some fixed constant, perhaps the 01 changed to some other non-zero byte, and as usual seed randomness as wide as the hash, and PS just enough zeroes to fill-in
applies the RSA private key function $x\to x^d\bmod N$

and the signature verification procedure matching that. I do not know that this was studied, or that we have a security reduction proving that if this signature scheme can be broken, then we can can break one of its components. I won't hazard into trying to guess in what framework such reduction could be made, and how quantitative it could be.

And why bother? The above signature scheme has no clear advantage over RSASSA-PSS, which has security reductions[*], is accepted by security authorities, and widely used. In particular, there is no grounds for fear about patents when using PSS signature, and there seldom was any (in my non-lawyer opinion and from the relative comfort of Europe on the legal uncertainty standpoint); quoting PKCS#1 v2.2 appendix D on intellectual property considerations:

  The PSS signature scheme is described in U.S. Patent 6,266,771, which expired on July 24, 2009, and U.S. Patent 7,036,014, which expired on April 25, 2010, and was held by the University of California. The PSS signature scheme is specified in IEEE P1363a-2004. Prior to the finalization of this standard, the University of California provided a letter to the IEEE P1363 working group stating that if the PSS signature scheme is included in an IEEE standard, “the University of California will, when that standard is
  adopted, FREELY license any conforming implementation of PSS as a technique for achieving a digital signature with appendix”.

[*] I vaguely recall debate about if PSS security reductions are quantitatively satisfactory for practically used modulus size and other parameters, but fail to locate a source.


Secure Key exchange using javacard applet I am working on a javacard applet project where i need...

Secure communication between two applets let say there is applet A
and applet B. Let say both applet has their own RSA key pairs.
Now I want to perform Diffie-Hellman key exchange between these applet.So
that both applet can talk securely.

How to perform above mentioned functionality if anyone can also suggest other than this where two applets can communicate by using asymmetric crypto.

Any help on this topic will be highly appreciated.

Both RSA and DH have a similarity which is the Modulus Exponential (modexp) function (RSA encrypt/decrypt function). Since both RSA and DH uses the same modexp function, you can make full use of the Cipher for ALG_RSA_NOPAD in JavaCard's crypto API.

I have sat down and taken time to adapt the RSA crypto functions for traditional non-ECC type of DH functions and you can find the open source applet code here (https://github.com/ASKGLab/DHApplet/blob/master/src/dhapplet/DH.java).

I have not yet done up the APDU commands to create a full fledge demo but I guess if you study the DH.java codes, it should be more than enough to give you a head start. I have included a ton of commends in the source code on how to adapt it to different scenarios and the thought process as well when designing the entire DH class and it's significance.


Hash-based signature scheme XMSS/LMS susceptible to preimage/second preimage attack? Are the quantum secure hash based signatures (XMSS/LMS) susceptible to preimage/second preimage attack?

I'll first recall the security notions used for signatures and those used for hashes, and then try to answer your question.

The building blocks

For signature schemes, we try to have "existential unforgeability", where an adversary tries to forge the signature of a message that was not yet signed.
We also try to have the harder "strong unforgeability", where an adversary tries to propose another signature for a message that was already signed.

For hash functions, we have the notion of "first-preimage-resistance", also known as "being one-way", that is, it must be hard to retrieve a preimage.
Next we have "second-preimage-resistance", when it is hard to find a distinct preimage, knowing one existing preimage.
Finally we have the "collision-resistance", which is an harder property stating that it must be hard to find a pair of messages that hashes to the same value.

Now, LMS uses the Winternitz one-time signature (WOTS) as its one-time signature scheme (OTS), while XMSS is based on a variant of WOTS called WOTS+.

To XMSS' advantage, WOTS+ does not require its underlying hash function to be collision-resistant, so second-preimage resistance is enough.

Against classical adversaries it lessens the burden of birthday attacks, and is good for performance, because then smaller parameters will offer the same level of security.

LMS on the other-hand, being based on WOTS requires a collision-resistant hash function.

Now, if we can break the underlying hash functions, the proofs of security of signature schemes based on it would collapse with it, as mentioned by Poncho in this related answer. But this does not necessarily mean the signature scheme is completely broken in that case... (Even if it actually does in this specific case, see below.)

Quantum stuff

While we are at it, we should distinguish the Quantum world from the Classical one, because the "complexity" of the generic attacks against hash functions' properties will depend on the world we consider:

$$
\begin{array} {r|r|r|}
& \text{Classical} & \text{Quantum}\\
\hline
\text{Preimage} &  \Theta(2^{n})& \Theta(2^{n/2})\\
\text{Second-preimage} & \Theta(2^{n})& \Theta(2^{n/2}) \\
\text{Collision} &  \Theta(2^{n/2}) & \Theta(2^{n/2})\\
\end{array}
$$

This is so because Grover’s algorithm allows us to find preimages with a complexity of  $\Theta(2^{n/2})$ in a quantum world, however the birthday paradox bounds the complexity of the collision-resistance in the classical world already. (And we don't know a better way to go around it in the quantum world. See [Be09].)

So in a post-quantum world, it appears that WOTS based scheme are as good as WOTS+ based schemes. In the classical world, WOTS+ has a slight advantage...

The signature schemes

Let's now take a look at the signature scheme themselves, not their building blocks.

For both LMS and XMSS, a second preimage attack on their hash function would allow for a single forgery.

More importantly, a preimage attack would allow the attacker to derive his own Merkle tree from a public key, thus allowing him to sign as many messages as he wants. This being the consequence of the way the keypairs are created.

Finally, it is worth mentioning that Winternitz-based schemes are all vulnerable to two chosen messages attacks: if an adversary know the signatures of the all-0 and of the all-1 messages, then she can forge the signatures of all possible messages.
However, this does not compromise the asymptotic security of the schemes (see [BH16]) if we consider that we are signing message digests, since the all-zero message and the all-one message are no easily "found". (And other signature schemes are trivially insecure against the all zero message.)
But notice this can become a serious problem if we are considering "fault attacks" in our threat model. (Which can be the case with signature schemes.)

References

[Be09]   Bernstein, D. J. (2009). Cost analysis of hash collisions: Will quantum computers make SHARCS obsolete. SHARCS, 9, 105.

[BH16]   Bruinderink, L. G., & Hülsing, A. (2017, August). “Oops, I did it again”–Security of One-Time Signatures under Two-Message Attacks. In International Conference on Selected Areas in Cryptography (pp. 299-322). Springer, Cham.


AES Key Generation based on database guid I am developing a .NET application spanning multiple servers who should all be able to decrypt data stored in a SQL database. My database is multi-company where each company has its own GUID. since the data being encrypted is personally identifiable information (PII) and the requirement is to be PII compliant, I am encrypting it all with AES256-CBC were the IV is generated randomly at each encryption and data is stored in a binary field in this format

<version><IV><encrypted data>

the version field is for future use should I need to change encryption/decryption algorithm, the IV is random and then the encrypted data.

as for the AES key, I am hashing the company GUID the database record belongs to using SHA256 (resulting in the same key on each server that is trying to decrypt the record from the DB)
I am unable to use SQL encryption for various reasons and must use code for encryption/decryption.

Is this PII encryption scheme secure? Any downsides? I know that no matter what key generation code I build, a hacker if he is already on my server could use a debugger or look at the .NET IL to decode what I am doing. That said, if he only gets the raw data from the DB is that data secure?

It isn't secure at all unless the GUIDs are completely inaccessible to everything except the encryption code. I doubt that is the case in a real application; I assume every DB query and API call passes those GUIDs around. Any anyone who can access the database can easily hash the GUIDs as well and decrypt any of the data. Your scheme as described is basically pointless obfuscation, not strong encryption.

One alternative would be to use the per-customer GUID as a salt for the input to HKDF, and then use a global secret key for the whole app as the key input to HKDF. This will give you a per-customer secret key while not requiring the GUIDs to be secret.

Protecting this "master" app key will be challenging, but protecting it in the same way you protect your TLS certificate private keys makes sense as compromising either would break all security.


Is ECDSA obsolete/deprecated? I have been reading about recommendations on the correct use of crypto as a developer and I read at least two references to the obsolescence (so to say) of ECDSA.

https://paragonie.com/blog/2015/08/you-wouldnt-base64-a-password-cryptography-decoded
https://crypto.stackexchange.com/a/58382/63254

Is that it? Is ECDSA really obsolete/deprecated ?

Of course not. As long as it is used and - preferably - unbroken, the algorithm is still out there. Actually, it is used a lot in the smart card world and ECDSA certificates are still out there as well. Not all crypto libraries will probably support the newer curves either.

ECDSA is still secure when it is being used correctly. Sure, it is harder to secure but if it is used correctly then nothing short of a quantum computer can break it. It also has quite a few curves defined for it, so there are plenty of (stronger) key sizes allowed.

As far as I know, no standard defining ECDSA or build upon ECDSA has been redacted or withdrawn. You would expect that to happen if it would be considered obsolete / deprecated. If it is the best choice for new protocols is of course up to the designers - I'd probably prefer EdDSA for now.

And if MD5, RC4 and DES / two-key triple DES have taught us anything, it is that algorithms are being used even after they are broken and / or withdrawn. Unfortunately.


Can the precompiles in Ethereum Byzantium for pairings be used for implementation of BLS verification? I asked this in the Ethereum StackExchange yesterday but I figured it would be more appropriate to ask it here.

I am looking into implementing some operations for the BLS signature scheme in Solidity, using the new precompiled contracts for pairing operations released with Ethereum Byzantium, but I am not sure whether it is possible.

According to the BLS paper, page 310, to verify a BLS signature $s \in F_q$ corresponding to public key $V \in G_2$ and message $M$:

Find $y \in F_q$ with $\sigma = (s, y)$.
Compute $R \leftarrow MapToGroup(M) \in G_1$.
Test if either $e(\sigma, Q) = e(R, V)$ or $e(\sigma, Q)^{-1} = e(R, V)$.

Ethereum has added a few precompiled contracts for operations on the bn128 curve:

Addition
Scalar multiplication
Pairing check: Given an input $(a_1, b_1, a_2, b_2, \cdots, a_k, b_k) \in (G_1 \times G_2)^k$, returns whether $log_{P_1}(a_1) \cdot log_{P_2}(b_1) + \cdots + log_{P_1}(a_k) \cdot log_{P_2}(b_k) = 0$ (in $F_q$)

Supposing we have $R$ and $\sigma$, is step 3 possible using the precompiled contracts (with other Solidity functionality)? I am not sure I can find a formulation since there is no implementation for evaluating the pairing function $e$ itself.

Let $P_1$ be generator of $G_1$ and $P_2$ generator of $G_2$. Let $f:(G_1 \times G_2)^k\rightarrow\{0,1\}$ be Ethereum pairing check operation.

Given $\sigma,R \in G_1$ and $V\in G_2$ it is possible to check if $e(\sigma, P_2)=e(R,V)\vee e(\sigma,P_2)^{-1}=e(R,V)$ is true with Ethereum built-in operations, you just check check whether:

$f(\sigma, P_2, -R, V)$ is true or
$f(\sigma, P_2, R, V)$ is true

Why this works:

Let $\sigma=sP_1, R=rP_1, V=vP_2$. So $s=log_{P_1}(\sigma),r=log_{P_1}(R)$ and $v=log_{P_2}(V)$. Also please note that $\forall i\in\{1,2\}\forall a\in G_i:(-a)P_i=-(aP_i)$ and from that $-log_{P_i}(aP_i)=log_{P_i}(-aP_i)$
$e(\sigma, P_2)=e(sP_1, P_2)=e(P_1,P_2)^s$
$e(R,V)=e(rP_1, vP_2)=e(P_1, P_2)^{rv}$
$e(R,V)^{-1}=e(rP_1, vP_2)^{-1}=e(P_1, P_2)^{-rv}$
$e(\sigma, P_2)=e(R,V)\vee e(\sigma,P_2)^{-1}=e(R,V)\iff s=rv \vee s=-rv$
$s=rv \vee s=-rv \iff s-rv=0 \vee s+rv=0$
$s-rv=0 \iff log_{P_1}(\sigma)log_{P_2}(P_2)+log_{P_1}(-R)log_{P_2}(V) = f(\sigma, P_2, -R, V)$
$s+rv=0 \iff log_{P_1}(\sigma)log_{P_2}(P_2)+log_{P_1}(R)log_{P_2}(V)= f(\sigma, P_2, R, V)$
$s-rv=0 \vee s+rv=0 \iff f(\sigma, P_2, -R, V) \vee f(\sigma, P_2, R, V)$
$e(\sigma, P_2)=e(R,V)\vee e(\sigma,P_2)^{-1}=e(R,V)\iff f(\sigma, P_2, -R, V) \vee f(\sigma, P_2, R, V)$

Said that, the paper you're citing is based on symmetric (type-1) pairing. In ethereum BN curve is used in asymmetric (type-3) setting so you have to use version of BLS that is adapted to that. Fortunately, there is one proved secure: BLS-3b on page 11 of https://eprint.iacr.org/2009/060.pdf. You have:

private key $x\in F_q$
public key $(W=P_1^x, X=P_2^x)$
hash-to-point function: $H:\{0,1\}^*\rightarrow G_1$
signature $\sigma=H(m)^x\in G_1$
you verify using $e(\sigma, P_2)=e(H(m),X)$

Verification again can be done using Ethereum pairings:

$e(\sigma, P_2)=e(H(m),X) \iff log_{P_1}(\sigma)log_{P_2}(P_2)+log_{P_1}(-H(m))log_{P_2}(X)=0$
$e(\sigma, P_2)=e(H(m),X) \iff f(\sigma, P_1, -H(m), X)$

Please note that $W$ is used neither in signing nor verification but is required for security proof. There is version without it (BLS-3), where public key is just $X=P_2^x$, but you can't construct proof with it even though assumption here is weaker than in BLS-3b.


Why use 256-bit symmetric encryption when the key is exchanged using asymmetric cryptography that only provides 112 bits of security? Since a 2048-bit RSA key or a DH shared secret obtainet using a 2048-bit prime only provides the equivalent of 112-bits of security in symmetric encryption, what's the advantage of using AES-256 with a key derived from this level of asymmetric cryptography?

Why many protocols such as SSL use it? Is there any advantage?

As indicated with Ryan, the key size for RSA is not a configuration option of a TLS ciphersuite. The RSA key size is part of the authentication phase which is part of the TLS protocol, but it is not configured through the ciphersuite definitions. So the RSA_ ciphersuites and ECDHE_RSA ciphersuites do not specify any key size for RSA.

The AES key size is however a configuration option. This is because the AES keys are not static, they are session keys and session keys are ephemeral. They will be generated on each new TLS connection. To generate the right size AES key the size must be known beforehand, otherwise the key derivation cannot take place.

Usually you would link a 2048 bit RSA key with either AES-128 or 3 key triple-DES. However it's perfectly possible to derive AES-256 session keys using RSA-2048. It won't harm performance much either; AES-256 is only marginally slower than AES-128 using a software implementation (in hardware the difference may even be non-existent). So there is no penalty to using AES_256 in a ciphersuite. Allowing any AES ciphersuite - regardless of key size - may help (somewhat) with the establishment of a good ciphersuite - i.e. compatibility between client and server.

As indicated before, the RSA key may just be used to establish authentication. ECDHE or DHE may be used to establish the session keys to provide forward secrecy. So the strength of the keys used for confidentiality may be much higher then the key used for authentication.

As the authentication is required to happen in real time the strength of the authentication key may be significantly lower to the one used to provide confidentiality: it may be that an attacker can recover interesting information a long time after the connection as established (and eavesdropped). The authentication key may be revoked or be over the date of expiry a long time before that.

Then again, if you specify just AES_256 ciphersuites or put AES_256 above AES_128 ciphersuites you are basically lying to your users. You are offering a kind of protection that you cannot deliver due to the small key size used for RSA.

I would not feel comfortable doing so even when I would combine RSA with a ciphersuite offering forward secrecy.


How can a key pair be derived from an arbitrary hash? If I correctly understand the concept of a "brain wallet" in BitCoin, you start with a passphrase, generate the hash of the passphrase, then somehow derive a public / private key from that to use as your BitCoin identifier.

This conflicts with what I understand about key pairs... namely that they are special... not every number is qualified to be part of a key pair because there are requirements related to prime factorization.  So how can the "brain wallet" algorithm work, since the hash could be any number?

Bitcoin doesn't use RSA, it uses ECDSA. Every 256-bit value is a valid private key. (Though a very small fraction of them have to be folded.)

But even if the numbers had to be special, it still wouldn't matter. You could use every 256-bit value as a seed to a pseudo-random number generator which you could use to deterministically generate numbers that had whatever properties you need.

You can also trivially create schemes to generate numbers that do have needed properties from passphrases. For example, Ripple uses a scheme like the following:

Set a counter to zero.
Hash the passphrase together with the counter.
Does the hash have the needed properties? If so, stop. We're done.
Increment the counter.
Go to step 2.


If all encrypt algorithms in TLS1.3 ciphersuites are AEAD , why do they keep including a Hash algorithm? In TLS1.3 all allowed algorithms included in cipher suites are AEAD, which means they don't just encrypt but they authenticate too (thus if I don't misunderstand, they give not only confidentiality but also integrity/authentication. So, then...why it's necessary to include a Hash algorithm in the cipher suite? I mean...why isn't ChaCha20 (or AES-GCM, etc) enough so Poly1305 (or SHA256, etc) should be necessary?

From RFC 8446, the hash is used for:

The transcript hash, covering every message in the handshake to authenticate it during key agreement and certificate verification (§4.4.1).
Deriving various session keys from raw key agreement material and transcript hash with HKDF (§7.1).
Deriving key material for protocols based on the key negotiated in a TLS session (RFC 5705).


how Content Scramble System (CSS) works? As I understand, the Content Scramble System (CSS) uses proprietary 40-bit stream cipher algorithm to decrypt the DVD content

My question is; where does this key come from? is it embedded within the Hardware DVD player or within the software player?

what's the principle in which this method prevent DVD copy?

1. Where does this key come from?
2. Is it embedded within the Hardware DVD or within the software player?

The soft|hard players have to authenticate to access the key from the disk. From Wikipedia

The details of CSS are only given to licensees for a fee. The
license, which is bound to a non-disclosure agreement, wouldn't
permit the development of open-source software for DVD-Video playback.
The player has to execute an authentication handshake first The authentication handshake is also used to retrieve the disc-key-block and the title-keys.

So, non-disclosure has the force.

3. what's the principle in which this method prevent DVD copy?

It has three types of protection, from wiki page;

Playback protection is based on encryption: the player requires a secret key to decrypt the feature.
Read protection is based on the drive: access to significant disc data is only granted if the player authenticates successfully.
Regional restriction is based on the disc and the drive: the drive can deny access if the disc doesn't belong to the drive's region.

All three protection methods have been broken.

And the keys are in the lead area of the DVD2;

It prevents byte-for-byte copies of an MPEG stream from being playable since such copies will not include the keys that are hidden on the lead-in area of the protected DVD disk


Finding a collision for a hash function I'm trying to find a collision for the following (modified) Merkle–Damgård hash function.

  Suppose we already have a hash function $h : \mathbb{Z}_2^{2·n} \to \mathbb{Z}_2^n$ for fixed length bit strings, with $h(0\ldots 0)= 0\ldots 0$.

  The input $x$ (bit string, variable size) is divided into blocks $x_j$ of $n$ bit each, padding the last block with zeroes if necessary:
  $$
\overbrace{x_0}^{n \text{ bit}}|| \overbrace{x_1}^{n \text{ bit}}|| \ldots|| \overbrace{x_{i-2}}^{n \text{ bit}}||\overbrace{x_{i-1}|| 0\ldots 0}^{n \text{ bit}}
$$

  We add another block $x_{i}$ of $n$ bit, containing the binary representation of $|x|$ (length of x), resulting in:

  $$
\overbrace{x_0}^{n \text{ bit}}||\overbrace{x_1}^{n \text{ bit}}||\ldots||\overbrace{x_{i-2}}^{n \text{ bit}}||\overbrace{x_{i-1} 0\ldots 0}^{n \text{ bit}}||\overbrace{|x|}^{n \text{ bit}}
$$

  Therefore we have $i+1$ blocks of $n$ bit each. For $0\leq j\leq i$, refer to the $j$th block as $b_j$.
  Define $y_0 := 0\ldots 0||b_0$ and $y_j := h(y_{j-1})||b_j$ for $1\leq j\leq i$
  ($0\ldots 0||b_0$ and respectively $h(y_{j-1})||b_j$ means concatenating everything together).

  The hash function $h^*$ is then defined as
  $$h^*(x) := h(y_i)$$

How can one find a collision for $h^*$ without having one for $h$?

The answer is that you can't; if you have a collision in $h^*$, you also have a collision in $h$.

The standard way to prove a collision-resistant hash based on a hash-resistant primitive is to show that if we are given a collision in the full hash, we can show that gives us a collision in the primitive.  Hence if we believe we can't find a collision in the primitive, we hence can't find a collision in the full hash.

That technique appears to work quite well here.

Suppose we are given two colliding messages $M$ and $M'$, that is $M \neq M'$ and $h^*(M) = h^*(M')$.  We will show how to examine how the two messages $M$ and $M'$ are processed by $h^*$ to show that there must have been some internal collision on one of the calls to $h$.

First, consider the case that $y_i \ne y'_i$.  If that is the case, then we immediately have a collision, because $h(y_i) = h^*(M) = h^*(M') = h(y'_i)$

The other possible case is that $y_i = y'_i$.  This implies that the length of the messages $M, M'$ are the same (because the lengths of $M, M'$ are included in the values $y_j, y'_j$.

We also know that $M, M'$ differ somewhere, that is, in at least one $n$-bit block.  Let us call $j$ one of the positions that $M$ and $M'$ differ; that is, $b_j \neq b'_j$.  This immediately implies that $y_j \neq y'_j$ (because $y_j, y'_j$ contain $b_j, b'_j$ as substrings).

Because $y_j \ne y'_j$ and $y_i = y'_i$ and $j<i$, that means there must be a $j \le k < i$ where $y_k \ne y'_k$ and $y_{k+1} = y'_{k+1}$.  That immediately gives us a hash collision in h, because $h(y_k) = h(y'_k)$


Algebraic cryptanalysis on public-key schemes The book Algebraic Cryptanalysis (Bard, G.V.; Springer, 2009) speaks about transforming a symmetric scheme into a system of polynomial equations and solving these equations to break the scheme.

But is there no way to do the same with asymmetric schemes?
Is it impossible to apply the same techniques to this kind of scheme?

Of course, it is possible.  It is possible to take a public key encryption algorithm which takes the private key and the known ciphertext into the known plaintext, convert that into a set of equations in $GF(2)$ with the private key as unknown variables, and solve for those unknown variables.  Alternatively, you can take the key generation algorithm, which takes some random bits and converts that into the public and private keys; convert that into a set of equations with the public key output as known, and solve for the private key (and the random bits).

However, the relevant question is "is this (converting the problem into a form that has known NP-hard instances) easier than solving the hard problem directly?"  I don't believe it is.


Why is the lite version of Cramer-Shoup not IND-CCA2 secure? In the lite version of Cramer-Shoup we have a group $G$ with generators $g_1$ and $g_2$, private key $a_1, a_2, b_1, b_2$, and public key $A = g_1^{a_1} g_2^{a_2}$, $B = g_1^{b_1} g_2^{b_2}$. Encryption works by picking a random integer $r$ and sending the tuple $(g_1^r, g_2^r, A^r m, B^r)$. When decrypting we check the $B^r$ portion of the ciphertext is correct and, if so, obtain $m$ by calculating the inverse of $A^r$ and multiplying $A^r m$ with it.

Consider the following formulation of DDH: for random group elements $g_1, g_2, u_1, u_2$ and random integer $r$, $(g_1, g_2, u_1, u_2)$ is indistinguishable from $(g_1, g_2, g_1^r, g_2^r)$. Cramer-Shoup lite can be shown to be IND-CCA1 secure under this assumption. The proof goes by employing a hypothetical CCA1 attacker $\mathcal{A}$ which breaks Cramer-Shoup lite to break DDH. Our challenge instance is a quadruple $(g_1, g_2, u_1, u_2)$. We simulate the IND experiment for $\mathcal{A}$ with our own generated private and public keys; thus we can also simulate its decryption oracle since we have full knowledge of the scheme's private key. When $\mathcal{A}$ commits itself to a message pair $m_0, m_1$, we send it one of this messages (randomly chosen) encrypted, but with $g_1^r$ replaced with $u_1$ and $g_2^r$ with $u_2$. Thus $\mathcal{A}$ receives $(u_1, u_2, u_1^{a_1} u_2^{a_2} m, u_1^{b_1} u_2^{b_2})$, which is a valid encryption iff $u_1 = g_1^r$ and $u_2 = g_2^r$ for the same exponent $r$. $\mathcal{A}$'s response (ciphertext is valid or not) is correct with non-negligible probability, so we can distinguish the DDH quadruples with non-negligible probability.

I am having trouble understanding why the argument fails for IND-CCA2. Is it because $\mathcal{A}$ can use $u_1$ and $u_2$ in subsequent decryption queries?

CS-lite has the same homomorphic properties as ElGamal. In particular, compontentwise product of $\textsf{Enc}(pk,m_1)$ and $\textsf{Enc}(pk,m_2)$ is a valid encryption of $m_1 m_2$ (and hence will decrypt properly):

$$(g_1^r, g_2^r, A^r m_1, B^r) \cdot (g_1^s, g_2^s, A^s m_2, B^s) = (g_1^{r+s}, g_2^{r+s}, A^{r+s} (m_1m_2), B^{r+s})$$

So a simple CCA2 attack is to request $\textsf{Enc}(pk,m)$ for an unknown $m$, multiply this ciphertext by a fresh encryption of 1, and ask the decryption oracle to decrypt the result (revealing $m$).


Which properties of a group are used in the steps of Diffie Hellman? I’m trying to understand which properties of a group are used in DHKE at each step.

For example, Alice and Bob’s public keys appear to only use the closure property of a group and maybe identity  (e.g. $k_{pubA}$ = $A^{k_{prA}}$ (mod p)?

When creating the shared key Alice and Bob appear to also use the associative property of a group $k_{AB}$ = $B^{k_{prA}}$ (mod p)?

So to perform both main steps of DHKE the multiplicative inverse property does not seem to be used at all?

I’m trying to understand which properties of a group are used in DHKE at each step.

Actually, you can implement a DH-style operation in any semigroup; you need closure, and you need associativity (so $A^3 = A\times A \times A = (A \times A) \times A = A \times (A \times A)$ is well defined), but other than that, you really don't need anything.  You don't need an identity, you don't need the semigroup to be abelian (although the sub-semigroup generated by a single element will always be abelian), it doesn't have to be finite (although infinite semigroups would cause practical problems during implementation) and you don't need inverses (which, if you don't have an identity, aren't well-defined anyways).

We typically don't talk about doing DH in a semigroup mostly because (AFAIK) no one has found a semigroup (that's not also a group) that has any particular advantage over a true group.

Now, what's a more interesting (and considerably harder) question is "what properties do you need for DHKE to be secure?"  We do have assumptions such as the CDH assumption ("given $g, g^a, g^b$, it's hard to compute $g^{ab}$), however we don't know what semigroup properties ensure that...


NIZKs for hash functions Hash functions such as SHA are considered as non-algebraic statements. How can one construct a NIZK proof to show that the output of a hash is computed correctly in an efficient manner.

For example, one could rely on ZKBoo, which in turn builds upon the MPC-in-the-Head paradigm by Ishai et al. The authors even provide an implementation, which demonstrates how to prove knowledge of a SHA-1 and SHA-256 preimage, respectively. The proofs are of linear size in the number of AND gates in the circuit. For more compact proofs you could have a look at SNARKs.

The authors discuss $\Sigma$-protocols, which are in fact interactive. However, as shown here or here, one can make those proofs non-interactive using the Fiat-Shamir transform (yielding security in the random oracle model) or the Unruh transform (yielding security in the quantum accessible random oracle model).


CTR block generation From what I understand, CTR works by taking a counter, concatenating it with a nonce, and encrypting the result, which gets XORed to the ciphertext. For a 128-bit block cipher (ie. AES), my understanding is that the first 8 bytes of the CTR block is the nonce, and the second half (bytes 8-16) is the counter. CTR is a secure mode of operation, but what if I modified it like this:
The nonce is 16 bytes, the counter is 16 bytes. The counter block is equal to nonce XOR counter.
Basically, he counter blocks are just XOR of nonce and counter. Would this be secure, or would this defeat the idea of CTR and be insecure?
Edit: For more clarity, here's CTR mode and my modified mode:
CTR:
nonce = 12345678
counter = 00000001
CTR block = 1234567800000001

My scheme:
nonce = 1234567890abcdef
counter = 0000000000000001
CTR block = 1234567890abcdeW

CTR works by taking a counter, concatenating it with a nonce, and encrypting the result

Not quite. CTR works by taking a value that is unique per block encrypted with the same key and encrypting it. How this value (the counter block) is constructed is not standardized, and all that matters for security is its uniqueness (and independence of the encryption key).
One way to use CTR mode is to keep a count of blocks (a number: 0, 1, 2,  …) that are encrypted with that key, and use a representation of that number as the counter block: typically base 256 big-endian or base 256 little-endian, if you see the counter block as an array of 8-bit bytes. That works when there is a single entity using that key, it only ever encrypts one message at a time, and it remembers where it left off between blocks.
This simple approach breaks down if multiple entities want to encrypt, or if even one entity wants to encrypt multiple messages in parallel, since there's no practical way to both keep counter values consecutive within a single message (without that, you'd need to save all the counter values with the message and not just the initial value) and avoid repeating counter values (which would break security).
The best solution is to never encrypt two messages with the same key, and instead do two steps to encrypt a message: first derive a key from a per-message nonce, then use that single-use key to encrypt the message. You would then send the derivation nonce with the message, and you wouldn't need to send the initial counter value since you can simply always start at 0.
If you want to encrypt multiple messages with the same key, you need a way to have disjoints sets of counter values per message. A common way to do this is to break the counter block into two parts: a per-message nonce, and an in-message counter. This limits the possible length of messages to the number of blocks that can be represented with the in-message counter, for example a 32-bit in-message counter means a maximum of $2^32$ blocks (so $2^{36}$ bytes for ciphers such as AES with a 128-bit block size). The per-message nonce needs to be unique per message, for example a counter of messages sent.
Another common approach that avoids saving state (such as the number of messages sent) is to start each message with a random counter value and increment it throughout the message. This is fine as long as you don't send too much data with the same key, where "too much data" means you mustn't get close to the birthday bound, i.e. the square root of the number of possible blocks. For a 128-bit block size, this means don't get close to $2^{64}\,\text{blocks} = 2^{68}\,\text{bytes}$ of data.
Xoring a per-message nonce with the in-message counter may or may not work depending on how the nonce is generated. For example, if the nonce is a count of messages sent, it's horribly bad, because it leads to repeated counter block values. In base 2, and just representing the last three bits of the counter blocks, you'd have:

First message: first counter block $000 \oplus 000 = 000$, second counter block $000 \oplus 001 = 001$, …
Second message: first counter block $001 \oplus 000 = 001$, second counter block $001 \oplus 001 = 000$, …

As you can see, counter blocks are repeated, and that defeats the security completely.
If your nonce is a random 128-bit value, it's similar to the common method of starting with a random 128-bit value and incrementing it, but with an order of enumerating counter blocks that depends on the per-message initial counter value. I think this has the same statistical properties, but I haven't done the math. It complicates the implementation very slightly. I don't see any particular benefit.


TLS: Does Diffie-Hellman make private keys useless When we are using TLS these days we use DH to establish a session key. So where in the TLS protocol do we determine that the host that we're talking to actually possesses the private key corresponding to the x509 certificate that it provided earlier? Or is this no longer required?

TL;DR: The host signs his public DH key

  When we are using TLS these days we use DH to establish a session key.

That depends, the RSA_ ciphersuites - that encrypt the session key using the RSA public key of the server key pair - can still be used even with TLS 1.2. They will be completely deprecated for TLS 1.3 as it looks now.

There are the ephemeral-static protocols as well - DH_ instead of DHE - although these are commonly not used in practice; they require a special X.509 certificate with DH or ECDH keys.

  So where in the TLS protocol do we determine that the host that we're talking to actually possesses the private key corresponding to the x509 certificate that it provided earlier?

Absolutely. Let's take a look at the 1.2 standard:

  When Diffie-Hellman key exchange is used, the server can either
     supply a certificate containing fixed Diffie-Hellman parameters or
     use the server key exchange message to send a set of temporary
     Diffie-Hellman parameters signed with a DSA or RSA certificate.
     Temporary parameters are hashed with the hello.random values before
     signing to ensure that attackers do not replay old parameters.  In
     either case, the client can verify the certificate or signature to
     ensure that the parameters belong to the server.

And this is apparent in the ServerKeyExchange message (in C):

case dhe_rsa:
    ServerDHParams params;
    digitally-signed struct {
        opaque client_random[32];
        opaque server_random[32];
        ServerDHParams params;
    } signed_params;

signed_params
    For non-anonymous key exchanges, a signature over the server's
    key exchange parameters.

  Or is this no longer required?

Of course this is required, unless another method of authentication - such as a pre-shared key (PSK) - is used. How would you otherwise authenticate the server?

Just possessing the public certificate is obviously not enough; the server needs to show that it can use the private key associated with the server certificate (within the verified & validated chain of certificates build by the client).


How to prove that work is done without actually knowing the payload Is there a way for an algorithm to run securely on one end, whilst the other end is able to be notified and also verify that it has run and done the work without knowing what the actual payload is?

For example, $A$ provides an algorithm that adds $1$ to any number.

$B$ takes this algorithm and performs it $N$ number of times. $A$ can then verify that $B$ has performed it $N$-times without knowing what $N$ is.

The answers to these questions depend heavily on the threat model.  Starting from the most pathological, and working our way back:

If the software has to be run on the remote machine, and $A$ cannot know anything about the data, and $B$ is willing to take full advantage of physical access to the remote machine, there's really nothing you can do.  Physical access is really hard to beat.
If $A$ can know a little of what $B$ needs, $A$ might be able to provide the algorithm encrypted in pieces, such that $B$ only gets enough of the algorithm to solve that one problem, but has to go back to $A$ to solve the next.  However, this requires knowing a little about $B$'s data and is very algorithm specific.
If the algorithm doesn't have to be run remotely, there's the relatively new field of homomorphic encryption.  This would let $A$ run the algorithm locally on an encrypted copy of $B$'s data without konwing anything about it.  However, this field is in its infancy, and practical examples are hard to find.
If we can reasonably trust $B$ to not reverse engineer the code, new options form.  At some point this trust becomes a legal question, which can get complicated.

In the last case, there is actually a solvable answer.  $B$ runs the program, which takes the inputs and outputs an encrypted form of the outputs (typically with asymmetric encryption).  This key is derived from the hash of all of the inputs.  This hash is then provided to $A$, who looks at that hash, and provides the correct decryption key.

It can also be done in the reverse order: $B$ hashes the inputs, $A$ looks at the hash, and signs them.  $B$ takes that signature and the inputs, and passes it into the algorithm, which confirms that the inputs are signed.


Is there a scheme where two cipher texts can be proven to have the same (unencrypted) content? Is there a scheme where two ciphertexts (encrypted with different keys) can be proven to have the same (plaintext) content without disclosing the plaintext or any private keys?  I assume that the public keys would need to be known.

This is for the purpose of detecting duplicated content on a server, without knowing the content.

This is probably impossible, but reading about homomorphic encryption leads me to think that it might be possible.

Consider that I, as an attacker, suspects what you're sending in your secret messages.  If what you propose were possible, then I could know your plaintext by comparing my encryption of what I thought you were sending to what you actually sent, and brute for variations until I could confirm what you had sent.  This would be VERY bad.  Therefore, I assume you understand why I hope what you want is impossible as you proposed.

What could be done, would be to hash the message before encrypting it, and then comparing the hashes... this would again, especially with rainbow tables, lead to what I said above... the ability to know the message without decrypting it.


Cryptanalysis of this one-time pad My question is related to this:
Security of one-time-pad without $\bmod $ operation?
but the way we mask values is different here.

We consider a finite field, $\mathbb{F}_p$, and a ring $\mathbb{Z}_N$, where $N$ is RSA modulus, and such that $p<<N$. Value $p$ is a (large) prime number and indepent of the prime numbers used to generate $N$.

Let $m_i\in  \mathbb{F}_p$. We mask it as:

$m'_i=m_i+r_i$, where $r_i$ is picked uniformly at random from the ring but  $m_i+r_i \in \mathbb{Z}_{N}$.

Please note that we do NOT perform $\bmod N$ when we compute $m'_i$.

Question 1:  Is there any way to argue that given $m'_i$, a semi-honest adversary cannot learn anything about $m_i$ ? for instance, it is statically indistinguishable etc.

For the sake of simplicity let's assume all the values are non-zero. we can pick large enough $p$ and $N$ to meet any security definition if it's required.

Yes, I believe you can argue statistical indistinguishability here. But, note that this is a weaker property than the typical one-time-pad which is perfectly secure, because XOR is mathematical magic (incurring no $\mathsf{negl}(\lambda)$-sized statistical offsets as below..).

High-level idea: If $N$ is sufficiently large with respect to $p$ --- i.e. if $N \ge \Omega(p\cdot\lambda^{\omega(1)})$ --- then random samples of size $\approx N$ will statistically swallow any "$p$-bounded" distribution (random samples of size $\approx p$).

[[Let $\lambda$ be the security parameter. For now, I'll ignore the factorization of $p$ vs $N$ for this..]]

Here's some fun with statistical distance between distributions:

A distribution $\chi$ is $(B,\epsilon)$-bounded if the probability of sampling a value larger than $B$ is unlikely; i.e. $$\Pr_{x\leftarrow\chi}[|x| > B] < \epsilon.$$

(Aside: Actually, my discussion here also assumes that the bound $B$ in $B$-bounded distributions is "chosen as small as feasible" for a given distribution; i.e. $B$ should be "tight" for $\chi$ asymptotically.)

A distribution $\widetilde{\chi}$ is $(B,\epsilon)$-swallowing if for all $y\in [-B, B]$ (respectively, $y\in [0, B]$), it holds that $\widetilde{\chi}$ and $y + \widetilde{\chi}$ are within $\epsilon$ statistical distance.

It turns out that the ("truncated," resp. "rounded") Gaussian distribution satisfies the property described above; namely, any $\left(B\cdot\lambda^{\omega(1)}, \epsilon\right)$-bounded distribution $\chi$ is also a $\left(B, \epsilon+\mathsf{negl}(\lambda)\right)$-swallowing distribution as well. (Gaussians just happen to often have "nice" geometric properties like this.)

For example: If $\chi$ is $(B, \mathsf{negl}(\lambda))$-bounded, and if $\widetilde{\chi}$ is $(B\cdot\lambda^{\omega(1)}, \mathsf{negl}(\lambda))$-bounded, and we sample $x\leftarrow\chi$ and $\widetilde{x}\leftarrow\widetilde{\chi},$ then we have:
$$
\widetilde{x} + x \stackrel{\rm stat}{\approx} \widetilde{x}
$$

In general, many "natural" distributions will exhibit this "swallowing" property. The Uniform distribution over (ranges of) integers is well-defined by a bound $B$ (or $p,$ or $N$), and swallows all 'small, uniformly random integers' w.h.p. whenever there is a superpoly gap in magnitude.

Note that you need to "sample & add-in" a fresh, i.i.d. "swallowing term" to each new message, for each time you use this kind of argument.. As far as going beyond truncuated Gaussians or bounded ranges of integers: Use your judgment! =) The distributions (certainly) must hit the same (say..) subgroups to use this argument, etc.

..finally, note there's no need to bother with statistical swallowing if the desired security property is a (standalone) One-Time Pad! Just using the standard OTP will be more efficient (fewer bits sampled in order to blind messages; i.e. less randomness needs to be securely/safely generated/shared). Moreover, the standard OTP will achieve stronger than just statistical indistinguishability.


Observing cipher suites and certificate algorithms without man-in-the-middle I manage a proxy server. Is it technically possible to observe and determine which cipher suite is selected between end points (client and server) without changing their SSL certificate, without mimicking server certificate through a proxy in general?

My main goal is to obtain weak algorithms that parties agree upon.

For example, if client and server get on MD5 or SHA1, DES or CAST included cipher suite, or on SSLv3, or, if server sends my client a certificate signed with SHA1, or an expired certificate etc., I want to detect this traffic.

Note: I already asked a question about specific server technologies here: Server Fault Question

There are no TLS ciphersuites using CAST, so you can determine that one without looking at any actual data of any kind from any connection(s).

Yes, you can always tell passively (merely by looking) at a TLS handshake the selected ciphersuite. Note ciphersuites containing 'SHA' (meaning SHA1) use it only for the key derivation (called PRF through 1.2), and HMAC through 1.1 (always) or in 1.2 for any CBC-mode cipher or RC4 -- but RC4 is so weakened it should never be used at all according to rfc7465 in 2015. Using SHA1 or even MD5 in key derivation or HMAC is not a weakness; their breakage for collision only endangers certificates. (And actually not all certificates, but enough that the consensus is to ban them entirely.) You should definitely worry about any use of single-DES, as well as the 'export' suites with DES-40 or RC4-40 (as above, even full-strength RC4-128 is now officially prohibited). Some people worry about Triple-DES (written 3DES_EDE_CBC in the RFC names, and 3DES-CBC3 in OpenSSL's scheme) because of the generic birthday bound for 64-bit block -- see https://www.sweet32.org -- but for many applications, e.g. accessing StackExchange, this is not a problem. IDEA in principle also has the 64-bit block issue, but it is very rarely used, mostly because its patent status caused many people to avoid it in the past, and now there's no reason, benefit or incentive to go back to it instead of newer, better options.

Through 1.2 you can also see the server certificate chain (which will almost always be two and occasionally more, not 'a' certificate as you asked) and check the signing algorithms, and key sizes which is more important. MD5 and SHA1 broken for collision does endanger certs, as above, and as a result no cert issued by a public CA after about 2008 uses MD5 and none after 2015 or at most 2016 uses SHA1 for signature -- and the certs issued before that are all expired and invalid (except roots where the signature algorithm doesn't matter at all). In 1.3 the certifcates are now encrypted, but if you are on-path you can actively make a test connection to the same server with the same parameters and you're pretty much guaranteed to get the same certificates, which you can look at. For that matter many certs from public CAs are now in the public transparency logs and you can look there -- although if a server/domain has multiple current public certs in the logs you don't know which one(s) is(are) actually used.

Those said, regarding your other Q I have no idea whether squid in particular can do any or all of this, or could resonably be modified to do so.

Lastly, to be clear, although this will detect some cases where a connection is insecure, the lack of an identified weak primitive in a connection does NOT mean it is secure. Except for the intentionally-broken export suites and long obsolete single-DES, and a few cases of certs signed using MD5, I've heard no credible allegations of real-world breaks of SSL/TLS connections because of weak primitives (not even RC4). Instead the breaks are due to bad parameters or keys (sometimes visibly so, i.e. too small, sometimes not) or protocol or implementation flaws, or not the connection at all but rather an endpoint. Plus not all connections even between the same pair of endpoints are the same, and the existence of some apparently-good connection(s) does not prevent the past, present, or future occurrence of bad one(s).


A Simple Provably Secure Key Exchange Scheme Based on the Learning with Errors Problem In this paper (A simple provably secure key exchange by Ding et al.)  At page number 8, the author gives correctness of the technique as follows

then SK A  = SKB with overwhelming probability i.e. if Alice and Bob run the protocol honestly, then they will share an identical key.

The above equation uses Lemma 1 which is as follows

How does the author deduce the above equation using Lemma 1. This equation gives correctness of the technique. Can anyone please help.

First: Lemma 1 says that $||\mathbf{x}|| \leq \alpha q \sqrt{n}$ with overwhelming probability if $\mathbf{x}$ is drawn from the discrete Gaussian since $\frac{1}{2^n}$ is negligible.

Next, from properties of absolute values, $|a + b| \leq |a| + |b|$. So, leaving the $2$ out for now and writing $\mathbf{s_A}^T\mathbf{e_B}$ as $\mathbf{s_A}\cdot\mathbf{e_B}$:

$|\mathbf{s_A}\cdot\mathbf{e_B} + e'_A + \mathbf{s_B}\cdot\mathbf{e_A} + e'_B| \leq |\mathbf{s_A}\cdot\mathbf{e_B}| + |e'_A| + |\mathbf{s_B}\cdot\mathbf{e_A}| + |e'_B|$.

Now, for Euclidean norms, Cauchy-Schwarz says $|\mathbf{a\cdot b}| \leq |\mathbf{a}|\cdot |\mathbf{b}|$, so we have, for example, $|\mathbf{s_A}\cdot\mathbf{e_B}| \leq |\mathbf{s_A}| \cdot |\mathbf{e_B}| \leq  (\alpha q \sqrt{n})\cdot (\alpha q \sqrt{n})$, the last inequality coming from Lemma 1.

Let's tackle $e'_A$ and $e'_B$. I could sample a vector $\mathbf{e'}$ from $\mathcal{D_{\mathbb{Z^n},\alpha q}}$ and Lemma 1 would apply to it; if $e'_A$ is a member of $\mathbf{e'}$, it is certainly smaller than $||\mathbf{e'}||$:

$|e'_A| \leq ||\mathbf{e'_A}|| \leq \alpha q \sqrt{n} \leq (\alpha q \sqrt{n})\cdot (\alpha q \sqrt{n})$. Same for $e'_B$.

Thus I have four terms, all $\leq (\alpha q \sqrt{n})\cdot (\alpha q \sqrt{n})$. Multiply back in that $2$ and you have the result.

Edit

They do a similar procedure later on in Section 4, and explicitly write out norms, for future reference.


ElGamal signature without calculating the inverse I stumbled upon this question in some textbook.

  Propose a variant of ElGamal signature scheme  such that there is no need to calculate the inverse $k^{-1}$ as it is usually done using the EEA.

Recalling what ElGamal signature is about: we fix a prime number $p$ and a generator $\alpha$ of $Z_p^*$. User $A$ then chooses a number $a \in \{0, \ldots, p-1\}$ as its private key and sets $ \beta = \alpha^a \pmod{p}$ as its public key. To sign a message $x$, $A$ chooses a random $k \in Z_{p-1}^*$. The signed message is then  $(\gamma, \delta)$  where $$\gamma \equiv \alpha^k \pmod{p} \quad{} \hbox{and} \quad{} \delta \equiv (x-a\gamma)k^{-1} \pmod{(p-1)}$$

To verify the validity of the signature, $B$ verifies that $$ \beta^\gamma \gamma^\delta \equiv \alpha^x \pmod{p}$$

I have no idea how to solve this problem without breaking the security of the system. Browsing the internet, I've found some papers related to this problem, but the proposed solutions seemed too complicated for a question posed at the undergrad level. Does anyone know a clever solution?

Try switching $\alpha$ and $\gamma$ during the verify.

Fix a prime number $p$ and a generator $\alpha$ of $Z_p^*$. User $A$ then chooses a number $a \in \{0, \ldots, p-1\}$ as its private key and sets $ \beta = \alpha^a \pmod{p}$ as its public key. To sign a message $x$, $A$ chooses a random $k \in Z_{p-1}^*$. The signed message is then  $(\gamma, \delta)$  where $$\gamma \equiv \alpha^k \pmod{p} \quad{} \hbox{and} \quad{} \delta \equiv kx-a\gamma \pmod{(p-1)}$$

To verify the validity of the signature, $B$ verifies that $$ \beta^\gamma \alpha^\delta \equiv \gamma^x \pmod{p}$$

Correctness:
$$\beta^\gamma \alpha^d = \alpha^{a\gamma+d} \text{ but } \gamma^x = \alpha^{kx} \text{ and } d = kx-a\gamma$$

Security: Seems a little iffy to move the known exponent onto an unknown generator, but forging a signature ($\delta$) for a given $\gamma$ still seems like a discrete log problem with base $\alpha$.  I don't know if there is a better way to choose $\gamma$ to make forging signatures easier though.

The definition of $\delta$ does not use $k$ (beyond $\gamma$) to mask the secret key $a$.  I think just using $\gamma$ is a bad idea, so I think this system is insecure, but I forget the attack.


Where is the mistake in my RSA by-hand calculation? Like several previous askers, I seem to have made a mistake in my RSA calculation, but despite going back over it three times, I cannot spot it.

I picked 1000003 and 6000011 as my primes, p and q.

n = 1000003 * 6000011 = 6000029000033
z = φ(n) = (1000003 - 1) * (6000011 - 1) = 6000022000020
e = 17 (arbitrary pick of small integer that's coprime to z)

Public key is (e, n) = (17, 6000029000033)

Found d by solving (17 * e) mod z = (17 * d) % 6000022000020
d = 857146000003

d was calculated with an online multiplicative inverse calculator. I suspect this is where the error is, but I've redone it several times with different calculators to no avail.

So then I encrypted the number 6:

encryptedMessage = (message)^e mod n
encryptedMessage = (6)^17 mod 6000029000033
encryptedMessage = 4926601444670

Decryption is where I realized something must be wrong, because:

message = (encryptedMessage)^d mod n
message = 4926601444670 ^ 857146000003 mod 6000029000033

Except obviously that exponential operation is too huge to be done. I can't calculate it anywhere. It crashed my interpreter when I put it into python.

What am I doing wrong here?? :(

Or, perhaps, am I doing it right, and it's just that there's a necessary efficient method for this calculation which I'm not aware of?

Your $d$ is indeed incorrect. I get $d = 4235309647073$, using Wolfram alpha.

As to python, use the builtin pow function with a third argument equal to the modulus.

So

message = 6
encmessage = pow(message, 17, 6000029000033)
assert message == pow(encmessage, 4235309647073, 6000029000033)

which will apply a smart algorithm like those in answers to this question. Never compute the direct power first!


Bilinear Form: Weil pairing I am doing an example on Weil pairings, and for that purpose I follow the thesis of Alex Edward Aftuck, The Weil Pairing on Elliptic Curves and Its Cryptographic Applications.

By following his thesis, on page #39 he selects 4 points on the elliptic curve  $Y^2=X^3+2X^2-3X$ and calculates six divisors from it
as shown in the figure:

Using divisors, he calculated four rational functions as  but in the last step, he calculates the Weil pairing between $P_1 $ and $P_3$. The sums of points are $P_3+S=(-2.496,-2.047) $ and $P_1-S=(20.798,-98.990) $.

My question is: how can I can put the points into the functions $f_{p_1} $ and $f_{p_3} $?  All of the functions have three variables $X,Y,Z$, but we have  only two points. What is the value of $Z$, and how can I calculate functions using these points? Please help me as I'm really confused.

See page 17 of the thesis you linked to. There he mentions affine coordinates and homogenization. For your points, $Z=1$. So just set $Z=1$ in your functions above.

  To find the poles, we must remember that as a rational
  function, $Y = Y/1$. Homogenizing, we have $f(X, Y, Z) = Y/Z$. Then to find the poles
  of $f$, we must analyze $Z$ as a polynomial. For all affine points on $E$, $Z = 1$, so $Z = 0$
  only at $\mathcal O$.

Here's more about projective coordinates.

Keep in mind that in general, the sum of two points in projective coordinates having $Z=1$ is not a point with $Z=1$. In this case, the author already did the sums $P_3 + S$ and $P_1 - S$ in affine coordinates.


Hash Function to get same value for different messages I am studying a function where I found the some hash properties.

Hash functions:

Given a code c is computationally infeasible to find m such
that h(m) = c
Given m is computationally infeasible to find n != m such that
h(m) = h(n)
It is computationally infeasible to find any pair (m, n) such
that h(m) = h(n)

Actually every point is clear to me. But I wondering what is the difference between point 2 and point 3? Can anyone give me any clue? Thanks.

For cryptographic hash functions, there are the 3 definitions of collision resistance, (first) preimage resistance and second preimage resistance.

Number 3 is collision resistance, and it is quite different than No. 1 and No. 2, which is due to the birthday problem (also see birthday attack).

In No. 1 and 2, the resulting hash value is fixed (once directly and once indirectly due to a fixed element as input to the hash function). In No. 3 however, you just have to find two elements with the same hash value. So you start by hashing two elements and the hash value has $n$ bits. The chance that they are equal is $1/2^n$. Now you hash a third value. The probability that it is equal to either the first or second value is $2\cdot(1/2^n)=1/2^{n-1}$, the next element has a chance of $3\cdot(1/2^n)\approx 1/2^{n-1.6}$, and so on.

In average (and this is a very rough estimate) you can find a collision after $2^{n/2}$ hashed values. For No.1 and No.2, you need to test in average $2^{n-1}$  values.

Btw, No.1 is (first) preimage resistance and No.2 is second preimage resistance. The difference between these two is less obvious, but you can create toy examples with preimage resistance but no 2nd preimage resistance. For example:

Why doesn't preimage resistance imply the second preimage resistance?

Pre-image resistant but not 2nd pre-image resistant?

The second thread also lists a function which is 2nd preimage resistant but not fully preimage resistant, but that is a very specific example and probably goes too far for your questions.


Can a document contain its own hash? Do any methods exist whereby a "hash" can be embedded in the "document" it hashes?

What I mean is this. Say I have a given plaintext T. I wonder if there is a method to craft (i.e. not discover as a fluke) a "document" D being some combination  (e.g. a concatenation) of T and a hashvalue h, where h is H(D), H being some hash function.

Perhaps a simpler way of phrasing this is: Is there any way to make a document contain its own hash, under the constraint that the document must, apart from its own hash, contain a given plaintext?

Is this possible in theory? In practice?

This question is somewhat different from this one, in that I am assuming a given plaintext T, whereas that question asks if any T can be crafted (or found).

It actually depends on what you consider a hash function.

If we take a CRC (Cyclic Redundancy Check) as our hash function, then it is quite feasible; a CRC has a property that every output bit is a linear (affine if the initial state is nonzero, but the difference is unimportant) function of the input bits; hence we can generate a set of linear equations over the various bits of X in the expression $CRC( Message || X || MoreMessage ) = X$, and attempt to solve that (and find the solutions, if any).

I would further note that CRC does meet the criteria you gave; it can potentially have a large range (just make the CRC state large enough), and at first glance, if you just look at inputs and outputs, it does appear random.

Of course, a CRC is not a secure hash function; however you didn't specify a secure hash function.


Can we replace the XOR operation in DES with some other operation? Can we replace the XOR operation in the DES algorithm with some other operation? If so, does it work for both encryption and decryption?

Within the DES block cipher itself, the XOR operation is used at two different places:

On the input of S-boxes, XOR-ing 48 bits per round: 48 bits from a subkey (extracted from the 56-bit key), and 48 bits that are the output of expansion E. The 48-bit result forms the eight 6-bit inputs of the S-boxes.
On the output of S-boxes, XOR-ing 32 bits per round: 32 bits from the former (left) half of the state, and 32 bits formed by the eight 4-bit outputs of the S-boxes. The 32-bit result forms the new (right) half of the state.

If in 1 XOR is replaced by addition modulo 248 (or eight additions modulo 26), in both encryption and decryption, the cipher remains operative, in the sense that decryption remains the reverse of encryption. For something comparable in 2, XOR can be replaced with addition modulo 232 (or eight additions modulo 24) during encryption, and subtraction during decryption (with the negated input being the output of S-boxes). For interoperability, such changes would need to define unambiguously the limits and ordering of input and output bits.

Any of these changes would remove one notable property of DES: the complementation property, stating that $\operatorname{DES}_\overline K(\overline P)=\overline{\operatorname{DES}_K(P)}$. Depending on context, that could be neutral (e.g. with any bit in plaintext fixed), a benefit (e.g. adding one bit of resistance to brute force), or a disaster (e.g. when the complementation property is part of a strategy against side channel attacks).

These changes would potentially slow down implementations of DES, both in hardware (due to carry propagation) and software (by breaking common optimizations).

The impact on security is debatable. Only one thing is obvious: the S-boxes have been carefully designed in a context with XOR for near-optimal resistance to differential cryptanalysis (and later found fair against other attacks), thus we'd be moving into uncharted territory. Resistance against side-channel attacks could be lessened, even without consideration for the lost complementation property. I would be surprised if practical security was otherwise lessened under the assumption of a single unknown key, but would not bet on related-key attacks, or firmly commit on anything.

All in all, I see no good rationale for such change.


How to configure Argon2d for commodity hardware? You may already have heard it: KeePass v2.35 has support for a new database format (KDBX4) which allows for the use of Argon2 (more precisely: Argon2d) as the password-based key derivation function (PBKDF).

However Argon2 has three independent parameters, called iteration count, memory usage and parallelism in the GUI. Furthermore it offers to measure how many iterations it can squeeze into one second. But if you "just" hit the button for this it's gonna use 1MB and a parellelism value of 2.

So my question: Is "just" adjusting the iteration count the best strategy to get the most security out of Argon2 or is there a better approach?

OK, so here's the more concrete situation for which the best strategy is searched: An x86 architecture PC, with basically unlimited amounts of RAM (let's just take 4GB+ as an approximation of unlimited), with a very limited number of parallel cores and with a very "tight" time budget of up to 1 second.
Now for the definition of the term "best": Given the above scenario the best strategy for parameter-selection is the one that allows for the biggest hurden on an GPU- / FPGA- / ASIC- based (in terms of the time-area-product) attacker while fitting the constraints.
As this is also intended as a ressource for persons without much of a crypto background, please keep possible strategies as concrete as possible.

The first thing to note is that KeePass uses Argon2d which is the Argon2-variant with data-dependent memory access.

Now it's best to (roughly) follow the guidelines lined out in the Argon2 specification (RFC draft):

Figure out the maximum number h of threads that can be initiated by each call to Argon2._ This means you should set the parallelism value to match your physical core count, ie 2 if you have a dual-core, 4 if you have a quad-core, ... You should double this value if you have (true) hyper-threading enabled on your CPU.
Optional: If you want to use the key-derivation on a lower power device (such as your phone), you need to figure out first how much RAM it has available during average use. This will be your upper limit for memory usage.
Optional: If you have less than 8GB of RAM on your machine, figure out how much is available during average use. The minimal value of this and the previous point will be the upper bound for memory.
Pick an iteration count between 1 and maybe 5. The higher you pick the harder it is for an attacker to reduce the memory required. Analysis suggests that low, single digit values are good, but going slightly higher should increase the penalty when trying to reduce memory usage. But do not higher this value indefinitely because while it would increase the penalties for reducing memory for an attacker, it could very well make the difference between you using 25MB and 500MB of memory and 500MB with "medium" penalties for reduction is likely going to be much worse for an attacker than 25MB with "high" penalties for reduction.
Figure out the actual memory usage parameter. To do this you pick a rather low value like 100MB or a tenth of your maximal budget and test how long it takes. If it takes not long enough increase the memory usage. The used time will roughly scale linear with the memory usage, that is, if you double the memory usage, you will get a doubled time. You want to tweak this time value to your liking, but about 1 second is recommended for disk-encryption or password databases.
If you hit the maximal memory budget, don't go over it (thinks will end badly), but rather increase the iteration count now. Also note here that the used time will scale linear with the iteration count, that is, double the iteration count and it will take about twice as long.

Overall your parameters should take maybe one second for the computation on your intended usage machine where you have to unlock the database often.

So…

TL;DR:

Set the parallelism to your thread count (double the core count if you have hyperthreading), set the iteration count in the range 1-5 and set the memory usage as high as you can while staying within your time and memory budget.

thanks to axapaxa for pointing out that the thread count should be used.
thanks to Luis Casillas for pointing me to the RFC draft and making me improve this answer.


Does every language's SHA256 implementation provide different result for the same value Probably this is very naive question, based on lack of understanding but I was watching a video from Andreas M. Antonopoulos about blockchain, bitcoin and consensus algorithms and he asked for the SHA-256 output of the string Hello!. A guy told him the first few characters, and being Windows/C# dev I decided just for fun to check the answer implementing this very simple C# method:

    public byte[] Generate(string valueToHash)
    {
        byte[] hashValue;
        byte[] stringToBytes = Encoding.ASCII.GetBytes(valueToHash);

        using (SHA256 hashGenerator = SHA256.Create())
        {
            hashValue = hashGenerator.ComputeHash(stringToBytes);
        }

        return hashValue;
    }

and then output the result using this method:

    public static void PrintByteArray(byte[] array)
    {
        for (int i = 0; i < array.Length; i++)
        {
            Console.Write($"{array[i]:X2}");
            if ((i % 4) == 3) Console.Write(" ");
        }
        Console.WriteLine();
    }

But I got a different result.

I remember in the past that there were sites which were storing a huge databases of hashes and the actual value to produce them and back then it was possible to paste the hash value and if it's something common you will get the actual string. This got me to think that no matter what language/Os you are using, a value hashed with SHA-256 for example would produce the same result. However it seems that this is not entirely the case. The guy from the video who provided the answer turned out (from the comments) to use a Mac machine, so what exactly is causing the SHA-256 to produce different outputs for the same input? Is it the OS, is it the programming language? Maybe I've made mistake in my simple code?

Yes, SHA-256 is defined to give the same output for the same input byte sequence on every platform.  However, by design, even the smallest change in the input will change the output into something completely different.  So the most likely reason for the discrepancy you observed is that the input you used is not actually the same as the original input from the video.

Some possible causes for this discrepancy might include:

An extra null byte at the end of one of the inputs.
An extra newline or space at the end of one of the inputs.
A difference in the encoding of newlines (if the string contains one).
A difference in the capitalization of one of the letters (e.g. hello vs. Hello).
A difference in punctuation (e.g. Hello! vs. Hello. or "Hello!").
A difference in the character encoding used to encode the string as a sequence of bytes (unlikely for a plain ASCII string like Hello!, since most commonly used character encodings today are extensions of ASCII, but possible e.g. if one string was encoded as UTF-16).


Are there any simple and yet secure encryption algorithms? Being very new to C++ and cryptography, I finally managed to implement a version of the Vinegere algorithm. I would like to try something a bit more complicated. I have looked at AES and DES and others like them, but I was wondering if there is something simpler. Something that might use some of the same basic ideas as AES, but is much simpler. Some kind of block cipher maybe?

So I am asking for suggestions for a block cipher that is much simpler than AES, but more complex than a basic substitution algorithm. I have by the way looked into the method used in the Enigma-machines, but from what I understand they do "basically" the same as Vigenere.

A simple block cipher would be Threefish (p. 11-13). It's a bit more complicated than RC4 or RC5 yet doesn't drive you insane with seemingly random design choices. It is presumably secure and was designed by experts but has not yet been reviewed extensively, so it shouldn't be used in sensitive applications yet (consider it an exercise).

You'll be able to implement the key schedule and the encryption/decryption functions, and if you use the PDF I linked above, it will be an excellent exercise in following a specification.

If anything, it's the technical details surrounding the implementations that can take you forever to fix, such as endianness concerns in particular (this isn't too much of a hassle for block ciphers but it did get in my way a few times when implementing hash functions).

PS: same name lol


Explanation of each of the parameters used in ECC I'm having a very difficult time finding a clear explanation of the parameters used elliptic curve cryptography. I know for certain that $p$ is the number or order or whatever of the given field that a particular curve uses. I know that $k$ is what is used as the secret key and that $Q=(Q_x,Q_y)$ is the public key. But playing around on these two pages and seeing the contents of this file have left me more confused. What is the importance of $P$ and how does it differ from $Q$? Do $a$ and $b$ change depending on the key in question or are they held constant for a curve? What is the function of $n$? It always seems to be slightly less in value than $p$. How do $G$, the order of the curve, and the seed fit in?

Finally, how is a number encrypted? Is it done by multiplying $Q$? And how can I extract the coordinates of Q from its "compact" form used in certficates?

I know that k is what is used as the secret key and that $Q=(Q_x,Q_y)$ is the public key. But playing around on these two pages and seeing the contents of this file have letft me more confused. What is the importance of $P$ and how does it differ from $Q$?

Don't get too caught up with variable names. People usually use $P$ and $Q$ to represent points in general. There's really no notation that says $Q$ is always the public key.

The contents of that github file are parameters for Dual EC DRBG, which uses two points $P$ and $Q$, which are related. They're not public keys (atleast in the typical sense).

  Do a and b change depending on the key in question or are they held constant for a curve?

No. $a$, $b$, and $p$ define the curve and do not change.

  What is the function of n? It always seems to be slightly less in value than p. How do G, the order of the curve, and the seed fit in?

$n$ is the order of the point $G$. Simply put, it's the number of possible points you can generate through multiplication of $G$.

The private key $k$ is $1 \lt k \lt n$. If $k \geq n$ then it's effectively $k \mod n$. So another way to look at $n$ is the number of possible private keys. That's why when we generate curve parameters we want good parameters that give us a large $n$.

The seed is simply the seed for the random number generate that generated the parameters. This is used to show that the numbers were actually generated randomly.

  Finally, how is a number encrypted? Is it done by multiplying Q?

ECC isn't like RSA where you can encrypt a number directly. For encrypting with ECC you basically do half a key exchange by generating a shared secret using the sender's private key and the recipients public key. The sender encrypts the message using this shared secret. The recipient can reconstruct the shared secret key using their private key and the sender's public key, and can decrypt the message.

One common method is ECIES.

  And how can I extract the coordinates of Q from its "compact" form used in certficates?

A coordinate in compressed form will be the $X$ value, a value indicating whether to use the positive or negative $Y$ value. You just need to plug the $X$ value into the equation $Y = \sqrt{x^{3} + ax + b}$. There are algorithms to compute square roots $\mod p$.


Encrypt than MAC scheme for Home Security system Developing a wireless home security system based on STM32M0 µcontroller, I'm currently looking for the best way to manage encryption/authentication.
For information, the STM32M0 has an AES hardware acceleration module with main modes.

So , I looked first for AES-GCM as AEAD, but there's too much overhead: my data is about 16 bytes , maybe 4 of additional data, and there's 12 bytes IV, and 16 bytes Tag.
I want to avoid that IV / Nonce to reduce frame size.

So here's the intended scheme:

Encrypt plaintext (that contains a UNIQUE 32bits counter for frames) using AES.
Append additional data without encrypt it
Use a MAC without IV/nonce (like CHASKEY, optimized for embedded)

This way I have to use 2 keys , one for AES and one for the MAC. I guess the second can be derivated from the first.

Is this scheme is secure enough for the purpose ?

my data is about 16 bytes , maybe 4 of additional data, and there's
  12 bytes IV, and 16 bytes Tag. I want to avoid that IV / Nonce to
  reduce frame size.

  Encrypt plaintext (that contains a UNIQUE 32bits counter for frames)
  using AES.

So this means that you already have a 32-bit unique value per-message. If you can guarantee it to be unique across all messages under any specific key, then you can use these 32 unique bits, padded with 0s to 96 bits as your IV for AES-GCM. Or you can construct the IV as your 32-bit unique value + 64 bit of randomness per message, which is transferred explicitely.

If you want to optimize even further (at the cost of security, mind you!), you could use a mode that allows tag truncation (do not truncate AES-GCM tags!), such as AES-CCM. There you would use a similar IV setup as above and additionally you could truncate a few bytes of the authentication tag. The calculation is simple: Let $r$ be the maximal risk you are willing to take that a forged message slips through. Let $e$ be the maximal number of times you output "invalid" for a given key on invalid ciphertexts. Then your tag should have length $l$ at least $l\geq \log_2(e/r)$ (this does not apply to AES-GCM). For more information, have a look at appendix B of NIST SP800-38C (PDF).


encrypt rsa + sign it I cannot quite grasp my head around this

Basically, RSA encrypts by having public key (e, n) and private key (d, p, q) Where n = pq

Signatures are done by: Signed = Message^d mod n Hence, to verify you would do Signed^e mod n = Message

You would get the Message. How do you encrypt the message and have a signature at the same time? What am I missing..? I know you would hash the message, but then again. How would you hash the message?

I want to encrypt the message, but if I send over the Signature, the attacker can simply reverse the signature to find out what the message is.... no?

You have correctly identified why the stupid ‘do you even RSA, bro‽’ cryptosystem is trivially vulnerable to forgery and/or decryption by an adversary if you naively use the same key for naive encryption and naive signature—although it doesn't apply in a single instance: you use your private key to sign a ‘message’, and your friend's public key to encrypt it.  But if someone can get you to sign a ‘message’ which is actually an encrypted message to you, they have just got you to decrypt the message for them.

This is why nobody in their right mind who takes the time to listen to cryptographers actually uses this stupid cryptosystem.  Unfortunately, many textbook authors document this stupid cryptosystem and call it ‘RSA’ and leave it at that.  This is why some people use the insufficiently derisive term ‘textbook RSA’.

What you should do instead is use independent keys for RSA-based signature and encryption, and use them in sensible RSA-based cryptosystems.

The post I linked to summarizes some alternative modern RSA-based cryptosystems.  In another answer, I summarized in simple terms a modern RSA-based signature scheme called RSA-FDH.

These may even be safe to use with the same key, as long as you choose independent hash functions for the signature scheme and for the signature scheme—however, I'm not aware of a security reduction to the RSA problem for the use of the same key in any pair of sensible RSA-based encryption scheme and signature scheme.  So I recommend using independent keys, just to be on the safe side.

Or don't use RSA at all, because securely composing signature and encryption into authenticated-encryption is hard (archived), and additionally leaks verifiability to third parties, which may or may not be what you want.  Instead, consider using a NaCl crypto_box_curve25519xsalsa20poly1305.