How difficult is it to guess a salt based on a hash and known plain text? I have the following use case:

Alice owns the domain alice.com and Bob owns bob.com.
I want to users to create a hash for themselves and a specific service e.g. facebook.com or twitter.com. The environment is a client side only application , no servers involved. Therefore each user owns a unique random string that is generated once, stored locally at the user's device and intended to be used as a salt. The goal is to have unique hashes for each user tied to a service without an attacker being able to guess the hash of a user on a specific other service. The hash is intended to be the local part of a catch-all email address.

Alice's generated email address for facebook.com: tcpcAwdfMGw5S22/98avSvqrO8vyEefLGRpmu5zHWKw@alice.com

A pseudo-code example with argon2 as hashing function would look like this:
argon2.hash("<service>+<user-domain>", {salt: <user-salt>}) -> hash

A concrete example for Alice, her domain and facebook would be:
argon2.hash("facebook.com+alice.com", {salt: <SaltOfAlice>}) -> tcpcAwdfMGw5S22/98avSvqrO8vyEefLGRpmu5zHWKw

Please note, that there is no actual password to be hashed, just a string consisting of the service's domain and the user's domain. Argon2 is alienated to generate a hash based on this string where the salt is the actual secret part.

This leaves us with a table of users, services, personal domains and hashes.

User     Domain         Service         Hashed Mail
-----------------------------------------------------------------------------------
Alice    alice.com      facebook.com    tcpcAwdfMGw5S22/98avSvqrO8vyEefLGRpmu5zHWKw@alice.com
Alice    alice.com      twitter.com     yQYCTrtMbQCq1ufLGCJAsc+Y1SIIYR7rC7Cbgp6e2IA@alice.com
Bob      bob.com        facebook.com    B+sKf7kXTH13tfj8ueZdmnTIpWRYCUYeNyQzFFx0jWs@bob.com
Bob      bob.com        twitter.com     /EIqXNIG/orOcQfYz/j1IYWTIRvTAoXJ4Di8cESsXwg@bob.com

These hashes are going to be publicly accessible. So when an attacker obtains a list of hashes of Alice and the associated services (facebook.com, twitter.com, etc) and her own domain (alice.com) would the attacker be able to extract the salt?

The attacker should not be able to guess Alice's hashed email address for a new service (e.g. stackexchange.com).

Is this guaranteed even when each user always uses the same salt and the salts are kept private?

It seems you are looking for a good way to creating different "passwords" from a user specific secret. For that you do not need a password hash, you can use a common key based KDF, assuming that your secret has the properties of a symmetric key.

In that case the secret should take the place of the secret key or password, not the hash. The information on the service and domain should then be part of the "other information" or, if you are dead-bound on using a password hash, the salt. The password hash would be needed if it would be too easy for an adversary to guess the secret otherwise, but note that it only gives you a small, constant size amount of protection against offline guessing attacks.

To do this you should probably prefix the byte-encoded values with the size in bytes, to make sure there is only one possible encoding for both values together. It could make sense to first hash the service and domain with a secure hash (SHA-256) if they are larger, because algorithms may not have been designed for a large info-field or salt - the CPU may otherwise be dependent on the encoded size.

So you would get something like:

$$\text{info} = \text{Encode}(\text{service}, \text{domain})$$
$$\text{passwordBits} = \text{KDF}(\text{secret}, \text{info}, \text{passwordSizeInBits})$$
$$\text{password} = \text{Format}(\text{passwordFormatting}, \text{passwordBits})$$

or, if you take into the hashing of the info:

$$\text{info} = \text{Hash}(\text{Encode}(\text{service}, \text{domain}))$$

It is generally possible to include a random salt as well to the KDF. This makes it possible to create a slightly more secure result, at the obvious expense of complexity of the function and additional storage in your table.

I'd also store the $\text{passwordFormatting}$ string in your table of course. Different services will accept differently formatted password strings, even in 2019. You could mimic/copy the password formatting from an open source password manager, where the password is generated from a random value. Check the license first of course.

A very simple formatting scheme that doesn't require a formatting scheme is base64url. Many sites would allow that if you don't make your password - and therefore the size of the password in bits - too large.

The password size in bits of course depends on how much bits you require for your password formatting. It can be too large, e.g. 128 bits, and then you can toss away the bits you don't require during the formatting / base conversion / whatever to create a password.

Good key based KDF's (KBKDF's) are HKDF, but you might also use ANS X9.63 KDF as KDF if none are available to you - that's probably the easiest one to implement.

Below is a more generic explanation on how a password hash should be used:

  The goal is to have unique hashes for each user at each service without an attacker being able to guess the hash of a user on a specific other service.

No. The main goal is to keep the password secret (and to verify it when using it in the correct use case, of course). That identical hashes leak information or even the password is the reason for the salt. That the hashes are unique is a means to an end, in other words.

  This leaves us with a table of users, services, personal domains and hashes.

Commonly these tables also include the salt, for instance by including it into the password hash. The salt is not kept secret; it would require you to keep a secret value for each user. If that would be possible then you might not need the password hash in the first place; you could just compare the password to one in secure storage.

I would certainly also store something like a version indicator that represents the number of iterations, password derivation function etc. in use, so you can upgrade the entries (one by one) when this is required.

  The attacker should not be able to guess Alice's hash for a new service (e.g. stackexchange.com).

This part is not applicable to the question above

You cannot login with the hash on a service; you need the password and that is converted to a password hash by the service. If you enter the password hash it would calculate the password hash over the password hash and the login should fail (unless the implementers have made a huge implementation mistake). Again, protecting the hash is not the goal; the password needs to be protected.

  Is this guaranteed even when each user always uses the same salt and the salts are kept private?

Well, yes, if there is a secret part within the input parameters of the password hash, and if this secret is one of the parts that is hashed, and if that secret has enough entropy then it would become impossible to calculate the password hash.

However, as explained above, it doesn't make much sense to keep the salt secret.

What is sometimes performed is to have a secret available that is made part of the salt. Then the part consists of the secret part and a (usually randomly generated) nonce (which could be used as a salt by itself). This is then called a pepper.

Without this secret value an adversary cannot start offline attacks as it is impossible to check if a password guess is correct without the pepper. However, this pepper is then identical for all (or possibly large groups of) passwords. It is not a salt by itself.

For this specific problem, I'd use the scheme written down at the start of the answer instead of using a password hash with a pepper


Use Cases of Otway Rees key exchange protocol I am working on an seminar paper regarding key exchange protocols. Of course my first choice of protocol was DH. Second, I choose Otway Rees protocol since I found it very interesting that there is not much literature existing.

So I did a little bit of research and have some basic knowledge regarding OR-protocol. I thing I somehow couldn't find were applications / use cases of Utway-Rees.

In literature they are talking about that its used for parties to agree on a secret key using TTP in unsafe networks and that its a common thing for VPNs. But one thing I am still missing is: where is implemented? Does it have some applications in TLS/SSL, or IPSec?

No, because the protocol is not secure against replay attacks.

In general, this is much closer to Kerberos (secure and state-of-the-art) or Needham-Schroeder (not secure either) than Diffie-Hellman key exchange, which does not rely on a trusted server. (Note DH alone is also not secure, you need an authenticated variant).

That is probably the reason why you didn't find that much information on the protocol, why there are no common standard references and why it isn't used in cryptographic standards. In any case, Kerberos provides the same functionality with better security properties and it is already widely used.


The purpose of the checksum is to detect a change of the configuration (e.g. change of serial number by constant device type). In the case of the serial number only single bits can change.

Actually, the birthday problem does not really apply to CRC; CRC doesn't act like a random function.

For your purposes, it acts better than a random function.  CRC-32 has the property that, if a change you make is limited to 4 consecutive bytes, the resulting CRC will always change.

Hence, if the only change in the configuration is a change to a single 4 byte serial number (and everything else is the same), then CRC-32 will always detect the change (and this remains true even if you change more than one bit of the serial number).

Of course, if additional things change within the configuration (e.g. if two serial numbers are changed), then this need not be true.


How to defend AES against chosen-plaintext attack? I have a server which encrypts files with the same AES key. Users can upload a file and download its encrypted version. A user can upload as many files as he wants. Users can decrypt the documents via the server after a D date. A user may see an other user's encrypted document, but it would be a disaster if he could decrypt it before the D date!

I've read in other stack overflow post that using the same initialization vector can make chosen-plaintext attack easy. So I want to generate a different initialization vector for every uploaded file. Is it a standard secure way to add this IV to the encrypted document?

My first idea is that I encrypt it with a different AES key and simply concat it to the encrypted byte array. But I'd rather use a more standard solution for this problem.

TL;DR: AES is safe against plain-text attacks.

If :

you do not reuse your IV
your IV are random
you use a correct mode of operation (not ECB...)

Then you are safe against such attacks (you need at least these 3 conditions to be met).

On a side note, IV can be public, it is not a problem.

Worth reading:

Why is CBC with predictable IV considered insecure against chosen-plaintext attack?
Why is AES resistant to known-plaintext attacks?
What is the difference between known-plaintext attack and chosen-plaintext attack?


blockcipher-based MACs with variable length that are UF-CMA secure? There are may papers and notes explain why CBC-MAC is only UF-CMA secure for fix length messages. Are there any other blockcipher-based (blockcipher and hash combined included) MACs that is UF-CMA secure with variable length messages?

Are there any other blockcipher-based (blockcipher and hash combined included) MACs that is UF-CMA secure with variable length messages?

Sure.
The most famous one is probably CMAC (a.k.a. OMAC1) which is essentially CBC-MAC but with a key-dependent secret random value XOR'ed with the last message block1.
Alternatively there is a general theorem that $F_k(H_\kappa(m))$ is a PRF (and thus a secure MAC) as long as $F$ is a secure fixed-length PRF and $H$ is a collision-resistant (potentially-keyed) hash function. You can find a proof of this e.g. in the Boneh-Shoup book (section 7). This e.g. brings the (parts of) the security proofs for HMAC and PMAC. Additionally you can somewhat easily define MACs based on this, e.g. $\operatorname{AES}_{k_1}(\operatorname{GHASH}_{k_2}(m\|\operatorname{len}(m)))$.

1: This is an accurate enough simplification of CMAC. It actually uses more than one such random value for messages that are not a multiple of the block length


Mapping a value $g^x \bmod p$ to a small interval $[1...H]$ My question is in $\mathbb{Z}_p^{*}$ context, where $p=q\cdot k+1$ for two primes $p,q$ and $k \in \mathbb{Z}$; $g$ is the generator of the subgroup $G_q$ of $\mathbb{Z}_p^{*}$, of order $q$.

Let's consider a small $H$ (e.g. $H=1024$) and a specific $h \in \mathbb{Z}_p$, with $0 < h < H$, and we randomly choose $g \in \mathbb{Z}_q$: is it true (I hope it is) that it is easy to find a $x$ such that $h \equiv (g^x \bmod p) \bmod H$?

My concern is: is it possible to create a mapping from a randomly chosen $g^x \bmod p$ that can be mapped to a target (desired) value $h$ in a small range, such that we can find it easily, e.g., in $\mathcal{O}(H)$?

Just sample a random $x$, and $[(g^x \bmod p) \bmod H]$ will equal your target value $h$ with probability $1/H$. After trying $O(H)$ candidates you will find a preimage.

Fine print: Technically speaking, the probability isn't exactly $1/H$. Each $h \in \mathbb{Z}_H$ has either $\lfloor \frac{p-1}{H} \rfloor$ or $\lceil \frac{p-1}{H} \rceil$ preimages under the mapping $a \in \mathbb{Z}^*_p \mapsto (a \bmod H)$. So the probability of hitting your target $h$, when you choose a random $a \in \mathbb{Z}_p^*$, is $\lfloor \frac{p-1}{H} \rfloor/(p-1)$ for some $h$'s and $\lceil \frac{p-1}{H} \rceil/(p-1)$ for others. But if $p$ is exponentially large (as I suspect it is here since you're talking about discrete logs), then this probability is negligibly close to $1/H$.


Do any (non-hardware) RNGs exist which could be used to create an OTP for crypto purposes? I've stumbled (jobwise) over a system where small messages (512 Bytes or less) are encrypted and decrypted using a simple XOR using a OTP. That OTP is created using a seed based on the individual user passwords and a simple PRNG.

I'm currently seeing the following problem: Alice always keeps her password absolutely secret and it is never shared or transmitted. But the crypto-message may be intercepted by Eve, who may be smart enough to detect the pattern used to XOR the message (as the PRNG functionality is widely used as simple C-lib rand() functionality and therefore publicly available).

The reason why "they" used the OPT approach is to ensure "speedy encryption" (before transmission via SSL, secured storage, etc.).

My counter-argument is that it may be speedy, but because the seed is generated using a simple byte-addition (which results in a seed between 0 and 255), Eve has pretty good chances to quickly find the used seed and thereby the PRNG offset... which will allow her to decrypt the complete crypto-message(s) within 256 trail-and-error approaches.

Personally, I am about to advise them to use an acknowledged crypto-scheme (like AES) and make them drop their weak and insecure OTP-based crypto thing.

For as long as I can remember, I have been reading and have been told that an OTP may be regarded to be theoretically secure — but for that, the OTPs must be absolutely and truly random. From my point of view, a PRNG (cryptographically secure or not) does not seem to be a secure way to generate an OTP for crypto-purposes (using simple XOR).

But this got me thinking — maybe I am missing something in the big sea of crypto-schemes, functions, and implementations.

To avoid I'm missing something, I would embrace any feedback on the question:

Do any (non-hardware) RNGs exist which could be used (or securely abused) to create an OTP for crypto purposes?

The system you describe is not a one-time pad, it is a stream cipher, and a bad one for that.

A one time pad has real (truly) random bits in the XOR pad, which are never reused for two messages. "Their" cipher has a pseudorandom pad (with non-crypto PRNG), and if I understand right, even the same one for each message.

Even a real random one-time-pad is vulnerable if the same key is used twice (or more often) for different messages (or the same message, if you don't want the attacker to know that it is the same message).

Even if you use a good stream cipher (or PRNG), and use different "passwords" (i.e. keys) for each message (or use a stream cipher with an IV input, and use different IVs for each message), you don't get the perfect security guarantees of an one-time pad – it can be brute-forced, with effort depending on the key size.

For a system to have the security guarantees of an OTP, you need key entropy of at least as much as the message length.

If you have such keying material, but not in a form suitable for direct use as a key (e.g. not equi-distributed, like a really really long passphrase), you might be able to pre-process it using some crypto functions like a hash functions, to transform it into a form usable for an OTP key. Though the transformation algorithm must be studied to make sure that enough entropy stays – for your OTP you need your $n$-bit output to have $n$ bits of entropy, which is not that easy using hash functions with internal state size $< n$.

Actually, most hardware PRNGs work that way – they measure some data and use it as entropy input to a crypto-PRNG.


standard way to authenticate parties with public keys without certificates Is there some standard protocol for mutual authentication of two parties when there is possibility to use public key cryptography? The problem is that two parties can use public key cryptography but public keys are not embedded within any kind of certificates. Is there a way to avoid MITM attacks? Simple use of public keys for authentication does not solve the problem of MITM attack (I would have to be sure about public key authenticity first). If I understand correctly FIPS 196 requires usage of authenticated keys so this is no solution.
Is it possible? If there is no previous communication and no certificates then how would it be possible for Alice and Bob to recognize that there is Eve trying to do something nasty?
And if there would be possibility for Alice to verify the fingerprint of Bob's public key that would be possible? Is there some standard protocol for this?

Without an out-of-band channel, no.

If all Alice has only a public key , she can't tell the difference between Bob's key and Mallory's.  Hence Mallory can mount a man in the middle attack.

To prevent this you either need a certificate or a a trusted  out of band channel though which you conform the key. The channel could be something that is harder to man in the middle ( e.g. the phone network) which you use to exchange key fingerprints, it could be an in person meeting(some people of pgp fingerprints on their business cards), or it could be that you remember the key from the last time you connected ( which only prevents subsequent man in the middle attacks)

A somewhat novel  application of this is used the ZRTP key agreement protocol used in VOIP.
ZRTP generates a short authentication string(SAS) based on the user's keys.  Bob can read that SAS to Alice and assuming Mallory can't forge Bob's voice in realtime, the channel is secure and the key is authenticated.


How did this group discover m wasn't random? In this video a group of "hackers" describe how they discovered private keys for the PS3 that was using this ECDSA algorithm by discovering that the "random" integer $m$ (or $k$ in the wiki link) was actually static, allowing the private key to be solved for. The attack is actually mentioned in the wiki link for the algorithm, and basically says the same thing as the video.
My question is, how did they discover $m$ was static, and how did they even know that particular ECDSA algorithm was used to generate the private key? Even once they knew these two things, wouldn't they need the particular curve sony used?

Per the notation of the wiki article, all signatures produced with the same random k would lead to the same value r which is published as part of the signature.


is there a way to specify the encrypted message length when using private and public keys? is there a way to specify the encrypted message length when using private and public keys? mainly I want the encrypted message to be 32 bytes? as I'm currently using RSA but that results in a length that is equal to the modulus Length.

Asymmetric cryptography are never space-efficient.

For example, in multivariate cryptography the public key is often the expanded matrix of coefficients of indeterminates, where as the private key are decomposed transformations allowing efficient decryption/signing. Although you can get ciphertext/signature size not too different from plaintext/hash size in multivariate schemes, the public key size is almost always huge.

The reason I bring up multivariate cryptography is 1) it's secure against quantum computers (as far as we know). 2) it's space efficient with ciphertext and plaintext as you've requested (but not with key sizes). and 3) it's a good illustrative comparison with symmetric-key cryptography.

Remember XSL attack? It fails catastrophically because accumulated rounds of AES permutations expands to high-degree multivariate expression of its inputs.

To summarize: You can specify ciphertext size with multivariate cryptography if you have the right scheme. But you loose the ability to specify public-key size there.

You can keep an eye on NIST PQC standardization, where there are some multivariate contenders. But keep in mind, that these schemes are in their earily stages of development.


The challenge c in Sigma protocol (using Fiat Shamir) As is known to all, the following picture depicts a sigma protocol, and to eliminate the interactivity, Prover can generate c by hashing (t, y) using Fiat Shamir transform. My question is:
1). Can c be obtained as hash(0x1234, 0x4321) by the Prover, (where 0x1234, 0x4321 are public parameters at setup)?
2). If above answer is yes, can a same c be used by different Provers at the same time in Fiat Shamir transform?

No. Since 0x1234, 0x4321 is public and thus known ahead of the execution, the prover knows the challenge c before sending t. This violet the requirement of the sigma protocol: c is sent to P after t is received.


Difference with round keys and round constant in AES I am confused with round keys and round constant in AES. Are they the same? Can someone explain it to me?

Round keys are not the same as round constants. A round constant is always the same no matter what the key is. The round keys, however, are an expanded representation of the AES key being used.

For more information, read up on the AES key schedule.


Secure multi-party private set intersectio: Protocols supporting MULTI-party VS supporting TWO-party Let assume party $B$ wants to receive secure multi-party computation (MPC) output.

The are many private set intersection (PSI) protocols that support only two parties but they  cannot support multi-party. In this case, party B needs to run PSI  with  party A. Then B uses the result as the input and runs two-party PSI with party C and, so on. However, this setting leaks more information to client B, than the protocol supporting, multi-party PSI.

Example: let computation be "set intersection"

Assume party A has $S_{A}=\{1,2,3\}$

party B has $S_{B}=\{1,2\}$

party C has $S_{C}=\{2,5\}$

Party B in the protocol only supporting two-party receives:

1- $K=S_A\cap S_B=\{1,2\}$

2- $K'=S_C \cap S_B=\{2\}$

Then, it finds $K\cap K'=\{2\}$. So it learns party A has $1$ but party C does not have $1$.

In contrast, if a protocol could support multi-party client B would only learn intersection of all sets that is $\{2\}$.

Question: What are the real-world applications (examples) of multiple-party PSI?

So I can use the examples  to show/justify that protocol supporting multi-party PSI is better (in terms of security) than those only supporting two-party.

I think that you are mixing between the terms "applications" and "implementation", let me explain.

In your question you took some secure two-party computation (2PC) and you showed that when using it in a "black-box" fashion and also each party gets the result of the computation on each pair of the inputs then the protocol leaks a lot of information that should not be leaked. This is true. But it doesn't mean that a secure multi-party computation (MPC) is useless! It just simply means that the protocol that you described (using 2PC) is leaking information and thus it is not secure!.

This multiparty set intersection is INDEED an application for MPC, it is just not implemented as you said but has some designated protocol that implements it (not necessarily through 2PC).

I hope that it clarifies the things.


Which is faster, PRF based on AES-CTR and PRF based on BLAKE{2,3}? Recently Blake3 has been announced, which can be used as PRF.
I'm wondering which PRF is faster, namely PRF based on Blake3 or the one based on AES-CTR?

As @SEJPM pointed out above, there's no one answer to this question. Everything varies based on what hardware you've got and what the length of your input is. As a first step, I'd start by looking at SUPERCOP performance measurements. You can find AES-CTR measurements at https://bench.cr.yp.to/results-stream.html, and BLAKE3 measurements at https://bench.cr.yp.to/results-hash.html. There's an enormous amount of data in both pages, because there's a lot of different hardware to consider. (And of course, lots of stream ciphers and hash functions to measure.)


Format of hybrid crypto envelope structure? From posts including the accepted answer to

How to encrypt file with RSA and AES that anyone with RSA key can decrypt them?

hybrid crypto (AKA envelope encryption) a GPG-encrypted file has an element that is the symmetric-key-encoded payload and also an element that is the asymmetric-key-encoded symmetric-key.

I need to manually construct such a file using e.g. RSA and symmetric crypto APIs in a legacy system.

(Edited the following to clarify...)
I know from reading up at e.g. https://futureboy.us/pgp.html#Symmetric, https://www.gnupg.org/gph/en/manual/x110.html, https://tools.ietf.org/html/rfc4880 that an OpenPGP message follows this structure.  But is there a good reference with examples having the required structure of a composite GPG-encrypted file?

Does anyone know of resources that include example envelopes of this kind?

First, OpenPGP/GPG is not the only standard for hybrid encryption, often called enveloping. For files/messages there are also PKCS7/CMS and SMIME which are ASN.1 (plus MIME) based, XMLenc which is XML based, and JWE (JSON web encryption) which is JSON based. There are also several communication schemes (at least SSL/TLS, SSH, IPsec/IKE) which are not directly applicable here.

All of these are standards and one of the defining characteristics of a standard is that it is specified in the document(s) that specify the standard. For OpenPGP, the current standard is RFC4880 as could easily found for example in the wikipedia article which is one place someone with any initiative would look. (RFCs -- Internet 'request for comment' documents -- are actually available numerous other ways, which used to be important decades ago before the web. For more about RFCs see the wikipedia article.)

PGP's encrypted-data functionality is introduced/outlined in 2.1 (and 2.4) and recapitulated in 11.3. The core of the document is organized bottom-up: data elements and packet structure are defined in 3 and 4; specific packets are defined in 5 with pk-encrypted-key in 5.1 and old-style encrypted data in 5.7 and the new improved encrypted+MDC-data in 5.13; optional compressed-data is in 5.6 and 'armoring' in 6. Note that PGP uses a not-quite-standard mode of symmetric encryption, described in 5.7 and expanded in 13.9: CFB with IV of zeros but a nonce block prepended (which serves the same security function) and a 2-byte 'stutter' that provides a quick check for wrong key.

The main implementation (now) of OpenPGP is GnuPG which is opensource, but is a pretty big program. For learning only a small piece like this, if you know or are willing to learn Java, I recommend BouncyCastle which is also opensource and (IMHO) well-organized and coded (though not extensively commented) and being Java isn't cluttered by much of the housekeeping code needed in C or even C++. Either of those programs can also be used to create (example) messages for your code to read, or check/verify messages created by your code.

Added: since you are so intent on an example, here is one, using the 'new' (symm+MDC) format preferred by my pretty elderly GPG 2.0.14 so I don't have to bother finding the option(s?) to turn it off:

$ od -tx1 cry64585.enc
0000000 85 01 0c 03 8a 30 13 e2 06 1f b9 42 01 07 fe 22
0000020 1b 8c bd 1b d3 d7 92 72 42 ee 86 aa e6 9b e1 eb
0000040 bb bc 88 b8 48 93 bd 56 28 49 28 77 59 e9 9c 61
0000060 69 06 0a 6c 86 5e d4 c7 48 24 c1 c3 c7 7e ee aa
0000100 e4 e4 08 4d 8b 64 ce 46 3a 91 64 98 52 e1 71 bd
0000120 4f b7 64 c2 9a c0 a4 cd b2 33 6f 41 9f 4d 5d eb
0000140 5a 1d 76 b5 19 5f 11 d4 2e ea 0b 50 04 34 f9 ed
0000160 15 b0 ae 63 6b d4 1d ed 9f 2e c8 6c 4f c3 1a ab
0000200 2a 1b f7 13 39 ac 14 de 30 f7 00 0f ae 61 d7 c4
0000220 c1 cc b2 33 0f fc a8 c7 61 7f a9 f7 23 f7 18 e1
0000240 59 3c b9 a5 5f b6 fe b4 26 65 3e fb 40 43 c3 46
0000260 7d 2b 32 25 6c b7 e3 8d a4 32 fd 69 a9 dd 69 65
0000300 4f 95 55 f8 f9 dc f9 50 e1 4d fe 5c 4e be 68 6d
0000320 8f 4f a8 bb 1a 05 07 05 57 22 51 37 87 2e 54 af
0000340 1a 69 2d c6 af 03 78 9f 6c db 71 e4 38 f5 03 f6
0000360 dc 80 93 63 ce b9 bd 61 d2 7e d0 98 26 15 8c 40
0000400 e9 35 da 60 5c e5 6d 3a c8 5a 26 08 26 69 dc d2
0000420 40 01 8f ce 2c ff 95 a8 65 09 22 5d 2c 40 37 c9
0000440 ac b3 f4 64 f9 72 f1 c7 3c a5 91 46 9d a9 3f 73
0000460 39 9a 8d e2 cb 66 f7 1e a2 19 73 e1 77 e9 ab 0b
0000500 b2 91 96 0c 3d 3b 77 17 25 1d 8f ec 21 f2 0a 53
0000520 5a
0000521

The 0x10f bytes at offset zero are the pk-enc-sk packet (tag 1), and the 0x42 bytes at offset 0x10f = 0417 are the symm-mdc-data packet (tag 18).

As a bonus, here's the public key used to encrypt:

$ od -tx1 cry64585.pub
0000000 99 01 0d 04 59 3b a3 a5 01 08 00 c0 77 a2 45 43
0000020 79 91 7b 7e 7b 88 e3 2f f8 19 5a b0 6a e8 67 87
0000040 56 a3 11 96 d7 fd c5 e2 33 19 f6 9d d5 1a 48 08
0000060 38 29 71 0e 4f 98 56 e9 5d 5c 09 b0 d6 6c 92 51
0000100 33 d4 a5 65 df fd 05 57 e6 ea 32 a4 88 55 01 e4
0000120 9b 27 1e 68 8a 10 45 df 72 26 2c bd 8a d8 04 59
0000140 e7 a1 79 21 90 33 e0 b9 51 48 ab 31 04 7a 3a 61
0000160 a1 88 6a 7f 6b b4 d6 49 3d ae 40 80 f5 33 f0 5f
0000200 1c 7d ad 30 2e a8 e8 3b 24 8f ca a1 54 4c 3e eb
0000220 61 03 78 91 72 dd 36 7d da 3d 92 46 f3 ad 7c 7b
0000240 c7 39 ae f0 4e 51 fd fe dc 09 26 3f 9f b0 24 4d
0000260 f1 d5 aa f0 84 2e 18 77 a7 b2 7d 5c fa d6 2b ae
0000300 f3 55 5a f2 af c2 15 de 82 82 37 14 8f 9b 52 3b
0000320 dd 63 8e 21 53 f2 cb 6b bb 50 bd 0e 08 f6 44 eb
0000340 8a 2f 3f 15 32 1f e3 d4 32 3c 5c 23 dc 30 ea b4
0000360 0c 3e 1a 69 0d 82 6a 74 fc 2c 3e 3d 63 a8 d0 83
0000400 b7 3e 79 3a 0a 60 81 65 e2 94 17 00 11 01 00 01
0000420 b4 13 72 73 61 40 74 65 73 74 20 3c 72 73 61 40
0000440 74 65 73 74 3e 89 01 38 04 13 01 02 00 22 05 02
0000460 59 3b a3 a5 02 1b 03 06 0b 09 08 07 03 02 06 15
0000500 08 02 09 0a 0b 04 16 02 03 01 02 1e 01 02 17 80
0000520 00 0a 09 10 d1 d6 73 c6 3b ed f9 8f e2 e9 07 fd
0000540 1a 85 15 61 d4 af 7f b2 94 95 c3 c2 ca b1 eb 1a
0000560 80 31 cd bd ec 26 78 0f 0b 97 29 85 9e 92 27 1b
0000600 ad 3c 7e 3c 35 eb 59 f9 57 ce 94 9e 13 e4 d1 50
0000620 fd 82 0f 3a 1f e7 75 56 70 e3 40 bf b7 6a 00 5f
0000640 b6 e9 83 f6 ba f1 28 12 4f 10 d5 72 a3 de d1 06
0000660 90 91 b0 dd e0 f7 95 b3 be 94 9b 43 ea 56 86 d7
0000700 d4 c3 6b 66 b4 db ed 07 6a 8e b7 97 72 b2 b2 dc
0000720 b8 db 33 de a9 76 10 7e 81 ae ab f4 19 39 e7 40
0000740 86 d1 32 53 c2 c1 e4 e1 dd e5 fd c5 16 2d 76 8d
0000760 3b 31 3f b7 e4 b8 8f f9 8b 36 ae b3 67 32 6d 40
0001000 83 ee 88 3f 8c ca 63 2c 33 bb 7c 82 04 07 58 d8
0001020 40 5b ec 1a 85 58 32 88 df e0 a8 72 f8 cf 1d f8
0001040 30 86 ad 22 c6 44 17 b7 03 0b e3 f7 a6 d8 43 6c
0001060 39 ea c2 c9 b7 a3 22 09 9b 8b b8 3a ea a6 c2 77
0001100 3d 60 29 9c 4b 02 ea 27 94 b9 77 7a 60 0d af 85
0001120 42 91 7b 0d 02 f9 fc fc 59 81 d5 e4 6b c9 10 45
0001140 b9 01 0d 04 59 3b a3 a5 01 08 00 e4 4c 11 6e 79
0001160 1b 58 da d1 b9 4c c9 6f 4d bd bf ee d8 40 f9 a7
0001200 a1 0f 5d 3e 8d 35 40 d8 36 0f 08 be fd 9d 3a 1a
0001220 13 ea 8d 49 47 1f f1 bc 5a 9a f7 33 ea c8 1f 7a
0001240 41 81 47 52 46 0f 37 7d a6 41 92 ba 2a 4b a0 a5
0001260 dc 83 03 e5 5c 39 3c 96 4a 1a 6e 3c a8 1f 29 8a
0001300 9f 91 10 31 94 f6 e0 d2 b8 c3 e1 60 29 67 d0 26
0001320 13 86 61 17 5d 64 39 4d 00 14 98 1b 67 b8 d8 44
0001340 2e 22 72 a3 25 5c 90 6f 8c 89 a6 3c 97 89 b5 26
0001360 1d 01 2e f5 e5 1b 38 34 63 f7 04 20 2a ce ba 35
0001400 cd 30 f2 91 17 09 a4 e3 d1 ba f9 f6 09 b7 00 ef
0001420 a2 72 76 5b dc 2a c8 10 44 81 84 8a 36 41 79 17
0001440 07 fe 18 6e 79 da ce 3d e1 2d 7d 30 d7 25 31 27
0001460 7b ae 4c 74 d6 17 d4 1b c5 b3 51 61 7d 87 8e 4e
0001500 5a df 43 6a 3d 00 0c 0e 99 dd 98 68 60 b9 87 06
0001520 09 44 36 b7 49 99 56 b8 f3 ce 86 b7 8a 9c 28 e1
0001540 65 82 7a 27 6b 9d e9 ea c7 e8 fd 00 11 01 00 01
0001560 89 01 1f 04 18 01 02 00 09 05 02 59 3b a3 a5 02
0001600 1b 0c 00 0a 09 10 d1 d6 73 c6 3b ed f9 8f 66 8d
0001620 08 00 b4 39 f4 ed ee 3a 2b fe eb 7f 40 8a 22 96
0001640 5e cb af 92 fb f8 70 37 6f e4 84 b1 81 2f 38 05
0001660 f2 28 a9 1a b5 c4 e1 be 3c 3b 64 20 7c 6e 7a a7
0001700 60 b1 3d be 9a e3 7c 8d 61 31 27 f9 a0 e6 a1 e7
0001720 e0 49 12 d4 e5 b2 57 ca ca 51 22 4a 5f 81 0e e0
0001740 a0 c7 41 89 63 01 55 21 23 bf 41 ec 7b 03 d6 7a
0001760 3b e5 8e 80 4e 37 d5 ce be 1e ae f7 a2 7a 8e ec
0002000 b9 64 88 64 dd 1c 36 08 73 7f 0a be e2 7c 48 c9
0002020 ee 8a 9f 72 e7 69 9b 7a ea 4f 4c 0a 21 9a 2e 7c
0002040 5f a6 5f 28 9b 31 b5 b0 fd 46 07 9c 80 9a 24 b4
0002060 86 27 1d 23 12 cb 19 64 aa 4e 40 7f 90 4d f8 c9
0002100 c0 7f b7 c3 93 7f 29 dc df e6 11 4a 5a af 7a 41
0002120 f5 9c cd 17 f7 a2 56 7e b6 3e 80 91 70 e6 9d 3e
0002140 23 55 73 de f4 e7 78 bf 7f ea ed c3 ce ee 4d 77
0002160 05 c7 39 c5 a0 b8 bd 00 ff bf 48 20 e4 89 50 2a
0002200 3c 5d 39 c2 55 53 12 dc 3c be 79 65 55 f6 d6 c4
0002220 65 90
0002222

I don't see how this can possibly help you. If you think you will write a (correct) program that reproduces the above (message) output and compare, that won't work; properly designed encryption, including both the symmetric level and the public-key level (here RSA -- even the outdated RSAES-PKCS1-v1_5 aka block type 2 scheme used by PGP due to its age), is randomized precisely to prevent reproducing it.


Why is synthetic IV (SIV) mode considered deterministic authenticated encryption (DAE)? I was just going over my (old) notes from Coursera's Cryptography I course, and I was puzzled by the description of SIV as providing deterministic authenticated encryption (DAE). The general SIV construction shown is to first compute a MAC over the plaintext using a secure PRF, and then to encrypt the plaintext using a secure block cipher in CTR mode using the MAC tag as the IV and an independent key. The IV and the ciphertext are then output.

As far as I can tell, this is essentially an Encrypt-and-MAC scheme, which would seem to me to be open to the same kinds of chosen ciphertext attacks as SSH? Is there some aspect of SIV that excludes such attacks? Or are such attacks excluded by the definition of deterministic ciphertext integrity?

From http://cseweb.ucsd.edu/~mihir/papers/oem.pdf page 17:

  E&M does not provide INT-CTXT. E&M also fails to provide integrity of ciphertexts. This is because there are secure encryption schemes with the property that a ciphertext can be modified without changing its decryption. When such an encryption scheme is used as the base symmetric encryption scheme, an adversary can query the encryption oracle, modify part of the response, and still submit the result to the verification oracle as a valid ciphertext.

Is this ruled out because SIV is only defined over CTR mode and so excludes such encryption schemes?

The definition of DAE security, as given in Rogaway and Shrimpton's original paper (which both defines the security notion and proves that SIV mode satisfies it), does effectively require that a DAE scheme must protect ciphertext integrity.

Specifically, the definition of DAE security (definition 1 in the paper) says that an encryption scheme is DAE secure if an adversary cannot, with non-negligible advantage, tell whether it is talking to the real encryption and decryption oracle, or to a fake encryption oracle that returns for each distinct query a random bit string of the same length as the real encryption oracle would've returned, and a fake decryption oracle that treats all ciphertexts as invalid, with the limitation that the adversary may not submit strings previously returned by the encryption oracle to the decryption oracle or vice versa.

Crucially, while the definition forbids the adversary from submitting ciphertexts previously returned by the encryption oracle to the decryption oracle (and thereby winning trivially), it does not forbid the adversary from submitting a modified version of a previously obtained valid ciphertext to the decryption oracle.  Thus, if an adversary could modify a valid ciphertext in a way that does not almost certainly render it invalid, they could win the "DAE game" simply by requesting a ciphertext from the encryption oracle, modifying it somehow to obtain another, distinct valid ciphertext, and submitting it to the decryption oracle (which, if the adversary is indeed talking to the real oracles instead of the fake ones, would then successfully decrypt it).

In particular, since the SIV construction only directly verifies plaintext integrity, this implies that, for an SIV-style encryption scheme to be DAE secure according to Rogaway and Shrimpton's definition, the encryption layer must not allow the ciphertext to be modified in a way that leaves the plaintext unchanged.

Fortunately, CTR mode does satisfy this property (as indeed do all length-preserving classical encryption modes, such as OFB, CFB and even CBC with ciphertext stealing).  In particular, a simple counting argument shows that, for any encryption mode where the length of the ciphertext (excluding the IV!) equals the length of the plaintext, no two ciphertexts with the same IV can correspond to the same plaintext.  Thus, for these modes, verifying plaintext integrity is equivalent to verifying ciphertext integrity, assuming that the IV is unchanged.

What remains to be shown is that the adversary also cannot change the synthetic IV (possibly together with the ciphertext) in SIV mode in a way that would not be detected.

Indeed, for plain CTR mode, this would be trivial: given two CTR mode encrypted messages $m_1 = (iv_1, c_1)$ and $m_2 = (iv_2, c_2)$ of the same length, and the corresponding plaintexts $p_1$ and $p_2$, one can construct a new message $m' = (iv_1, c_1 \oplus p_1 \oplus p_2) \notin \{m_1, m_2\}$ that also decrypts to $p_2$.

However, in SIV mode, the IV also serves as the authentication tag for the plaintext.  Thus, in effect, it is not feasible for an adversary to find two plaintexts that would be valid for the same IV, and thus any modification attempts like the one described above will be detected.

Furthermore, the SIV construction requires that the (keyed) function used to derive the synthetic IV must be a PRF.  This is a significantly stronger requirement than merely requiring it to be a forgery-resistant MAC (or even a privacy-preserving one), and essentially requires that an adversary must not be able to find any valid IV / plaintext pairs other than those returned by the encryption oracle.  Thus, for any IVs other than those returned by the oracle, the adversary cannot produce any valid message; and for the IVs that the oracle does return, the adversary only has the single valid plaintext, and thus, due to the length-preserving encryption, only one valid ciphertext.

In short, the key properties that make the Encrypt-and-MAC construction in SIV mode provably DAE secure are that:

the encryption layer is length-preserving (and thus, for each IV, bijective),
the encryption layer IV also serves as the plaintext authentication tag, and
the function used to derive the IV from the plaintext is a PRF.

Ps. For further reading, you may also be interested in the following paper:

Namprempre, Rogaway and Shrimpton. "Reconsidering Generic Composition". Cryptology ePrint Archive, Report 2014/206, 2014.


Difference between one-level and two-level E0 encryption I am trying to understand the practical security implications of the way E0 is used in Bluetooth 2.1 devices. In reading up on the subject, I am seeing that encrypting a large amount of data with E0 when using a single key gives way to practical attacks. Only so-called one-level E0 is vulnerable to this attack. Two-level E0 somehow uses a different encryption key for each frame (with a frame being 2745 bits long), and attacks against two-level E0 require the first few bits of a large number of frames. In order to understand the implications of E0's weakness as used in Bluetooth 2.1, I need to understand the difference between one-level and two-level E0. I have two questions:

Is one-level encryption the act of using a single master key and encrypting all Bluetooth frames with it, and two-level encryption is using a single E0 keystream with a master key to generate temporary per-frame E0 encryption keys?
Does Bluetooth 2.1, which uses HMAC-SHA-256 for key generation, still use two-level encryption? If so, is a master E0 keystream used for generating each E0 frame key, or is HMAC-SHA-256 used instead, making it so the attacks against two-level encryption do not apply to E0 as used by Bluetooth 2.1?

I seem to have found the answers myself:

Two-level E0 uses one instance of the cipher with the master key to generate the internal state for a second instance of the cipher which is then used to encrypt a single frame. I found this out from a slide presentation and a paper describing attacks against two-level E0.
Bluetooth 2.1 does still use two-level E0. HMAC-SHA-256 is only used in combination with P-192 key exchange to derive the master key. Attacks against two-level E0 do apply to 2.1, however the best known attacks require more frames encrypted under a single key than is supported by the protocol. This was made clear in a Security SE answer.


Why are cube and square roots of primes used as SHA constants? Do square or cube roots have properties that make them a better choice over, for example, the primes themselves?  Or is it arbitrary - would random numbers work as effectively?

This is more of a humanist rather than mathematical answer, but the design of a cryptographic primitive cannot be abstracted away from the human condition.

Knowing some research methodology, there will be a great deal of one up manship taking place.  There is a powerful motivation to produce something innovative that acts as a differentiator (marketing wise not cryptographic wise) for your particular work.  The underlying idea of the 'nothing up my sleeve' number is to form a (proven) dissociation between the value of the constant for cryptography and the source of the numbers.  E.g. It is unlikely that the sine wave can have any effect on the behaviour of a hash function**.  Similarly prime numbers are unlikely to have any deleterious effect on mixing rounds.

Clearly a string of zeros might be counter productive, but pi digits are proven as random.  Cube roots of primes are just bravado.  You could just as well use the ASCII values of the names of the planets.  That would    be at least noteworthy and hopefully more inventive than the next designer's constants.  The Million Dollar elliptic curve is probably the most blatant form of such showmanship.

**Note.  It would be interesting as to how close to the 'knuckle' this could be taken.  What if IVs or constants were somehow derived very tightly from powers of two for example?


Why is the rand() function in C not a cryptographic pseudo-random generator? For example, one of the possible rand() implementations：

int rand_r (unsigned int *seed)
{
    unsigned int next = *seed;
    int result;
    next *= 1103515245;
    next += 12345;
    result = (unsigned int) (next / 65536) % 2048;
    next *= 1103515245;
    next += 12345;
    result <<= 10;
    result ^= (unsigned int) (next / 65536) % 1024;
    next *= 1103515245;
    next += 12345;
    result <<= 10;
    result ^= (unsigned int) (next / 65536) % 1024;
    *seed = next;
    return result;
  }

How to proof that it is not a pseudo-random generator?

This is a Pseudo Random Number Generator, but not a Cryptographically Secure PRNG, which requires that the output is undistinguishable from random for one not knowing the initial *seed.

One problem is, the effective state is very small: 27 bits at most (or less, limited by the size of int), because only the 27 low-order bits of the input *seed ever have a chance to influence either result or the low-order 27 bits of the output *seed. That alone limits the generator to 27-bit security, which is not enough (40-bit was already low security down in the 1980's). Also, this small effective state limits the period to $2^{27}$ (about 134 million), which is not enough even for simulation purposes.

Worse, one 31 bit output result is (at least, most likely) enough to easily reconstruct the full state *seed on output and then trivially predict future output, a total disaster for a CSPRNG. One simple method for that is: enumerate the $2^{16}$ possible values of the low 16 bits of next in the line result = (unsigned int) (next / 65536) % 2048;, and deduce the other 11 meaningful bits of next as result>>20; then check that guess of next against the 20 lower bits of result by replicating what the code does. We are down to 16-bit security, and that could be brought further down.

Walking back and computing previous output is trivial, too. The low 27 bits of *seed are transformed by three iterations of the linear $x\mapsto a\;x+b\bmod2^{27}$ with $a=1103515245$ and $b=12345$, giving $x\mapsto y=c\;x+d\bmod2^{27}$ with $c=a^3\bmod2^{27}=8240309$ and $d=117712863$ determined from $x=0$. And that is inverted as $x=e\;y+f$ with $e=c^{-1}\bmod2^{27}=70668701$ and $f=80477501$ determined from $x=0$.


Calculation of AES encryption per second How fast in terms of the number  AES encryption/sec, would an Internet encryptor need to be if the plain text rate is 10gb/sec?

Let us assume a few things:

10 gb/sec means Gb/s, the number of gigabits per second;
we use network notation for Gb/s, which means that 1 Gb consists of 1,000,000,000 bits;
we'll use the minimum of AES blocks to encrypt - this is true for most single pass modes of encryption such as CBC and CTR;
we only use the AES primitive for confidentiality, not message integrity or authenticity (this restriction is lifted in the second part of the answer).

In that case 10 Gb/s is 1.250 GB/s. And as AES encrypts 16 bytes per block, this comes down to 78,125,000 operations per second (ops/s). Depending on the protocol and mode a few operations may be required at the start or end but those are insignificant to the ~78M ops/s.

If AES is also used for message authentication, for instance using AES-CMAC then you should double the amount of ops required.

Authenticated encryption modes based (solely) on AES such as CCM mode and EAX mode are "double pass", which means that two AES block encrypts are required for each block of input.

AES-GCM uses 128 bit modular multiplication during GMAC calculation. It is likely faster than these double pass modes, especially on newer processors with instructions to accelerate the multiplication required for GCM.


Comparison of security definitions for signatures The two main security definitions for signatures are EUF-CMA and the strong version of it sEUF-CMA.

What I see that their difference is that in EUF-CMA experiment, the adversary needs to produce a valid signature for a message of its choosing, where the message has not been queried before (i.e., a message for which the adversary hasn't made queries to the oracle).

Whereas in the sEUF-CMA experiment, similar thing happens, though now the adversary needs to make sure that it hasn't queried the oracle with the forged (message, signature) pair. So, simply the signature also enters into the equation in sEUF-CMA.

The part that I don't understand is why the sEUF-CMA actually constitutes a stronger definition than regular EUF-CMA definition? Why does including the signature makes it stronger?
Also, for example in ECDSA, for a message $m$ and a valid signature $\sigma = (r,s)$, the signature $\sigma' = (r, -s \bmod N)$ is also valid. So, in a sense you get a new signature $\sigma'$, but, actually the signed message is the same $m$.

So, this seems to me that it does violate sEUF-CMA as, although the message is the same one, the signature is different, so adversary wins. Whereas, this cannot violate EUF-CMA, while there we care only for the message, so we don't care if adversary can produce a forgery for an already queried message. So, it achieves EUF-CMA security, but not sEUF-CMA, right?.
I think the situation is also different in textbook RSA, where it has homomorphic properties, so given a valid $(m, \sigma)$ pair, using the homomorphic properties one can produce a valid signature $\sigma'$ for a new message $m'$, and it seem does not satisfy any of the provided security definitions, is that right?

What I see that their difference is that in EUF-CMA experiment, the adversary needs to produce a valid signature for a message of its choosing, where the message has not been queried before (i.e., a message for which the adversary hasn't made queries to the oracle).

  Whereas in the sEUF-CMA experiment, similar thing happens, though now the adversary needs to make sure that it hasn't queried the oracle with the forged (message, signature) pair. So, simply the signature also enters into the equation in sEUF-CMA.

Right.  The point of EUF-CMA is the forger simply can't find a signature on any message it didn't send to the oracle.  With sEUF-CMA, the forger can't find a message/signature pair it didn't get from the oracle—not even a second signature on a message it did send to the oracle.

  The part that I don't understand is why the sEUF-CMA actually constitutes a stronger definition than regular EUF-CMA definition? Why does including the signature makes it stronger?

Can you forge signatures for messages not previously seen in an sEUF-CMA signature scheme, or can you prove that that's not possible?  What does that imply about whether an sEUF-CMA signature scheme is necessarily EUF-CMA?
Can you find a signature scheme that satisfies EUF-CMA but not sEUF-CMA?  (Hint: you already did!)  What does that imply about whether an EUC-CMA signature scheme is necessarily sEUF-CMA?

‘Strong’ just mean it implies other properties which don't necessarily imply it conversely.  Most protocols don't rely on strong unforgeability.  While Bitcoin doesn't rely on strong unforgeability, the first Bitcoin exchange, MtGox, did; it was exploited, because ECDSA does not provide strong unforgeability, and the subsequent demise of MtGox was later blamed on transaction malleability, whether rightly or not (paywall-free).

Another relevant property is signature uniqueness where even the signer can't come up with a second signature for a message—for this you may even want a VRF, a verifiably pseudorandom function, which is a PRF to anyone who doesn't know the key and is a signature to anyone who does and gives a verifiable proof of uniqueness.

  Also, for example in ECDSA, for a message $m$ and a valid signature $\sigma = (r,s)$, the signature $\sigma' = (r, -s \bmod N)$ is also valid. So, in a sense you get a new signature $\sigma'$, but, actually the signed message is the same $m$.

  So, this seems to me that it does violate sEUF-CMA as, although the message is the same one, the signature is different, so adversary wins. Whereas, this cannot violate EUF-CMA, while there we care only for the message, so we don't care if adversary can produce a forgery for an already queried message. So, it achieves EUF-CMA security, but not sEUF-CMA, right?.

Correct.

  I think the situation is also different in textbook RSA, where it has homomorphic properties, so given a valid $(m, \sigma)$ pair, using the homomorphic properties one can produce a valid signature $\sigma'$ for a new message $m'$, and it seem does not satisfy any of the provided security definitions, is that right?

Textbook RSA signature is, indeed, completely broken.  RSA was the first idea for how to make a signature scheme, but it was completely insecure; the first secure signature scheme was Rabin's in 1979.

The crucial insight of Rabin was that hashing is an integral part of a signature scheme.  Some textbooks will confusingly describe hashing as an afterthought to compress long messages, and talk of hash-then-sign, which is a dangerously wrong idea that can lead people to make mistakes that destroy security.

The computation of a hash and the computation of fancy math can be done separately, but only when they are combined into a verification equation like $\sigma^e \equiv H(m) \pmod n$ do you get a secure signature scheme.


What is the need for Diffie-Hellman key exchange when we have asymmetric encryption? I am new to cryptography and I am having a hard time to understand what is the need for DHKE procedure. I think I fully understand the principle in which it happens and also the mathematics behind it however I feel it is not needed (most probably I am wrong that's why I asking you guys here).
Let's say a client wants to communicate with a server - everything makes perfect sense with the first part of the handshake:
The client sends: "Hello server, this is my TCP max version, this and that, etc."

Then the server responds: "Hello, I am the Foo server. This is my public key (go check my certificate) this is my signature (so you can be sure it is me and not a 'middle man')"

Now due to the properties of the public-private key encryption, the client can send the server HIS public key (we don't care how, it's public anyway, but still the message can be encrypted with the server's public key) and then the secure communication can begin by using asymmetric encryption - when the client send something to the server it will be encrypted with the server's public key (so only the server can decrypt it) and vice versa (when server has to send something to the client it will be encrypted with the client's public key).
If my understanding is correct the DHKE procedure brings nothing new to the table in terms of security and I don't understand the need for using it (I doubt that the symmetric key encryption/decryption is much more efficient in terms of computing power).
Thanks in advance!

when the client send something to the server it will be encrypted with the server's public key (so only the server can decrypt it) and vice versa (when server has to send something to the client it will be encrypted with the client's public key)

As I understand it, you are suggesting not to bother using symmetric encryption; instead, have both sides exchange messages using public key encryption.
That would be horribly expensive (that is, slow); symmetric schemes are literally thousands of times faster than asymmetric schemes.
For example, on my test machine (using OpenSSL), it would 0.4 microseconds to encrypt a 64 byte message (size selected because that would fit within a single RSA encryption); in contrast, it took 614 microseconds (that is, 1500 times as long) to RSA decrypt the same amount using 2048 bit RSA.
Performance varies a lot depending on the processor, however this sort of huge performance is typical.

What is the need for Diffie-Hellman key exchange when we have assymmetric key exchange?

Well, one could use assymmetric key exchanges to share symmetric keys, and use those symmetric keys to encrypt the actual messages - that certainly can be done (for example, in some ciphersuites in older TLS versions).  It wasn't great when dealing with server compromise (which is why newer TLS versions abandoned it), but it did work.


Differential Fault Analysis of AES Let's say: an error is induced into an implementation of the AES-128 to produce a faulty ciphertext. The error is a one-byte eror and is always induced on the last state byte, during round9, before the MixColumns operation. The induced errors are unknown and can be different. However the key is the same in both cases.

Then how can I recover 4 bytes of the last round key? Which bytes of that round key can I recover and what's their value?

ciphertext1 = 0xe719f8ab9e0b846f0cf2e5c32a0e5b45
faultytext1 = 0xe719f86f9e0beb6f0c97e5c38b0e5b45

ciphertext2 = 0x78f272c7cf5383085fa240236d97130f
faultytext2 = 0x78f27277cf53e7085f944023fa97130f

Your fault attack scenario correspond to this paper :

A Differential Attack Technique Against SPN Structures with Application to AES and KHAZAD (Piret & Quisquater - CHES 2003)

This paper describe how to retrieve four bytes of the last round key with at least two pairs of ciphertext/faultytext.

Each pair of ciphertext $C$ and faultytext $C^*$ could be written as $C^* = C \oplus E$, where $E$ contains 4 bytes $\neq 0$.

For more details, the attack consists on several steps :

Compute a list $L$ of 4x255 possible differences after the MixColumns of Round 9
Guess 4 parts of $K_{10}$
Compute $d = SB^{-1} (C \oplus K_{10}) \oplus SB^{-1} (C^* \oplus K_{10})$
If $d$ in $L$, add guessed $K$ in a list of possible candidates of $K_{10}$
Repeat for each pair, considering only guessed $K$ in the list of possible candidates, if $d$ is not in $L$ for the new pair, remove the candidate.
Repeat until the list of possible candidates is reduced to one.


Recognizing and decrypting custom cipher with known plaintext and ciphertext I've been trying to reconstruct an encryption algorithm that produces a known ciphertext from a know plaintext. I have done some analysis:

the algorithm operates on single bytes
a plain text can be of any length and len(ptext) == len(ctext)
for a same letter plaintext the ciphertext repeats after 20B

Example (bytes are hex; ASCII(A) == 0x41):

P: 4141414141414141414141414141414141414141 414141...
C: cbcd7f01128216acb2495fa2625aa245d9d30366 cbcd7f...

a minor change in input reflects in minor change of output

Example (ASCII(B) = 0x42; the diffrence is probably +-3 max):

P1: 414141414141...
P2: 424242424242...
C1: cd7f01128216...
C2: ce7c02118115...

xor of ciphertexts from single letter plaintexts is obviosly corelated

Example (Cx = ciphertext of same letter 'x' plaintext)

Ca: cd7f01128216...
Cb: ce7c02118115...
Cc: cf7d03108014...
Cd: c87a04178713...

Ca ^ Cb: 3 3 3 3 3...
Ca ^ Cc: 2 2 2 2 2...
Ca ^ Cd: 5 5 5 5 5...
Cb ^ Cc: 1 1 1 1 1...
Cb ^ Cd: 6 6 6 6 6...
Cc ^ Cd: 7 7 7 7 7...

Do you recognize this cipher? How could I proceed with my analysis/reconstruct the algorithm?

Another complication is that ciphertexts seems to be sort of "rotated" with every new message, see what I mean.

Example (P1 and P2 are sent separately; '!' is used only to visualize it better):

P1: P2
P2: 4141414141414141414141414141414141414141 414141...
C1: !!!cbcd7f01128216acb2495fa2625aa245d9d30366 cbcd7f...
C2: 0366!!!cbcd7f01128216acb2495fa2625aa245d9d3 0366cb...

I am a beginner, any help is appreciated.

I figured it out.

keys = [k1, k2, ... , k20]
def encrypt(offset, message):
    ctext = []
    for i in len(message):
        ctext[i] = keys[(offset + i) % len(keys)] ^ message[i]

The "rotation" is caused by the "offset" parameter. The keys are stored in a rotation buffer and xored with plaintext bytes. The keys can be obtained by xoring a plaintext with a ciphertext.


What exactly is a “security parameter”? I often encounter the term “security parameter” when I read crypto related stuff. My basic understanding is that it just denotes some bit-length however, I'm not so sure.

For example, when it says

  … output strings of length 2K where K is the security parameter

how should I understand that ?

Quoting the obvious (Wikipedia article about the term “security parameter”.)

In cryptography, the security parameter is a variable that measures the input size of the computational problem. Both the resource requirements of the cryptographic algorithm or protocol as well as the adversary's probability of breaking security are expressed in terms of the security parameter.
The security parameter is usually expressed in unary representation (for example, a security parameter of $n$ is expressed as a string of $n$ 1s) so that the time complexity of the cryptographic algorithm is polynomial in the size of the input.
For example, in the RSA cryptosystem, the security parameter $k$ denotes the length in bits of the modulus $n$; the positive integer $n$ must therefore be a number in the set ${0, …, 2^k - 1}$.

Also note that the parties and adversary are assumed to run in time that is polynomial in the security parameter, and that security must hold except with probability that is negligible in the security parameter.


Offline anonymous electronic money systems and their cryptographical base What anonymous offline electronic money systems exist and what are they based on? I know only one currently - eCash, based on RSA blind signatures.

http://faircash.org/technology/teleportation.html

  Due to the Digital Coin concept, a value transfer between payer and payee is realized by transferring ownership of the eCoin. An essential part is the way how this transfer is conducted: Following the cash paradigm, it needs to be done peer-to-peer and offline in a repeatable way. Such a transfer is called teleportation.


Prime computation for Diffie Hellman While reading some cryptographic RFCs, came across the Diffie Hellman prime computation formula:

2^1024 - 2^960 - 1 + 2^64 * { [2^894 pi] + 129093 }

I am curious what the expression [2^894 pi] means here. The part specifically confusing me is the space between 2^894 and pi. It cannot be a multiplication operation as that does not give me the correct result. I am sure the answer is straightforward for someone with mathematical background...


Basic encrypted custom protocol I've been suggested to ask here instead of stackoverflow, so here I am.

I'd like to encrypt the data of my application that uses a custom protocol I've created. I know about TLS and other protocols but I just want to do a basic encryption. The following code is C++, please ask me if you need any help to understand it.

My protocol is something like:

template<uint16_t thePayloadLength>
struct MyProtocolHeader{
uint16_t startOfFrame = 0xFFFF; // Protocol signature
uint16_t version;
uint8_t src;
uint8_t dst;
uint16_t payloadLength = thePayloadLength;
uint8_t payload[thePayloadLength];
}; // the template part probably is going to disappear (too much code bloat)

My idea is to create two functions like:

template<uint16_t thePayloadLength
 /*EncryptedData*/ encrypt(const MyProtocolHeader<thePayloadLength>& plain);

 template<uint16_t thePayloadLength
MyProtocolHeader<thePayloadLength> decrypt(const /*EncryptedData*/& encryptedData);

that basically just do an encryption / decryption of my protocol struct. Then I can send the "EncryptedData" as a payload of an header like the following:

struct EncryptedProtocol{
uint16_t startOfFrame = 0xAAAA;
uint16_t version;
uint16_t sequenceNumber; // can be useful for UDP
uint16_t length; // lenght of the encrypted payload
};
// Encrypted payload here

I was thinking to use AES-GCM as encryption algorithm with the shared key already known by all the applications.

What do you think about it?

[EDIT] all the applications are outside Internet and they all know the public keys of all the other applications.

[EDIT2]

  would you only feed the plaintext part to AES-GCM?

Yes. An alternative would be to add random bytes but I'd like to do something not complicated to implement that guarantees some kind of protection.

  Would you make use of the Associated Data input?

Yes, if I recall correctly AES-GCM should provide that

  Is the shared key static / negotiated for a "connection"?

The first version will make use of pre-shared keys, so no need to negotiate the key. For a future version I was thinking to get the RSA shared key creating a new protocol that will use RSA. All the applications will be configured by an administrator that will "install" the public keys of all the other applications.

Just to clarify, TLS seems too general-purpose and bulky to implement (OpenSSL seems really messy for instance), and I just wanted to add a basic encryption scheme to my application. What I'd like to know is if this design can satisfy that requisite and how good can be considered from a security point's of view.

[edit3]
Totally open to suggestions if something similar already exists.

The best way to learn something is to do it right. So I'd suggest just using TLS, but perhaps use a different library, like BearSSL. That way if it does turn into something more than a learning project, you don't have to redesign everything or risk being very insecure.

That said, here are some things to think about given your current path.

You should definitely protect the EncryptedProtocol struct using the associated data portion.
You need to make your protocol "future-proof". This means that if someone broke GCM or AES tomorrow, you should be able to easily adapt to needing to use new ciphers for modes. Thus, in your protocol header, you probably need a cipher version field. Maybe for now you only support AES-GCM, but that cipher version field will make it so you can change in the future if needed.


Keys: Is This Way of Encryption Already Invented? I've invented a way of encryption where there are keys which represent a certain cipher alphabet, whether it be a scrambled alphabet, shifted alphabets, numbers or symbols/pictographs.

For example, a letter R with the number 2 above it equals E in Rot13 but, and R with a 1 above it is I in Atbash.

Is this method already invented?

Maybe not the precise scheme, but having elements in the key select a particular cipher is pretty common - mainly by persons starting crypto. All in all they are generally not secure and end up discussing Kerckhoffs's principle.

It is not easy to create a modern, secure cipher by alternating between a lot of insecure classical ciphers. No doubt it can be done, but this scheme is not intricate enough for that; it will fail basic randomness tests and will probably fall to frequency analysis as well.


Is there a way to double the size of ciphertexts of a public-key scheme which is IND-CCA2 Let $\Pi = \left( \mathrm{Gen}, \mathrm{Enc}, \mathrm{Dec} \right)$ a public-key scheme which is secure in the sense of IND-CCA2.
Assume the ciphertexts space is $\mathcal{C} \subset \{0,1\}^{n}$.
Can we construct a $\Pi' = \left( \mathrm{Gen}', \mathrm{Enc}', \mathrm{Dec}' \right)$ which is also secure in the sense of IND-CCA2 such that $$\mathcal{C}' \subset \{0,1\}^{2n}$$
and for every plaintext $x$,
$$|C'(x)|/|C(x)| > poly(n)$$
and
$$0^{n} \Vert \mathrm{Enc}_{pk}(x) \in C'(x)$$
where $C(x) = \{ y \mid y = \mathrm{Enc}_{pk}(x) \}$.

In general, it seems easy to make the ciphertexts longer keeping the level of security. But if I just modify the form of ciphertexts simply (e.g. $r \Vert \mathrm{Enc}_{pk}(x)$ for $r \leftarrow \{ 0,1 \}^{n}$). It can not be secure in the sense of IND-CCA2 any more.

This is actually a very interesting theoretical question that was open for many years. For CPA-secure encryption, it is possible to simply concatenate ciphertexts in order to increase the plaintext space. However, for CCA2, it is not sufficient to concatenate since it's possible to move around the bits and maul the ciphertext. Note that if you assume that the original plaintext space is large  (super-polynomial), then it's easy to solve by just using hybrid encryption. This is because you can encrypt a symmetric key and work from there. However, if the plaintext space is small -- especially hard if a single bit -- then it's very unclear. Fortunately, Myers and shelat solved this in FOCS 2009 in a paper entitled Bit encryption is complete.


How to get an optimal strategy in computing isogenies for SIDH/SIKE How to get a strategy $(s_1,...,s_{t-1})$ as mentioned in section 1.3.7 of SIKE spec?

If possible, can anyone give me an example?

And why do we need to compute all leaf point? I though we just need the right most leaf point to get an isogeny of smooth degree ${l_A}^{e_A}$

On page 67 of the same spec, Algorithm 42 does exactly what you are asking for. Here it is again in Python:

def strategy(n, p, q):
    S = { 1: [] }
    C = { 1: 0 }
    for i in range(2, n+2):
        b, cost = min(((b, C[i-b] + C[b] + b*p + (i-b)*q) for b in range(1,i)),
                      key=lambda t: t[1])
        S[i] = [b] + S[i-b] + S[b]
        C[i] = cost
    return S[n+1]

The parameters p and q are used to weigh the strategy, they depend on your implementation of SIKE. Following the definitions of the spec, p is the cost of one multiplication step, q the cost of one isogeny step.

When choosing a strategy, there may be other considerations than those related to the weights p and q. For example, you may prefer a strategy that is slightly more costly, but easier to parallelize. So the algorithm above is by no means a definitive answer: you should choose whatever strategy works best for you, as long as it is a valid one (see page 15 of the spec). If you have no idea what's best for you, choose the ones given in appendix C of the spec, or use a non-optimized strategy.

Regarding your "why" question, each "leaf point" defines the kernel of one ℓ-isogeny step. You want to compute all of them, so you can compute all isogenies, and compose them. This is not a theorem. It is just the best way we know.


Manual secret sharing? What are feasible options for an equivalent of Shamir Secret Sharing using small tables, preferably usable with pen-and-paper? We want to share a secret $K$ into $n\ge2$ shares, so that $m$ shares ($2\le m\le n$) are necessary to reconstruct the secret, and less than $m$ shares reveal no information about $K$.

For $m=n$ (e.g. 2-out-of-2), we can use $n-1$ shares $S_i$ ($1\le i<n$) of uniformly random independent bits, and another $S_0$ that is the bitwise-XOR of the secret $K$ and the other shares: $S_{0,j}=K_j\oplus\left(\displaystyle\bigoplus_{i=1}^{n-1}S_{i,j}\right)$. The secret is recomposed by bitwise-XOR of the random shares: $K_j=\displaystyle\bigoplus_{i=0}^{n-1}S_{i,j}$.

This is easily extended to $2^k$ symbols, e.g. octal or hexadecimal.

For 2-out-of-3, we can use a ternary system, a first share $S_0$ of random trits, an two shares $S_i$ ($i\in\{1,2\}$ ) defined by $S_{i,j}=S_{1,j}+i\,K_j\bmod3$. The secret can be recomposed from any two shares, as:
$$K_j\,=\,S_{1,j}-S_{0,j}\bmod3\,=\,S_{2,j}-S_{1,j}\bmod3\,=\,S_{0,j}-S_{2,j}\bmod3$$
The tables for addition (used for encoding) and subtraction (used for decoding) are:

    | 0 1 2                             | 0 1 2
----+------                         ----+------
+ 0 | 0 1 2                         - 0 | 0 1 2
+ 1 | 1 2 0                         - 1 | 2 0 1
+ 2 | 2 0 1                         - 2 | 1 2 0

This is easily extended to base $3^k$; e.g. for $k=2$

    | 0 1 2 3 4 5 6 7 8                 | 0 1 2 3 4 5 6 7 8
----+------------------             ----+------------------
+ 0 | 0 1 2 3 4 5 6 7 8             - 0 | 0 1 2 3 4 5 6 7 8
+ 1 | 1 2 0 4 5 3 7 8 6             - 1 | 2 0 1 5 3 4 8 6 7
+ 2 | 2 0 1 5 3 4 8 6 7             - 2 | 1 2 0 4 5 3 7 8 6
+ 3 | 3 4 5 6 7 8 0 1 2             - 3 | 6 7 8 0 1 2 3 4 5
+ 4 | 4 5 3 7 8 6 1 2 0             - 4 | 8 6 7 2 0 1 5 3 4
+ 5 | 5 3 4 8 6 7 2 0 1             - 5 | 7 8 6 1 2 0 4 5 3
+ 6 | 6 7 8 0 1 2 3 4 5             - 6 | 3 4 5 6 7 8 0 1 2
+ 7 | 7 8 6 1 2 0 4 5 3             - 7 | 5 3 4 8 6 7 2 0 1
+ 8 | 8 6 7 2 0 1 5 3 4             - 8 | 4 5 3 7 8 6 1 2 0

See this for $k=3$ used for the 26 letters and space.

As long as conciseness of the shares is not an issue, we can directly encode binary with the ternary system, octal with $k=2$, hex with $k=3$, base64 with $k=4$.

What about other $m$-out-of-$n$ schemes? In particular 2-out-of-4, 2-out-of-5, 3-out-of-4?

It is known that (m,n)-threshold schemes are equivalent to n-1 m-dimensional mutually orthogonal latin m-hypercubes. For m=2, there is a basic construction (Latin Squares) for prime n. For m > 2 you would need higher dimensional tables, there should still exist a simple way to generate them for prime n.


Generate a list of valid ASCII codes I have read many pages about encryption but I am really stuck on this. For access control to a building I want to print a 10 character ASCII code on a ticket (as a barcode).

The barcode reader (controlled by an Arduino or mini PC) is not connected to the PC which creates and prints the barcodes.

When both server and client have the same keys, is it possible to validate the codes?

EDIT:
My first attempt was to convert the current date in to binary, and then to ASCII with base64. The problem was that I ended up with a too big code (11 characters).

Considerating everything I came to the conclusion that it would be better too convert the date and time directly into ASCII characters. ASCII characters become readable at position 33, so year 2015 becomes 15 + 33 = ASCII character 0

In this way Year + Month + Day + Hour + Second + Validtime only takes 7 characters.

EDIT2:
I tried different encryptions en base encodings. Because year and month don't vary much, the generated code before encryption looks very much alike. When I use ARC4 encryption, the generated codes are also very similar.

Using DES3 the generated codes are not alike. I have included the two encryption methods in the code below. Because I use Python 2.7 I have to use the base85 module from the mom package. In Python v3 base85 is included.

Here is the code:

from datetime import datetime
from Crypto.Cipher import DES3
from Crypto.Cipher import ARC4
import base64
from mom.codec import base85

sleutel="Dsdfk3#$294ddkwlsslwEefm"
now = datetime.now()
year = chr((now.year - 2000)+33)
month = chr((now.month)+33)
day = chr((now.day)+33)
hour = chr((now.hour)+33)
minute = chr((now.minute)+33)
seconds = chr((now.second)+33)
#validtime from 0 till 9 in this case just a random 4. So 0 would be a few hours and 5 a week etc.
validtime = chr(4+33)
key = ''.join([year,month,day,hour,minute,seconds,validtime])
print key
obj1 = ARC4.new(sleutel)
obj2 = DES3.new(sleutel)
cipher_text = obj1.encrypt(key)
cipher_text1 = obj2.encrypt(key+ 'a')
print "Base64 ARC4 encrypted:", base64.b64encode(cipher_text)
print "Base64 DES3 encrypted:", base64.b64encode(cipher_text1)
print "Base85 ARC4 encrypted:", base85.b85encode(cipher_text)
print "Base85 DES3 encrypted:", base85.b85encode(cipher_text1)

Because I added seconds, every code is unique (as long as it is impossible to print two tickets in one second)

If you really can use all 95 printable ASCII characters, you're better off encoding everything in binary (however you want) into 64 bits, then encrypting that with your secret key (using a cipher with a 64-bit block size, such as 3DES), then turn the result of that into 10 characters using an encoding from binary into base-95.  You can actually encode 64 bits into 10 characters using only 85 characters, so you could omit some that might be a problem (e.g. SPACE).  Since you're encrypting only one block, and they're guaranteed to be unique, you can simply use it in ECB mode (no IV, no chaining modes).

Then just turn it into a 10 digit base-85 number (the same way you'd convert binary to base 10), then map each of the 85 possible values for a digit (0-84) into an ASCII character (either with a lookup table or something as simple as adding 0x21).

You'll want to make the data as well-structured as you can so that you can detect any tampering, including perhaps a (small) checksum of some sort, and verify all 64 bits as being valid/well-formed.


When attacking keyed algorithms, how is it known when the output is correct? I've been reading a little bit about cryptanalysis, and I'm wondering how attacking algorithms that work on keys is performed.
It's obvious how algorithms like MD5 are attacked, in pseudocode:
hashed = 'blablabla'
while guess != hashed:
    guess = md5(inc(guess))
print('{hashed} is {guess}')

But I can't see how you'd perform a similar attack on, for example, XTEA. To attack it through the deciphering process you'd have nothing to compare the guess to, and to attack it through the enciphering process you'd have to guess if  encipher(key, data) == enciphered_data, i.e. guess both the content of the data and the key, which seems like it would take an incomputable amount of time, especially if data is, say, a 64-bit block.
Is brute-forcing such a large space truly the only option?

Usually, the brute-force attack is performed with known-plaintext where a message $m$ and its ciphertext $c = \operatorname{XTEA}(k,m)$ is available. Indeed, one may need more than one to exactly found the key since a key selects permutation and at the point $m$ there can be more than one permutation selected by different keys that maps to the same ciphertext.
In ciphertext only attack, you may need some additional information to test the outcome, the candidate plaintext. Options are;

The encoding : for example in ASCII encoding the MSB is usually 0.

The padding : Block cipher if not used in streaming mode like the CTR mode, then a padding is needed. The padding can be used to identify the correctness. The padding can be  PKCS#5 as in the RSA DES challenge which was a known plaintext attack and bruteforced.

The language : if the target language is known than the current plaintext during the search can be tested for words like the string command in the Linux

Each of the options can increase your change. Having more ciphertext messages can eliminate more false candidate. Keep in mind that, however, if an option is not 100% correct, that can cause to find the key.
If there is no options, there is no test a validity of a candidate key.
In academical history, T.Siegenthaler use ASCII to break combined LFSR with a ciphertext only attack.

Decrypting a Class of Stream Ciphers Using Ciphertext Only

Is brute-forcing such a large space truly the only option?

If there is no weakness in the algorithm, the above is the only way. For the attacks in XTEA, listed from the Wikipeida

In 2004, Ko et al. presented a related-key differential attack on 27 out of 64 rounds of XTEA, requiring $2^{20.5}$ chosen plaintexts and a time complexity of $2^{115.15}$ (Ko et al., 2004).
In 2009, Lu presented a related-key rectangle attack on 36 rounds of XTEA, breaking more rounds than any previously published cryptanalytic results for XTEA. The paper presents two attacks, one without and with a weak key assumption, which corresponds to $2^{64.98}$ bytes of data and $2^{126.44}$ operations, and $2^{63.83}$ bytes of data and $2^{104.33}$ operations respectively.

Those require much more than one known-plaintext to execute an attack, and this is common if you are executing a brute force attack.
And, final note
If a cryptographic algorithm or scheme is breakable with ciphertext only attack,  turn back an run.
We need at least CPA secure ciphers in modern cryptography.


RSA: special parameters construction I have to show that the following construction of $q$ allows to factorize $N$ :

  $p \in \mathbb{P}$, the set of primes
  $q \gets p \cdot \left((p - 1)^{-1} \bmod e\right) \bmod e$
  $k=1$
  while $q \not \in \mathbb{P}$:

  $q \gets q + k \cdot e$
  $k \gets k + 1$

  end while

I tried to analyse $N \bmod e$ and transform the expression but without success.

If some can give me some hints

Edit:

$p$ is 512 bits size,  $e$ is 504 bits size.

Let's $\alpha = (p - 1)^{-1} \bmod e$ then $N = p \cdot (\alpha + 1 + k \cdot e)$

Finding $q$ is equivalent to finding $\alpha$.

It is easily seen that the value of $q$ is invariant modulo $e$.  As a consequence, we always have $q \equiv p\cdot (p-1)^{-1} \pmod e$ and thus $q(p-1) \equiv p \pmod{e}$.  So, the resulting modulus $N = pq$ is such that $N \equiv (p+q) \pmod e$.

Example: With $p=10598342506117936057$ and $e=5004898192290387253$, the proposed construction yields the prime $q = 106091356957242239963$.  One can check that $p\cdot q \bmod e = 1577041040681269201 = (p+q) \bmod e$.


Could PAKE via smooth projective hash function protect agaist replay attacks? I came across some password-based authenticated key exchange (PAKE) protocols that are based on the smooth projective hash function (SPHF) in the standard model. And I checked some related works, and most of them only considered the dictionary attack and forward security. I am wondering if this kind of PAKE via SPHF could prevent replay attacks? If it can prevent, why? Otherwise, how to fix this problem?

And I checked some related works, and most of them only considered the dictionary attack and forward security.

Actually, a PAKE has two security goals:

That someone cannot recover the password from a number of exchanges (with any greater advantage than being able to test $N$ potential passwords using $N$ active attacks).

That someone will not be authenticated without knowing the password (or having a correct guess to it).

Both of these needs to be true even if the adversary has the transcripts of a large number of successful authentications.
The "replay attack" falls in an attempt to violate the second security property.  If the related works did not specifically call that out, the security proofs they presented still need to address that (and if they don't, well, that's a hole in the proof).
All of the PAKEs I'm familiar with handle replay attacks; most of them because the initial message from both sides include some randomness that is different with each exchange, and which is stirred into the later computations; this implies that straight-forward replay attacks will fail.
The exception is Opaque, which has a different defense against replay attacks; the difference is on the replay on the client side,  The adversary can indeed replay the initial message (and get the repeat of the server side message; it doesn't stir in any randomness for this part of the exchange), however the adversary cannot then retrieve the client's private key (stored in some data encrypted with a key that the adversary does not know), and hence will fail in the next stage of the protocol.


Signature algorithm SHA 1-2 with ECDSA Can someone please explain what key sizes are required for the ECDSA algorithm?
I tried a 128 bit EC Key for SHA1withECDSA and it throws an error. However with 256 bit key I could run the algorithm. Therefore want to know what key sizes are required for the different ECDSA algorithm with SHA1 and SHA2.

Also, how does the key size affect the signature here? Can you please explain?
Thank you.

In principle it should be possible to use 128 bit EC domain parameters / keys with any hash:

For Alice to sign a message m, she follows these steps:

Calculate $e = HASH(m)$, where $HASH$ is a cryptographic hash function, such as SHA-1.
Let $z$ be the $L_n$ leftmost bits of $e$, where $L_n$ is the bit length of the group order $n$.

Source: Wikipedia

However, implementations may reject combinations that would result in a very strange mix of security levels. Normally, I would try and use EC key sizes that are equal or larger than the digest algorithm used. It may be that some implementations refuse to perform step 2, only using the full hash instead of cutting it down to a smaller size.

Note that SHA-224, SHA-512/224 and SHA-384 kindly supply hash output sizes that can be combined with 224 and 384 bit ECC. Please have a look at keylength.com for more information about choosing matching sizes for algorithms.


Is AES ECB mode with salt and frame counter still comparatively weak? Many advice against using AES in ECB mode as it always produces same cipher text for a given plain text.
That shortcoming can be addressed by using salt appended to original message so that the resulting cipher text is different each time , the receiver can then decyrpt the cipher text and discard the salt keeping the original message
However this is susceptible to replay attacks, but that can be mitigated further by using a frame counter in the plain text message so that the receiver knows if the message is being replayed by a unauthorized sender.
So the result would be
Encrypt[Counter + Message + Salt] ===> CipherText ==> Decrypt[CipherText] ===> Counter + Message + Salt.
That strategy seems sound to me , are there any known flaws that advise against using it ?

The point of producing different ciphertexts for the same plaintext is so that an attacker, given two identical ciphertexts, could not conclude that the plaintexts must be the same. This is indeed a weakness, but is not the main problem of ECB, which is that each block is encrypted completely independently, leaking huge amounts of information about the plaintext to even a passive observer.
Your strategy does not help with that, as the attacker could simply ignore all the ECB blocks belonging to the counter and salt and simply pick out blocks belonging to the messages, and we're back to standard ECB.


Is there a method to encrypt relations in between values of a cyclic value set and generate values out of this set with pseudo RNG? (all at user PC) Is there a pseudo RNG and function $f$ with
1.) The RNG produces a value $v_0$ out of $N$ different values (set $S$).
2.) Independent of the RNG the function $f$ generates $v_{i+1}=f(v_i)$

Requirements:
$\bullet$ $v_{i+N} = v_i$
$\bullet$ $\forall i$:  $\{v_{i+k}, 1\le k \le N\} = S$
$\bullet$ $v_{i+j} = f^j(v_i)$ so it needs $O(N)$ computations (hard to compute)

All this is computed at the users PC. He has access to all variables. Given two random values genereated by the RNG the user should not know how to compute the second out of the first (= how often $f$ need to be applied).

Question: Is there any cryptographic method which has such conditions?

Further notes:
(*..) ... in further text means an optional simplificaion

$\bullet$ each $v_0$ is part of the same cycle (*or part of one out of a max of 10 cycles of equal size (+/-5%))

$\bullet$ There should exit no faster way to compute $v_{i+j}$ out of $v_{i}$ except in $j$ $(\mod n)$ steps (or $N-j$ steps) (*linear speed up of less than 5 times is ok)
$\bullet$ (*The result set of function $f$ can be larger than those $N$ values (up to ~1000 times)(and with this the cycle size) but there need to exists an efficient function to prove if it is one of those $N$ values.)

$\bullet$ There need to be an efficient way to (pseudo) randomly generate values $v_0$ (*not all values in $S$ need to be generated by the RNG but at least $N^{2/3}$)
$\bullet$ (*The RNG dont need to be uniform distributed among those $N$ values (but it can). It's fine if no probability of one value is much higher than 1000 times than any of a subset containing 80% of all values.)

Examples

$\bullet$Using unknown methods:
A random cyclic permutation (with cycle size N) with function $f$ which generates the next value in that cycle and the RNG could be a random number between 1 and $N$.

$\bullet$Too easy to compute:
The discrete logarithm in $\mathbb{Z}/N\mathbb{Z}$ with prime $N$ and a primitive root $g$ as generator with $f(v)=v⋅g$. The RNG would just give a random value between $1$ and $N−1$. If now the user gets two such random values he does not know how to compute one out of the other (how often multiply with $g$) even if he knows all internal variables. But it can be solved in about $O(\sqrt{N})$ steps. For small numbers that would be too fast to compute. I'm looking for something similar but with $O(N)$ (or bigger).

Example use case:
 _

 _

The green square is value $v_0$ generated by the RNG.
A-F are members of set $S$.
The relation from one value to the next is equal in each picture (modulo 9).
E.g. to get from value D to E it is always 1 square to the right and 1 below.
If now $N=80$ and $f$ delivers the next value in the cyclic permutation (with size N) the following blue square can be generated like:
with $v_{i+1} = f(v_i)$ then shift horizontal $= v_{i+1} \mod 9$ and vertically $= \operatorname{roundDown}(v_{i+1}/9)$

This can lead to multiple values at same position but values which are close in cycle also share almost equal other values. Values at the other end of the cycle still share more than half of the values. This property is not needed, equal values all the time would be better.

If now given only two random values e.g. D and G it should be as hard as possible to derive the position of G starting at D.

The grid will be 3D and about 100k x 100k x 100k tiles. Neeed about $10^{12}$ unique values. Only need to be safe for standard PC (>10.000 hour compute time, not supercomputer, grid, hardware)

Besides the 'next' function $f$ also the inverse can exists. Except just a single function also a function for each dimension can exists. If that's the case only the adjacent square gets computed. It need to be independent  of the order of function execution and there should exist no (easy) way to reduce a given value to its dimension values. Else finding the way between two random values would be too easy.

If evaluating $f$ uses computer time $t$, a brute force attack takes on average time $Nt/2$. To have this larger than $T=36\cdot10^6$ seconds, with $N\approx10^{12}$, we need $t>72\cdot10^{-6}$, that is some hundred thousands CPU instructions. Artificialy slowing down the implementation of $f$ in the program won't help. $f$ must be inherently slow so that it is slow for the attacker; and controllably slow so that we can tune the compromize between security and speed of the user program.

The example application suggests that $S$ is a haphazard subset of a larger set with $M\approx10^{15}$ elements. We'll take it as $[0,M)$, with $M\ge2N$.

I aim only at a reduced version of the security requirement: Given two random values produced by the RNG, a guess of the number of steps of $f$ to go from one to the other, if made with much less than $T$ seconds of compute time, has low probability to be exact. Towards that:

Choose an integer parameter $\alpha$ (a larger one will slow $f$). Find a prime $p\approx\alpha N$ with $q=(p-1)/2$ prime ($p$ is a safe prime and $q$ a Sophie Germain prime), and also $2^q\bmod p=p-1$ (and perhaps $\log_2p$ unremarkably close to a simple fraction).
Define the function $b$ on the set $[1,p)$ as $x\mapsto b(x)=2x\bmod p$. The function $b$ is a cyclic permutation of $[1,p)$.
Define the function $c$ on the set $[N,2N)$ that iteratively applies $b$ (at least once) until the result is in $[N,2N)$, and returns this result. The function $c$ is a cyclic permutation of $[N,2N)$. See note for implementation.
Build a permutation $g$ of $[0,M)$ using a standard Format-Preserving Encryption technique. $S$ is  the set of integers $v$ in $[0,M)$ with $N\le g^{-1}(v)<2N$.
Define the RNG as drawing $u$ uniformly at random in $[N,2N)$ and returning $g(u)$.
Define function $f$ over the set $S$ as $f(v)=g(c(g^{-1}(v)))$. It cycles over the $N$ elements of $S$ in exactly $N$ steps.

Given random $v$, $v’$ produced by the RNG, it is possible to estimate how many steps of $f$ are necessary to go from $v$ to $v’$: we compute $u=g^{-1}(v)$ and $u’=g^{-1}(v’)$, then $y=u^{-1}\,u’\bmod p$, then solve for $x$ the Discrete Logarithm Problem $2^x\bmod p=y$ (this remains easy, given the order of magnitude of $N$ and $\alpha$). A reasonable guess of how many steps of $f$ are necessary to go from $v$ to $v’$ is $x\,N/p$ rounded to the nearest integer. However that estimate has low probability to be exact for moderate $alpha$ (much less than $N$), and I have some hope that markedly improving it has some sizable cost.

Note: there are time/memory trade-offs possible for evaluation of $c$ faster than the trivial:

uint64_t c(uint64_t x) {
  do {
    x += x;
    if (x>=p)
      x -= p;
  }
  while( x>=2*N || x<N );
return x;
}

and the program should use these, in order to increase $\alpha$ inasmuch as functionally tolerable, maximizing the cost of a brute force attack.


RSA polynomial cubic root Let's suppose we are given a linear polyonmial
$$\begin{align}f(x) = ax + b\end{align}$$
where a and b is known which satisfies this equation
$$\begin{align}y^3 - f(x) \equiv 0\mod(n) \end{align}$$ where n is RSA modulus.
Is there any way to solve for pair(x,y)?
Follow-up question: If there is restriction where only those values of x are allowed for which $$\begin{align}f(x)<n \end{align}$$

Is there any way to solve for pair(x,y)?

If you're looking for an arbitrary pair, it's easy (assuming $a \ne 0$).

Pick an arbitrary $y$

Solve for $f(x) = y^3$; that'd be $x = a^{-1}(y^3 - b) \pmod{n}$

You're done.


What does CA certs contains? public key of site or CA? I believe it contains public key but whose? the site like a bank or the certificate authority who has signed?

As per definition, digital certificate is a security document that binds public key to some entity. That is, any X.509 certificate at least contains certificate owner's public key and information about the cert owner.

In the case of web site SSL certificate, digital certificate contains web site's public key and information about the site.

For CA certificates, they contain CA's public key and information about that particular CA.

Digital certificate contains other information as well, like information about issuer, validity, key usages and information that could be used to validate each certificate (e.g. build certification path, perform revocation checking, etc.)

For your question: CA certificate contains its own public key. When bank web site's certificate is validated, a certification path is constructed by using issuer information. Then issuer's public key is used to validate web site certificate's signature. That is, when you validate any particular certificate, public key for signature validation is taken from other source (except self-signed certificates, where public key in the cert is used to validate its own signature).

For more details I would recommend to read RFC5280.


Error during transmission with one plaintext block (Cipher block operation) I was given a graph like this, and the problem was stated as: if something happens to P2 then only P2 would not be retrieved on the decryption side, and all other P's can be retrieved normally. I do not understand how so? If something happens to P2 then its encrypted XOR will be wrong, then leads to a wrong C2. Also, P2 will get XOR with the encrypted P3 to create C3, won't that be wrong too, and the same with all other blocks?

Note: P is plaintext, C is ciphertext, D is decryption, and E is encryption.

First, Let us write the encryptions as an equation;

\begin{align}
c_1 & = \text{IV} \oplus \operatorname{Enc}(k,p_1) \\
c_2 & = P_1 \oplus \operatorname{Dec}(k,p_2)\\
\end{align}
and the last

\begin{align}
c_3 & = p_{n-1} \oplus \operatorname{Dec}(k,p_3) \\
c_4 & = P_n \oplus \operatorname{Dec}(k,p_4)
\end{align}

As one can see the chaining(?) is constructed(?) within two by two blocks. However, there are more serious problems than the original question.

The decryption of $p_2$; $$p_2 = \operatorname{Dec}(p_1 \oplus c_2)$$ If one look at the encryption of $p_2$ they will see that $\operatorname{Dec}$ is used. Therefore, unless the block cipher is a very sepcial cipher that $\operatorname{Enc}=\operatorname{Dec}$ than this is not possible to get $p_2$. Thas is the blockcipher chooses an involution for every key, see OEIS A000085.
This is similar to the first; This time always $\operatorname{Dec}$ is used. So we don't expect even decryption.

Now back to corrected one, that is for encryption $\operatorname{Enc}$ is used and for decryption $\operatorname{dec}$. Then, as stated above, the blocks are operated two by two and this means that an error can only affect at most two blocks. $c_1$ affects two blocks and $c_2$ affects one block, etc. It is also not clear how the odd number of blocks are encrypted. One can guess that there is a special padding mechanism.


Can you use ECDSA on pairing-friendly curves? I'm learning about Elliptic curve cryptography. If I understand right, ECDSA and other algorithms used in ECC are dependent on the curve chosen. So, before you want to use ECDSA, you first have to choose a suitable curve.
Pairing-friendly curves are a special kind of elliptic curves that have properties that allow for different algorithms not available on every elliptic curves such as BLS or Identity-Based Encryption.
In this publication there is written on page 8:

Following the discovery of these attacks in the early 1990s, the consensus was that elliptic curves with low embedding degrees should not be used in discrete log protocols.  In fact many standards for elliptic curve cryptography such as ANSI X9.62 [3] explicitly forbid the use of such curves. However, low-embedding degree elliptic curves are now very much back in vogue since they are crucial for the efficient realization of the pairing-based protocols that were presented in §3.

Let's say I wanted to use ECDSA (which is based on the discrete log problem I believe) over a pairing-friendly curve (like alt_bn128). According to this, the pairing-friendly curve is supposed to have a low-embedding degree and shouldn't be used with ECDSA.
Am I understanding this correctly? Does that mean the cryptographic primitives one can use on pairing-friendly curves should be specifically designed for pairing-friendly curves (like BLS)?

You can. Low-embedding degree may be bad due to the MOV attack, but pairing-friendly curves are particularly chosen so that the embedding degree is low but still enough to not decrease security. So any elliptic curve algorithm should be safe on the curve, not only pairing-based ones.
Some observations:

ECDSA if often used with NIST curves with cofactor 1. However, some pairing-friendly curves have larger cofactors, so you need to take that into account. For example, the BLS12-381 curve has a 381-bit prime but the main subgroup has 255 bits, therefore is has around $255/2 \approx 128$ bits of security (and not $381/2$)
It's still a bit riskier than using high-embedding degree curves. If there are advances in attacks against discrete logs in finite fields then the curve security can decrease. In fact, this has already happened once: for example, the BN256 curve security was reduced from 128 bits to 110 bits.