Difference between eavesdropping and traffic analysis I was wondering what is the conceptual difference between these two passive attacks on a network. I was reading about them on Wikipedia and they seem quite similar to me. Is there a difference?

The Wikipedia definitions;
Traffic analysis;

Traffic analysis is the process of intercepting and examining messages in order to deduce information from patterns in communication, which can be performed even when the messages are encrypted

Eavesdropping;

Eavesdropping is the act of secretly or stealthily listening to the private conversation or communications of others without their consent.

This type of network attack is generally one of the most effective as a lack of encryption services are used. It is also linked to the collection of metadata.

Wikipedia definition of Eavesdropping is a bit historical definition. In the cryptographic terms, the Eavesdropper listens to the medium and tries to break the ciphers, and the action is Eavesdropping. We call it also a passive attacker and passive attack, respectively. We don't use traffic analysis to eavesdropping.
Traffic analysis, today, is used in computer security. Traffic analysis can be executed even the channel encrypted with OTP. The time of the message, the frequency of the messages etc. All can be very important to signal intelligence. However, OTP has perfect secrecy so no passive attacker can break it.
For example; If the battleships send to their control center we are alive message for every 8 hours in a normal day with OTP, then any increase of the messages during a day may indicate that there is an action around. So the enemy can concentrate on this region. As you can see, this leaked information. This can be prevented by on-line encryption. There are more examples in Wikipedia;

It is difficult to defeat traffic analysis without both encrypting messages and masking the channel. When no actual messages are being sent, the channel can be masked

Traffic analysis is a very broad term and it came also from the history (part of Signal Intelligence). It can  still be applied if the protocols are not considered to prevent this attack as in Timing Analysis of Keystrokes and Timing Attacks on SSH


AEAD: Is it secure to decrypt the content encryption key before verifying the MAC? The JSON Web Encryption (JWE) standard defines a number of encryption modes with the same basic form:

First, the a unique content encryption key (CEK) is generated and used to encrypt the payload with associated data in an AEAD mode (e.g. AES-CBC with HMAC or AES-GCM). If a separate block cipher and MAC are used then the individual keys for each are concatenated to form the CEK.
Then, the CEK is encrypted with the public key of the recipient (e.g. using RSA with PKCS#1 v1.5 padding) and the result is prepended to the ciphertext.

My question is: while the underlying symmetric cipher provides authenticated encryption, the recipient must decrypt the CEK before they can verify the MAC on the underlying AEAD construction. Does RSA with appropriate padding when used just for key wrapping already provide authenticated encryption?

No, RSA encryption does not provide authenticity, regardless of the padding. This is for the simple reason that anybody can encrypt with the public key. This is irrespective of the asymmetric algorithm used. You need to sign the data to obtain authenticity.

What AEAD does do is to protect e.g. against padding oracle attacks. These can be performed on CBC mode encryption, which could also cost you confidentiality (leaving you with nothing).

In that case however the RSA implementation must also be protected against padding oracle attacks. That basically means that OAEP (or possibly RSA-KEM) should be used instead of PKCS#1 v1.5 compatible padding. Otherwise the PKCS#1 v1.5 unpadding must be performed in such a way that padding oracle attacks are impossible.

With regards to this specific protocol it seems that signatures are handled by a separate document: JSON Web Signature (JWS). Section 11.4 is called "11.4.  Adaptive Chosen-Ciphertext Attacks" and explains the attack on PKCS#1 described above.


Method to verify a signed archive's X.509 CoT I am trying to understand the key high level details behind verifying trust when downloading an archive.

This is my understanding of how it could be done:

On the Software Developer side:

Obtain a certificate from a public CA like verisign
Generate a hash of your archive and then encrypt this string using the private key from your certificate, this is the "signature"
Host the archive for download, along with a separate file which contains the public key from your certificate + the signature generated in step 2.

On the (user) client side:

Download and unpack the archive, download the signature + public key file
Decrypt the downloaded signature using the downloaded public key, save this value
Iterate through the public root certificates embedded within your operating system. For each root certificate, decrypt the signature value and compare the result to the result in step 2.
Once a match is found in 3, you have verified that the author's private key descends from the chain of trust of the CA which you found matched in step 3
Note: This all assumes that the software developer used a CA for which we have an embedded root certificate in our clients OS.

Questions:

Is the above method sound, or am I overlooking key details?
Given a blank slate client, if I wanted to combine the public key + signature + archive into a single file that I could make the client understand and parse, are there any widely supported formats to leverage for organizing this data?

On the Software Developer side:

  Obtain a certificate from a public CA like verisign

Yes, you could use a CA, but you could also host your own CA. You'd of course need your clients to trust this CA.

Obtaining a certificate is probably more economic in the long term though.

  Generate a hash of your archive and then encrypt this string using the private key from your certificate, this is the "signature"

The signature generation in general contains the hashing operation. The hash algorithm is a parameter to the signature generation algorithm. The hash doesn't need to be encrypted, for instance ECDSA is not used for encryption.

Sometimes a hash tree is used instead - the hash over the data is not directly signed, but the hash is included in a structure also containing meta data (e.g. the MIME type of the data), and that structure is signed.

  Host the archive for download, along with a separate file which contains the public key from your certificate + the signature generated in step 2.

No, you'd leave the public key within the certificate. You can used either attached or detached signatures (see below).

On the (user) client side:

  Download and unpack the archive, download the signature + public key file

Right. Except that the public key file would be a certificate.

  Decrypt the downloaded signature using the downloaded public key, save this value

See above, decryption is not always used.

  Iterate through the public root certificates embedded within your operating system. For each root certificate, decrypt the signature value and compare the result to the result in step 2.

The chain is probably longer than two certificates (containing intermediate / server certificates), and certificates helpfully contain one or more "Issuer" fields to look up the higher level certificate. So there is no need to search for the root certificate top-down.

  Once a match is found in 3, you have verified that the author's private key descends from the chain of trust of the CA which you found matched in step 3 Note: This all assumes that the software developer used a CA for which we have an embedded root certificate in our clients OS.

Yes, by verifying the signatures in the certificates, but also validate CRL's for revocation, validate that the certificate is within the validity period, etc. etc.

Questions:

  Is the above method sound, or am I overlooking key details?

Yes, see above.

  Given a blank slate client, if I wanted to combine the public key + signature + archive into a single file that I could make the client understand and parse, are there any widely supported formats to leverage for organizing this data?

For systems using PKIX (Public Key Infrastructure using X5.09 certificates as issued by - for instance -Verisign) the best known container format is probably CMS, the Cryptographic Message Syntax.

There are of course various package managers (or "stores" nowadays) that may describe how software needs to be signed or otherwise managed. It could well be that they in turn use CMS to sign the software, but other protocols may be used as well.


How can I get select messages ciphers for salsa20poly1305 for unit tests? In order to avoid memory errors, I always write safe C++ wrappers with strong type-safety for any C encryption library I use.

To test my wrapper of crypto_secretbox_xsalsa20poly1305 of libsodium and make sure I'm using it correctly, I need a set of messages, nonces and keys that someone used and encrypted and the outcome of that. This is necessary for unit tests.

In OpenSSL, when I do that, I usually use the terminal, and pipe from the terminal to my unit tests and compare the output of my result.

There doesn't seem to be a terminal tool for libsodium. So I'm hoping there's either an online service that does this (take msg + nonce + key and produce cipher + mac), or someone here could provide a few test
messages and their expected mac + cipher in hex.

Just use the test vector specified by DJB himself, specified here, chapter 4 (just XSalsa20) and chapter 10 for the box. This will already test all your primitives.

To perform boundary tests, I would strongly suggest you first document the boundaries. These are the places where there is a difference in e.g. buffer handling for the MAC function. If you test those boundaries against your own library then the MAC will still generate the same wrong value.

There seems to be TweetNaCl.js available online, so you can generate your own vectors after establishing your boundaries.


Why are homomorphic algorithms slow? Why are homomorphic algorithms slower than regular(symmetric and asymmetric) algorithms?

For example RSA in regular asymmetric cryptography uses the same algorithm as in RSA homomorphic (partially HE) cryptography.

but in homomorphic Whereas there isn't decryption time for execution time homomorphic is slow?

We consider the following cases.

Somewhat Homomorphic Schemes(SHS), Fully H.S. (FHS) and Partially Homomorphic Schemes (i.e. homomorphic with respect one operation, either addition or multiplication). RSA belongs to the third case, which is multiplicative homomorphic and is fast.
Remark that, the textbook-RSA is multiplicative homomorphic and  so insecure, since we do not use a secure padding scheme.
A secure cryptosystem in this class is the Pallier's additive homomorphic cryptosystem.

SHS support both operations, addition and multiplication but up to some level. In these systems, beyond some level, the noise to the ciphertext increases so much as a result the decryption is not correct.
There are many SHS such as, the family based on the Learning With Errors problem. These systems are slow because they use large keys in order to get the necessary security.

FHS start with a SHS (all SHS are noisy encryption schemes). The construction of Gentry, found a way to refresh the ciphertext in order to decrease the noise (bootstrapping). The reason that make them slow is the bootstrapping step. It applies an operation to ciphertext called ${\tt Recrypt}$, which increases the complexity of the system but also manages to control the noise. So allows as many operation we want and the decryption will be correct. I suggest you to read the original paper of Gentry for the case of FHE. Also see this post.


One time pad - how is the difference in length between the plain text & the OTP handled? Since OTP have to be agreed upon in advance, they may be longer than the plaintext. So in this case, how is the encryption done? Is the OTP truncated to the same length of the plaintext before encrypting or is some kind of padding used - how does it work?
I am talking about the case where Alice & Bob exchange a book of One Time Pads. Each page of the Pad is used for one plaintext encryption. So each page is of a fixed length & is always longer than the plaintext which it encrypts. So how is the difference in length handled?
As per Dan Boneh's book, a scheme which leaks the length of the plaintext cannot satisfy the definition of perfect security. If we only use that much part of the OTP same as the length of the plaintext, then we are essentially leaking the length of the plaintext because then ciphertext is same length of the plaintext. So how is this handled? I am looking for an authoritative source on how this is handled? Is it via padding? If so, how is the padding done?

In OTP, one party generates a uniform randomly key, writes it in a roll of paper, or a book, or CD, or USB. They transmit it in person with reliable people to the other side.
The OTP keystream obviously is a long stream to long-time use, i.e. one can encrypt many messages over time without using any bits again. If a predetermined size exists to achieve the perfect secrecy, the long stream must be divided into chunks.

OTP with hiding the maximum possible length of the message;
Wikipadia defn;

One-time pads are "information-theoretically secure" in that the ciphertext provides no information about the original message to a cryptanalyst (except the maximum possible length of the message).

Let both parties agree on a maximum length of the messages in advance, say $t$.
Let the keystream is represented by $k_i$ and the message to be encrypted be $m$ with length $\ell$. Then the encryption is performed with the first $\ell$ part of the message. The remaining part is padded, here 10..0 bit padding is used since it is easy to apply even by hand.
\begin{align}
 c_i &= k_i \oplus m_i , \quad\text{for } 0\leq i < \ell\\
 c_{\ell} &= k_1 \oplus 1\\
 c_i &= k_i , \quad\quad\quad\;\; \text{for } \ell < i < t\\
\end{align}

One time pad - how is the difference in length between the plain text & the OTP handled?

Two cases we have;

The OTP keystream is shorter: in this case, one should not send reusing the keystream. Otherwise, two(or many)-time pad use occurs, and that OTP is no longer informationally secure and can be broken.

How does one attack a two-time pad (i.e. one-time pad with key reuse)?

Taking advantage of one-time pad key reuse?

One can break the messages into parts. This, however, may leak the information about the message length is longer than $t$ if the adversary observing the message traffic and two consecutive message sending is unusual.

The OTP keystream is longer: The 10.. padding as above.

10..0 padding (bit padding)
The padding simply works as adding 1 to the message then adding as many as 0s to fill the message size and possibly none. Consider only 16-bit length fixed messages;
message1 = 1010110          wiht padded 1010110100000000
message2 = 101011101100101  wiht padded 1010111011001011

The unpadding (removing the padding) starts from the end of the message, remove the trailing zeros if there are any, and then one 1.
Note that to work with the fixed messages, the length of the message must be one bit less than the fixed size. Otherwise, one cannot decide that the padded message 1010111011001011 is message2: 101011101100101 or 1010111011001011.
Other paddings
The bit padding works for bits, there are other paddings that works in the binary case;

ANSI X9.23 : Block-based padding, the remaining bytes in the last block is filled with 00 and finally the length of the padding is added.
ISO 10126 : Same as above, instead of 00s random bytes are added
PKCS#5 and PKCS#7 : can only support a message size of fewer than 256 bytes.
ISO/IEC 7816-4: Identical to the bit padding, the byte 80 is added then the remaining bytes are set to 00

Historical paddings:
In short, currently none.

Currently, the first describer is Frank Miller in 1882. the OTP is patented by Gilbert Vernam in 1919 (U.S. Patent 1,310,719) this patent doesn't include any padding.

The Venona project doesn't mention either

Shannon doesn't define either


What is difference between Zero Knowledge proof and Zero Knowledge Proof of Knowledge? In a zero knowledge proof, a prover interactively proves to a verifier that an NP statement is true. If the language is an NP complete language and if the prover runs in poly time, the only way a prover could make such a proof is when it has a witness. So, when a prover provides a ZK proof for an NP complete statement, the prover is proving he has knowledge of a satisfying witness.

So, what is a Zero knowledge proof of knowledge? How is it different from Zero knowledge?

How do you define "having" or "knowing" the witness?

This question, which is much less intuitive than it may seem, is the core reason behind the difference between proofs of language membership and proofs of knowledge. Even though it seems intuitively true, there is no known general reduction from "I can prove that this word belongs to this language" to "I know a NP-witness for this statement". The latter is, in fact, a much stronger requirement - we are asking about a specific piece of information $w$ such that some fixed polynomial-time relation $R$ outputs 1 on $(x,w)$ (where $x$ is the statement). As far as we know, it might be that someone can "prove that $x$ is in the language", in the sense of being able to send the appropriate messages in an interactive and probabilistic proof, without knowing the static and deterministic proof (i.e., the witness). It also often occurs that the language is trivial (every word belongs to the language), yet it is defined by a specific relation such that it is non-trivial to know a witness for a given word, with respect to this relation.

Well, let me give you an example: fix some prime-order cyclic group $\mathbb{G}$ with generator $g$, and consider the language $L = \{x \in \mathbb{G} : \exists w, x = g^w\}$. Yes, this is a trivial language: since $\mathbb{G}$ is cyclic, every element of $\mathbb{G}$ belongs to $L$. This means that the following is a valid interactive proof of language membership: the prover sends nothing, the verifier checks that $x$ is an element of the group $\mathbb{G}$, and accepts if it holds. But now, consider the relation that I used to define this language: $R(x,w) = 1$ iff $g^w = x$. Clearly, knowing a witness $w$ with respect to this specific relation is much stronger than just being able to show language membership: in the first case, we must show that we know the discrete log of $x$ in base $g$, while in the latter, there is nothing to do.

Now, to answer my own initial question: in cryptography, we define knowledge by saying that a party knows some information if this information can be efficiently learned from this party. Formally, this is stated as follows: a proof is a proof of knowledge of a witness $w$ if there exists a probabilistic polynomial-time extractor which, given the code of the prover, is able to extract the witness $w$ from the prover. This property is crucial in many security analysis. Typically, we will want show that a cheating prover allows us to reach a contradiction to some security property, and the extractor will help us in deriving this contradiction.


In Multi-party communication, how can I find that one encrypted value is negative or not? I'm using Pailier Cryptosystem as an additive homomorphic system in my scenario. I have two parties: Alice and Bob.
Alice has one pair of (SK, Pk) keys. She encryptes one value using her public key and sends it to Bob. In Bob's side, we need to define whether this value is negative or positive.
How can I achieve that?

Assume that there is a such function $f$, that can determine the sign of the number within the ciphertext .

Let the message space $P$
Using the binary technique, then an adversary can actually find the message as; where $c$ is the ciphertext

if  $f( c - E_p( |P|/2 ))$ > 0
  if $f( c - E_p( |P| ))$ > 0
else if $f( c - E_p( 0 ))$ > 0...

As usual binary search.


How does EAP-TLS authenticate? I understand that a client and server certificate is required, however the validation process isn't clear to me.

Is it simply that the certificates are check to ensure they're valid, aren't revoked, and are signed by the same root ca? Can certificates from different root CAs (both trusted by client and server) be used? Are there any other specific checks?

Sources

https://www.juniper.net/documentation/en_US/sbr-carrier7.5.0/information-products/topic-collections/sbr-admin-guide-10/index.html?id-98057.html
https://tools.ietf.org/html/rfc5216

If CA certificates are trusted by client and server both, than an CA certificate will work.
However, apart from CA Signer (CA certificates), you can also validate the certificate subject CN name. [ this functionality is not provided by all the product ]

Process in details:

Negotiation (SSL Handshake)
Server Sends its Server Certificate to Client. (s - > c)
2.a Client validate that signer of certificates provided by server is in its trust-store.
Client Sends its Client Certificate to Server (c -> s)
3.a Server validates that the signer of certificate provided by client is present in it's trust-store.
Than, they exchange master-key.
Handshake done, and data transmission over synchronise encryption.


How can an adversary use Mac(.) with a new key to compute a tag although this is not a query to Mac oracle? I am having some troubles understanding the power of an adversary in attack against a MAC.

In chapter 4 in Introduction of Modern Cryptography by Jonathan Katz and Yehuda Lindell, specifically in the message authentication experiment ($Mac-forge_{A,\Pi}(n)$), an adversary $A$ is given access to MAC oracle $Mac_k(\cdot)$ where $k$ is previously generated by $Gen$. So my question is: Is it right that $A$ can only access to $Mac(\cdot)$ with a fixed key $k$? Can $A$ access to $Mac(\cdot)$ with a different key $k'$ in a same experiment?
In the paper The Power of Verification Queries in Message Authentication and Authenticated Encryption, specifically in Claim 4.2, it is stated that adversary $A$ simply runs algorithm $Mac(\cdot)$ with key $L$ and message $M$ (where $L$ is a key forged by $A$). I do not understand this part.

Question: How does $A$ run the algorithm if it is not a $Mac$ query? If possible, could you please provide an example in reality?

In modern cryptography it is generally assumed that algorithms are public and only the key is kept private.
Thus, the adversary can compute $\operatorname{Mac}(k', m)$ for any key $k'$ and message $m$.

The oracle $\operatorname{Mac}_k(\cdot)$ in the experiment allows $A$ to additionally receive valid macs under the challenge-key $k$ for which it is supposed to forge a valid mac (for some message $m^\ast$ that it has not queried from said oracle).

The same goes for the second part of your question: the algorithm is public, so $A$ can run it on any input.


What does "crypto_box" actually mean in libsodium and NaCl? I cannot find what "crypto_box" actually means. In general, and in specific cases, what does "box" do? I know that libsodium is authenticated encryption, but GPG is not. "Box" makes me think the encryption and signing are somehow sealed and protected.

What does "crypto_box" mean in libsodium and NaCl?

What does "cryptobox" mean in Libsodium and NaCl? In general, and in specific case, what does "box" do?

cryptobox or correctly crypto_box is just box. box_easy calls secretbox with the shared key between the sender and receiver, unique per direction. box_seal calls box_easy with a random sender secret key and prepends the ciphertext with its corresponding public key. secretbox does the symmetric authenticated encryption.

crypto_box_easy(ciphertext, MESSAGE, MESSAGE_LEN, nonce,
                    bob_publickey, alice_secretkey)
crypto_box_seal(ciphertext, MESSAGE, MESSAGE_LEN, recipient_pk);
crypto_secretbox_easy(ciphertext, MESSAGE, MESSAGE_LEN, nonce, key);

  I know that libsodium is authenticated encryption, but gpg is not. "Box" makes me think the encryption and signing are somehow sealed and protected.

Both secretbox and GPG/PGP use authenticated encryption. box (deniably) authenticates the sender without a signature. box uses Diffie-Hellman to derive a key which requires either of the sender or receiver's secret key to compute. Consequently, if an adversary steals Alice' key, they may impersonate Bob to Alice; this attack is known as Key Compromise Impersonation.

PGP is vulnerable to a related attack by using sign-then-encrypt. I.e. If Alice signs a message and encrypts it for Bob, Bob may decrypt it and encrypt it for Carol. When Carol decrypts the message, she may believe Alice sent her the message, because Alice did, in fact, sign it.

Libsodium's box is better than PGP's sign-then-encrypt but we can do even better when both parties can send messages to the other. I.e Triple-DH used in Signal (ignore the prekey extension). Edit: Although I'd rather avoid signatures, I should have included this. Signatures may be combined appropriately by signing the (message, recipient public key) tuple; such that signature validation with the incorrect recipient fails to verify.


is using secp256k1 curve for ECIES considered safe? I read SafeCurves it indicates Secp256k1 is not SafeCurve by their standards but bitcoin and ETH use it in their blockchain.

I researched more and figured out that using Secp256k1 ECDSA(singing algorithm not encrypting)
is safe and has no problem, since those laking standards are not important in ECDSA but are in ECIES

so my questions are :

how much Unsafe is using secp256k1 for ECIES and what dangers/weakness it exposes
/what attack it makes possible
should I avoid secp256k1 completely(for ECIES) or I can use in some circumstances
what cures are safe for ECIES  (since Curve25519 is only implemented for ECDSA)

How much Unsafe is using secp256k1 for ECIES and what dangers/weakness it exposes /what attack it makes possible?

Let's have a look through the "failures" that secp256k1 achieves according to SafeCurves.

ECDLP: "disc": This means that the curve has a specific value to be small. As the website indicates this is not inherently bad or exploitable, it just means a (minor?) speedup is possible for the brute-force search. Because a large value is "safer" here a curve has to achieve that.
ECC: "ladder": This means that a naturally fast and side-channel resistant scalar multiplication algorithm isn't possible for this curve. However side-channel resistant implementation is still possible (though it requires a bit more care).
ECC: "complete": This means you have to do a case-distinction if you want to add two points $P,Q$ (in theory making side-channel resistant implementations harder). However this is irrelevant in practise given that the case distinction for secp256k1 is "$Q=-P$" or "$Q=P$" or "$Q\neq \pm P$" and for any sane scalar multiplication algorithm we can in fact predict which case will happen at any point with 100% accurcacy, so the fact that there is a case distinction doesn't matter.
ECC: "ind": This means that if you are given a string you can efficiently decide whether you're looking at a random string or a random point on the curve. This most likely won't matter to you unless you have some super fancy protocol that relies on this property, but things like ECDSA and ECDH / ECIES are not included in this.

  Should I avoid secp256k1 completely or I can use in some circumstances?

For "standard" use-cases, i.e. ECDH / ECIES / ECDSA and similar "simple" applications you can use secp256k1 just like Curve25519 assuming you have a secure implementation. The only place where you can't is when you need the indistinguishability property, but that seems to not be the case here.

  What cures are safe for ECIES (since Curve25519 is only implemented for ECDSA)?

Curve25519 should be usable for ECIES given that ECIES is essentially "do a ECDH key exchange with a fixed public key and then hash to shared secret to be used as a symmetric key" and the standardized version of Curve25519 for Diffie-Hellman is also sometimes called X25519.


Attacks on code misusing RSA_public_decrypt I've encountered some code that I'm reviewing that is misusing RSA_public_decrypt to "authenticate" a variable-length response without using any hash. The code assumes that a successful decryption means that the given data buffer was generated by the server and processes it without any additional checks.

I believe that this is unsafe, even though the code is using the RSA_PKCS1_PADDING mode. Is there a reference to a set of attacks on misuse of RSA in this way?

For additional context, this code is using a 2048-bit key with e=3.

In OpenSSL 1.0.2 (and former) at least, based on its documentation and code of an implementation, the big picture is that RSA_public_decrypt with RSA_PKCS1_PADDING applies the RSA public-key transformation $S\mapsto S^e\bmod N$ where $S$ is the alleged signature, then checks that the outcome (considered as a big-endian bytestring of the same size as $N$) is of the following form
$$\mathtt{00}\mathbin\|\mathtt{01}\mathbin\|\underbrace{\mathtt{FF}\ldots\mathtt{FF}}_{\ge8\text{ bytes}}\mathbin\|\mathtt{00}\mathbin\|D$$
and in the affirmative returns the bytestring $D$, and its length.

However, implementation is configuration dependent. Sticking to openssl-1.0.2t, RSA_public_decrypt of rsa_crpt.c can vector to a number of things, including RSA_eay_public_decrypt of rsa_eay.c with padding checks in RSA_padding_check_PKCS1_type_1 of rsa_pk1.c, but also to various other engines for HSM, Smart Card, OS-dependent service (like CryptoAPI on Windows). Thus exactly what it does is quite configuration-dependent. In particular:

Implementations should check that $S<N$, and the aforementioned version of RSA_eay_public_decrypt does, but some implementations do not. The main cryptographic significance is that, if this check is not performed, it is possible to transform a rightful signature $S$ into into another accepted one $S'=S+jN$ (depending on if there is a length check for $S$, that could be for all or a fraction of rightful $S$). In the context of the question where the easiest forgeries $S$ are much smaller than $N$, $S+N$ would typically have the right size, and would look less regular (thus suspicious) to the naked eye.
Implementations often accept that the leading $\mathtt{00}$ is absent, and the aforementioned RSA_padding_check_PKCS1_type_1 does. There might be some even more lenient checks in other implementations. Either would give more freedom in the following attack.

  code (..) is misusing RSA_public_decrypt to "authenticate" a variable-length response without using any hash. The code assumes that a successful decryption means that the given data buffer was generated by the server and processes it without any additional checks.
  (..) 2048-bit key with $e=3$.

With these parameters, it's indeed possible to forge the signature for a number of $D$. In particular, it is enough that $\mathtt{00}\mathbin\|\mathtt{01}\mathbin\|\mathtt{FF}\ldots\mathtt{FF}\mathbin\|\mathtt{00}\mathbin\|D$ is a $e^\text{th}$ power. If the key is $k$-bit, and $\tilde k=8\lceil k/8\rceil$, it is enough that $D$ is the low-order $\tilde k/8-11$ bytes of $S^e$ with $S$ the signature in the integer range
$$\Biggl[\;\biggl\lceil\sqrt[e]{2^{\tilde k-15}-2^{\tilde k-80}}\;\biggr\rceil\;,\ \biggl\lfloor\sqrt[e]{2^{\tilde k-15}-2^{\tilde k-80}+2^{\tilde k-88}-1}\biggr\rfloor\;\Biggr]$$

For small enough $e$, this interval in non-empty, and it is possible to obtain $D$ with some of its left bits at a chosen value, by putting the others at zero and computing $S$ as $\biggl\lceil\sqrt[e]{2^{\tilde k-15}-2^{\tilde k-80}+D}\;\biggr\rceil$. More (smaller, possibly empty) intervals are possible for shorter $D$.

Here $k=\tilde k=2048$, $e=3$, that interval contains over $>2^{603}$ signatures $S$, and there are as many 245-byte $D$. One such signature $S$ is

00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000032cbfd4a7adc7905583fd1456434c26cdf83a920b31e26cc57a313376f4148ebf9544218c1bdc0793bf961895224ef87d397320d586eb7c6ce051ad3fe93b96e22c7f1ec329b88780a17483947fbb7bf3707b0f445

with $S^3$ equal to

0001ffffffffffffffff0077652063616e20666f7267652061207369676e6174757265206f7574206f66206e6f776865726500000000000000000000000000000000000000000000000000000000000000000000000018e546e7c17e2565ec99cfa7249fd76b89b819c73a68a5e19d0302472cdd57230fb23fba23f25e9e76d6345156620f5ecabd14f65fd2fd230a38a769eb521b6e61ac9d9a995e857d03525128e8c1689814fec44d88abded8e3ee67e87b227536f1c42b9a8a1c08d918de54653f8cb1cd54699edfd00763fb0644e304c9644b87b75731bd6fabe7920bb47ba3151f614256814655db5ced95b7c480c5daf51d96145dc26d831fea327f3d

thus this $S$ is acceptable (regardless of the value of the public key) by most RSA_public_decrypt, and produces a 245-byte $D$ of

77652063616e20666f7267652061207369676e6174757265206f7574206f66206e6f776865726500000000000000000000000000000000000000000000000000000000000000000000000018e546e7c17e2565ec99cfa7249fd76b89b819c73a68a5e19d0302472cdd57230fb23fba23f25e9e76d6345156620f5ecabd14f65fd2fd230a38a769eb521b6e61ac9d9a995e857d03525128e8c1689814fec44d88abded8e3ee67e87b227536f1c42b9a8a1c08d918de54653f8cb1cd54699edfd00763fb0644e304c9644b87b75731bd6fabe7920bb47ba3151f614256814655db5ced95b7c480c5daf51d96145dc26d831fea327f3d

which, when interpreted as a C string in ASCII or UTF-8, is the string

we can forge a signature out of nowhere

The LLL algorithm may allow further forgeries, I'm not a specialist of that.


Elliptic Curve Cryptography Encryption Results I'm playing around with a package that does Elliptic Curve Cryptography from http://jecc.sourceforge.net/

Every time I encrypt a value it produced a different result (same private key). However I'm always able to decrypt this result with the related public key. For a 1 byte result the resulting data is 34 bytes, 2 bytes the resulting data is 35 bytes. I assume some knowledge of the curve is contained in the result.

Is this a feature of ECC or would you assume it is just this implementation?

It has to be this way.

First, if it was deterministic, you could trivially break the encryption. Say the encrypted message was a response to "which candidate for President do you vote for". An attacker would simply need to encrypt each candidate's name and see the response that matched the encrypted data.

Second, if it was the same length as the encrypted data, you'd have at least two problems. First, short messages could be trivially brute forced. For example, if the output were only two bytes (for any input) you could encrypt messages until you got a match. Second, there's an obvious pigeonhole problem for messages of any length. You can't encrypt all possible X byte messages into an X byte output unless the relationship is one-to-one, which requires it to be deterministic which fails for the reasons I explained above.

I'm not specifically familiar with jecc, but the usual way to use ECC for encryption (IES) involves two random steps. First, the data to be encrypted is encrypted with a random symmetric key. Second, a random public/private ECC key pair is used in the encryption of the symmetric key. This explains both the indeterminism and the length.


How does one implement the Inverse of AES' MixColumns I got an answer in the related question about Mixcolumn for encryption, but how about decryption?

what will I do?

Because it said that I will used this:

  During decryption the Mix Column the multiplication matrix is changed
  to:

0E 0B 0D 09
09 0E 0B 0D
0D 09 0E 0B
0B 0D 09 0E

How does one implement this maxtrix multiplication?

It's pretty much the same as the forward Mix Column direction; it's a series of multiplications in $GF(2^8)$, however, instead of multiplying by 1, 2 and 3, you're multiplying by 9, 11, 13 and 14.

The multiplication rule isn't that complex; however, it is a bit fancier than the quick rule we got for $\times 2$ and $\times 3$.  If you're happy with doing a table lookup, this wikipedia page gives tables of values for $x\times 9$, $x\times 11$, $x \times 13$ and $x \times 14$.

Another way to approach it is to take the rule you already know for $x \times 2$, and use it several times, as in:

$x \times 9 = (((x \times 2) \times 2) \times 2) + x$

$x \times 11 = ((((x \times 2) \times 2) + x) \times 2) + x$

$x \times 13 = ((((x \times 2) + x) \times 2) \times 2) + x$

$x \times 14 = ((((x \times 2) + x) \times 2) + x) \times 2$

(where $+$ is addition in $GF(2^8)$; you know it better as "exclusive-or")

Further explination would require me to get into the technicalities of what multiplication in a finite field actually is; I'm not sure you're quite ready for that; if you think you might be, you might want to start in on this article.


Asymptotic Hash Function and Concrete Hash Function I'm reading Collision-Resistant Hashing: Towards Making UOWHFs Practical, and they

say that its formalization is non-asymptotic. Why is the formalization non-asymptotic?

What is an example of hash function with an asymptotic formlization?

An asymptotic formalization cares only about what happens when the security parameter becomes "large enough". Since we use (essentially) one fixed security parameter, it is certainly possible to construct cryptosystems that would be insecure for some fixed security parameters, but secure in an asymptotic formalization.

This means that a non-asymptotic formalization is to be preferred over an asymptotic formalization (although the latter may be "cleaner").

A silly example is the following construction of a compression function (which should exist under reasonable number-theoretic assumptions):

For $n \leq 10000$, let $p_n = 10^n$. For $n > 10000$, let $u_n$ be the integer made up of the first $n$ decimal digits of $\pi$, and let $p_n$ be the smallest safe prime larger than $u_n$. Let $g=4$ and $h_n$ be the integer we get from the first $n$ decimal digits of $e$.

Let $f_n:\{0,1,\dots,\lfloor (p_n-1)/2 \rfloor\}^2 \rightarrow \{0,1,\dots,p_n-1\}$ be defined by
$$f_n(x,y) = g^x h_n^{2y} \bmod p_n .$$

Under reasonable number-theoretic assumptions (that it is asymptotically hard to compute the logarithm of $h_n^2$ to the base $g$ modulo $p_n$), this is asymptotically collision resistant. But for any security parameter $n$ that we would like to use, it is easy to find collisions.

(Note that we can flip this construction around to get a compression function family that is (under reasonable assumptions) collision resistant for any security parameter we care to use, but asymptotically insecure.)


Reversing Rotation + XOR I have this cypher which is as follows :

Take 2 numbers : A=1011 and B=1010

if the ith bit of A is 1 then shift B i times to the left.
So in the end you will get something like

   1010
  1010
1010

So now you Apply XOR on these numbers which results in :

00001010
00010100 (XOR)
01010000 (XOR)
---------
01001110

So you end up getting 2 4-bit numbers from 01001110: that is 0100 & 1110

So now given 0100 & 1110 how do I reverse this and find the initial A & B

PS : I am a complete newbie when it comes to crypto so please explain it like how you would explain it to a noob.

While you're a crypto newbie, I hope that you know something about mathematics (because you've stumbled something that needs to be described in mathematical terms).  What you've described here is actually polynomial multiplication (over polynomials in $GF(2)$ (that is, we do our computations modulo 2).

That is, you can interpret the numbers as specifying a polynomial (where each bit indicates whether the coefficient of the polynomial is either 0 or 1; for example, 1011 would correspond to the polynomial $x^3 + x + 1$, and 1010 would correspond to the polynomial $x^3 + x$.  When you perform your operation, you generate the product polynomial, in this case $(x^3 + x + 1) \times (x^3 + x) = x^6 + 2x^4 + x^3 + x^2 + x = x^6 + x^3 + x^2 + x$ (this last step of dropping $x^4$ happens because we're computing everything in $GF(2)$

With that in mind, the problem of reversing the operation is actually a factorization problem (not factorization over the integers, which is what people generally think about when factorization is brought up, but its analogue over polynomials).

This implies that:

The values $A$ and $B$ need not be unique.  For one, the operation is actually symmetric (even if your algorithm to perform it is not); swapping $A$ and $B$ will always result in the same product, and so another solution in your case is $A = 1010$ and $B = 1011$.
More generally, as yyyyyyy referenced, the factorization process can reduce the product to its prime factors, but there might be multiple ways to reassemble these prime factors (for example, the prime factorization of $1010 = 11 \times 11 \times 10$).  It terms out that $1011$ is prime (and hence if we limit our multiplicands to 4 bits, $1011$ and $1010$ are the only two possible factors), however this won't be the case in general.

And if you're asking whether factorization is a hard problem, it is not.  There are known polynomial time factorization methods over polynomials (this is one way where factorization over the integers differs from factorization over polynomials).  However, those techniques are a bit beyond what a newbie can be expected to understand.


Has SHA256 been broken by Treadwell Stanton DuPont? In a recent press release issued by Treadwell Stanton DuPont, the claim is made that their research laboratories have successfully broken all 64 rounds of the SHA256 hashing algorithm. They further claim that they achieved this milestone a year ago (late 2018).

  "While we have successfully broken all 64 rounds of pre-image
  resistance," said Seiijiro Takamoto, Treadwell Stanton DuPont's
  director of newly formed Hardware Engineering Division, "it is not our
  intention to bring down Bitcoin, break SSL/TLS security or crack any
  financial sector security whatsoever."

How credible is this claim in the wider cryptographic community?

[Update, 2019-09-12: Upon being exposed, and/or after taking advantage of market manipulation by their fraudulent announcements, the scam artists of Treadwell Stanton DuPont have retracted their claim, with more meaningless waffling technobabble about ‘laboratory equipment flaws’ and ‘ambiguous results’—yet they are still selling the same snake oil!  I leave the commentary below as a record of their fraud, including magic market prediction oracles they continue to hawk as well.]

[Update, 2019-09-18: Now the scam artists of Treadwell Stanton DuPont are just straight up asking for donations, perhaps because the world pointed out they don't actually have anything to sell but they still want to take your money and haven't found a productive way to contribute to society in exchange for it.]

  How credible is this claim in the wider cryptographic community?

It is balderdash by scam artists trying to bamboozle people into buying fintech snake oil, using meaningless technobabble (plus quantum!), a virtual office address on Wall Street, and a slick-looking web site with sleek gadget photos and impossible claims about market prediction.

There is no merit to this claim.  If they actually had this capacity, they could easily demonstrate it by showing a SHA-256 collision, or a message whose SHA-256 hash is all bits zero.  Since they are running an elaborate fraud, rather than doing cryptography, obviously they cannot do this.  But for fun, and to make an indelible record on the web for the chumps who at least have the good sense to search the company's name, let's take a look at these scam artists.

From the press release, archived in case anyone tries to memory-hole it to evade prosecution for fraud.

  "While we have successfully broken all 64 rounds of pre-image resistance," said Seiijiro Takamoto, Treadwell Stanton DuPont's director of newly formed Hardware Engineering Division, "it is not our intention to bring down Bitcoin, break SSL/TLS security or crack any financial sector security whatsoever."

Seiijiro Takamoto does not appear to exist on the web outside the fraudulent press release issued by ‘Treadwell Stanton DuPont’.

  Up to now, it was thought impossible to use the output of the hash function to reconstruct its given input.

They don't seem to be clear on what a preimage attack does.  (If the input is longer than the output, what a preimage attack finds is almost certainly not the original input but another one with the same output.)

  In accordance with its disclosure policy, Treadwell Stanton DuPont won't be saying exactly how they did it — because once the proof-of-concept is out, anyone with enough computing power will be able to produce a SHA-256 collision, rendering the algorithm both insecure and obsolete.

They can't keep their story straight about whether it's a preimage attack or a collision attack.

From their web site, archived:

  While the exploit won’t be detailed here, it does take quite some computing power to achieve, overlapping into the quantum computing realm. So much, in fact, that combinatorial optimization is used, along with a fully connected/coupled 32,768-bit scale, 256-bit gradation solution space, which translates to a maximum of 1.158x1077 gradations of large-scale, precision parallel processing.

wat

  Remember: this is not brute force.

False.  This is a brute force assault on hapless victims by a barrage of technobabble.

  It is not our intention to bring down Bitcoin, which is why only 25 PHAEDRA A3497 and 25 PHAEDRA A3487 Compute Nodes will ever be constructed. Even though preliminary design, manufacturing specification and initial construction work has already begun, it will likely be 12 months before the first compute nodes are delivered to clients, worldwide.

The fraudsters are creating the illusion of scarcity to scare chumps into giving them money as soon as possible, and setting a deadline that gives them plenty of time to walk off with the money and find another scam.

  PHAEDRA A3497 will start shipping around mid-October 2020 at a rate of one per week. PHAEDRA A3487 will follow suit starting around mid-November 2020. Shipped on a first come, first served basis (S&H not included), if you have secured a place amongst any of the two lists (10 BTC and 6 BTC respectively), you can still climb to a higher rank by submitting or resubmitting an accumulative higher bid.

It's first-come-first-served, except if you pay more you can skip the queue!  But you have to pay in BTC, it seems.  I'm sure this is for principled reasons about evil central payment processors like ‘Visa’ who could be capriciously subverted by the judicial overreach of a court order about fraud, and certainly not because BTC transactions are irreversible.

  Timeline:

  Founding.  Treadwell Stanton DuPont is created to research and develop stock market prediction algorithms using artificial intelligence neural networks.

Curious that they waited until 2017 to register their domain name, nine years after their scam was founded.

Their main web page, amazingly, manages to be worse:

  There's only one proven method to beat the stock market: accurate, precise and timely world-class stocks and securities forecasting. It's like having an oracle at your beck and call. Like clockwork, know what's going to happen beforehand, every single time and take the guesswork —and risk— out of wise stock market investing.

In principle there could be a cryptanalytic attack on SHA-256, but the market will be deterministically predictable only when birds like me hang out with airborne pigs.

Here's another product with their name on it, the NEBULA6 SSE Stock and Securities Forecasting Neural Net platform, sold—as a 100 USD brochure—on eBay:

  If you're a sophisticated investor, hear this: Even your initial investment appreciates over time! Treadwell Stanton DuPont accounts are scarce and highly sought-after, and only a few dozens are available (it's free to register). Their value will SKYROCKET in the next, upcoming months, with many standing in-line for a chance to grab an account. ABSOLUTELY NOTHING TO LOOSE! This is a NO-RISK, ZERO LOSS, FAIL-SAFE, FOOL-PROOF investment! EASY TO USE: Even a total newbie who knows next to nothing of the stock market can get up and running in LESS THAN 15 minutes! TSD does not sell securities - they offer extremely accurate stock forecast charts with a degree of precision previously unheard-of, that has until now been the domain of some of the biggest and most established financial players (aka large investment banks).

I'm ready to line up outside their virtual office at 30 Wall Street which is so exclusive anyone on the web can rent it and make my millions!

Maybe they broke into the cryptobabble fintech space because the sketchball eBay fintech predictimacator market was too smart and got wise to them too fast.


Are there any practical attacks that create a printable chosen prefix MD5 collision? I would like to create two ASCII text messages with the same MD5. Is this possible? If not, is there a similar but less strict attack that could work?

Or to rephrase my last question: what are the minimum prerequisites for the message alphabet?

Also: Do the Flame and Hashclash attacks have different prerequisites?

In general, most of the readable MD5 attacks are carried out in formats that make it possible to add non-printing elements, such as postscript. It is hard, yet possible, to create collisions going down to pure ascii or hex. However, they may or most likely will not be readable, and if the hex is doing something meaningful, e.g. assembler code, the code will most likely be faulty.

In general, it is possible when certain bits are changed in certain positions- they have to be identified, by trial and error or looking for flaws, both in the algorithm or the implementation.

Here is a Stack Overflow question on creating collisions: Create your own MD5 collisions


AES-GCM Encryption and Replay Attacks I have a doubt about AES-GCM on how can I avoid replay attacks. We have 2 users (Alice and Bob). After that the entities negotiate crypto parameters and generate a symmetric key, they'll exchange encrypted message.

The possible encryption algorithms are two: AES-128-GCM and AES-128-CBC.
By using AES-128-GCM, Alice and Bob choose the following parameters:

$IV=nonce$ where $nonce$ is a pseudorandom number
$AAD="static-data"$
$K$, a 128 bit key
$D$, the plaintext

Now we suppose that in order to avoid replay attacks, I want to use a timestamp $t$. Is it correct that Alice sends the ciphertext $CT=E_K(IV,AAD,D)$ to Bob together a timestamp $t$ like $CT||t$ or encrypt the timestamp in the ciphertext (and in this case the plaintext $D$ becomes $D||t$) in order to avoid replay attacks ?

Is it correct that Alice sends the ciphertext $CT=E_K(IV,AAD,D)$ to Bob together a timestamp $t$ like $CT||t$

That doesn't work; here, GCM doesn't protect $t$; the attacker can easily change it to anything he wants, and GCM will never notice.

Now, you could expand the AAD to include the value $t$; , that is, we have $CT=E_K(IV,AAD || t,D)$.  With that change, this is safe.  What this does is cryptographically bind the value $t$ to the ciphertext (the GCM tag), if the attacker modifies it, then the tag would not validate.

  or encrypt the timestamp in the ciphertext (and in this case the plaintext $D$ becomes $D||t$)

That also works; in this case, $t$ is cryptographically bound to the ciphertext, and hence cannot be modified.

The main difference between the two is whether the timestamp is in the clear or not.


Why are the first few bytes of a gpg encryption always the same? If I run the command 'gpg -a -e < input.txt > output.txt' with completely different inputs (e.g. from /dev/urandom), the first 19 characters are always the same.  What is this header?  Is it identifying in any way?

For example:

-----BEGIN PGP MESSAGE-----
Version: GnuPG v1.4.11 (GNU/Linux)

hQEMA5QidX3vO49mAQf/dZzGGqfxC/7T7sOM+ome1i7Cwd1e2dOiTvRIA2LYZXpi

and

-----BEGIN PGP MESSAGE-----
Version: GnuPG v1.4.11 (GNU/Linux)

hQEMA5QidX3vO49mAQgAkz+xM9ojPvOBUtDRvCecr344PJbmbaMFxJrpJBICnywE

The first few bytes are the PGP header. They encode the format information, encryption algorithms and the recipient(s) key id. The recipient must know which key to use and how GPG/PGP has encrypted the session key and payload and how the MAC was generated. Like TLS/SSL the OpenPGP standard has a couple of cipher suites and hash algorithms.

The format is defined in RFC 4880 (http://www.ietf.org/rfc/rfc4880.txt). You can inspect the data with the tool pgpdump

$ gpg -a -e test.txt

$ pgpdump -g test.txt.asc
Old: Public-Key Encrypted Session Key Packet(tag 1)(524 bytes)
        New version(3)
        Key ID - 0x59C8FAE9A25222C6
        Pub alg - RSA Encrypt or Sign(pub 1)
        RSA m^e mod n(4095 bits) - ...
                -> m = sym alg(1 byte) + checksum(2 bytes) + PKCS-1 block type 02
New: Symmetrically Encrypted and MDC Packet(tag 18)(110 bytes)
        Ver 1
        Encrypted data [sym alg is specified in pub-key encrypted session key]
                (plain text + MDC SHA1(20 bytes))


How is the MAC or HMAC secret shared with the other party for verification? I've seen people everywhere say to use a MAC or HMAC with block ciphers. I think I understand the basics, but I'm still not sure how the HMAC secret is distributed so the other party can verify that it's valid. Is the secret distributed freely like the IV (though the name suggests it is secret)? Is it part of the ciphertext? Is it sent over a secure channel like the AES key?

Also, is it safe to use the same HMAC secret for each subsequent AES encrypted message after the initial connection? Assuming all keys (other than public/private keypairs) are destroyed after the connection is closed.

It is "sent over a secure channel like the AES key".

It is "safe to use the same HMAC secret for each subsequent
AES encrypted message after the initial connection".


Can ECB be turned into a secure algorithm by adding obfuscation of the plaintext patterns? Just to preface this I'm very new to cryptography. However, I've been reading that ECB should not be used under most circumstances due to its symmetry which allows attackers to gain information about the plaintext from observations of the ciphertext.

It got me thinking about a way obfuscate patterns in the plaintext before encryption occurs.

Let's say for instance each block of plaintext is XOR'd with a randomly generated "key" of maybe 1 or 2 bytes that is stored with the block and then encrypted along with it, effectively hiding any observable pattern.

In this manner wouldn't the obvious attacks that ECB would normally be prone to be completely dismantled?

Let's say for instance

  each block of plaintext is XOR'd with

  a randomly generated key
  that is stored with the block

  and then encrypted along with it, effectively hiding any observable pattern.

For 1. you need as much entropy as the amount of information in the message.

For 2. you need double the storage for ciphertext.

The clever audience may have observed by this point, that it's just a convoluted way to make one-time-pad insecure against unbounded adversary.


Generating passwords using Password-Based Key Derivation Function I was thinking of using different and independent password for different websites, but not storing them in some password manager so I don't need to backup the passwords. I thought I could use some cryptographic technique to do this, and I come up with a script that do the following:

User input a master password into the script.
User input a name, or domain - whatsoever, into the script as site name.
The script use PBKDF2 with HMAC (hashlib.pbkdf2_hmac in Python) to generate a key, using the master password as the password input and site name as salt, 250000 as the number of iterations and 8 bytes as the key length.

Doing this currently takes around 1 second on my computer.
The resulting key is treated as a number, and is converted into base 75. Each resulting digit is then mapped to a character using the following array:

0123456789:;<=>?@ABCDEFGHIJKLMNOPQRSTUVWXYZ[\\]^_`abcdefghijklmnopqrstuvwxyz

The script output the resulting string and that string is used as a password for that site.

There's three goal I want to achieve with this script:

Given the same master password and same site name, the script should output the same string and it is a good secure password to be used on website.
Given only the generated password and site name, it should be impossible for an attacker to compute the master password (At least it should take a long time if the master password is strong).
Given only the generated password and site name, it should also be impossible for an attacker to compute password for other site name.

My question is: is this a secure password generator? The master password I used is basically just like a password that this script will output.

My implementation of this can be found here.

Like I wrote in the comment, the method here is pretty similar. The differences:

Rather than deriving each site password directly from the password, I recommended deriving a single master secret using a password hash and then deriving the site passwords from that using another KDF.
You are truncating the PBKDF2 output to 64 bits.
You define the method of turning the hash into a password explicitly.

Regarding the first, using a single master secret allows you to derive it once and then quickly derive multiple site-specific passwords. (It also uses a known-unique salt, which is nice.) This is not necessary, but does mean you can perhaps use more iterations in some cases.
Truncating to 64 bits should be fine, but is not necessary if you can copy-paste a stronger one. (If your password is complex enough brute forcing the 64-bit hash or the derived password will be faster than attacking the master password.)
The last is problematic. As discussed in the comments to the question I linked above, each site has their own requirements on the password so any static algorithm like that is unlikely to work for all. That is not a security issue, however: as long as you do not drop information from the hash further, any method of encoding it as a password will be fine.

However I'm not sure about if it is OK to use a such simple salt. Like I once heard that salts should be unpredictable...

No, salts only have to be unique. However, if you ever need to change the site password (e.g. their database is stolen and they require new ones), you may need to add something to the site name. Also, theoretically someone else who used the same method could be using the same salt, allowing a faster attack. (Adding e.g. your email address could solve this.)

Other than the downsides I mentioned in the other question (quoted below) there is the question of which password hash to use. PBKDF2 is not exactly the state of the art and using e.g. scrypt might give you a larger advantage over potential adversaries.

If you go this route you are putting all your eggs in one basket. If you forget the master password, you lose all the derived ones. If someone guesses it, they can derive all the others.
You would probably be better off just using a password manager that prevents guessing attacks. Otherwise the master must be very strong. A password manager generates random site passwords that leak no information about the master.


How to determine RSA block size for decryption A message coded with RSA is broken up into blocks, then padded/transformed prior to encryption via modular exponentiation with the public key.  However, the encryption result for each block is not necessarily a fixed length of bits, octets or characters. What are the accepted protocols for delimiting these encrypted blocks so that they can be decrypted with the private key?

Nobody (at least, nobody who does crypto seriously) splits up data into blocks to be independently encrypted with RSA. Not only is this inefficient, in CPU and in network bandwidth (because asymmetric encryption necessarily implies data enlargement), but we do not really know how "safe" it is. This is a little-studied question, so there is no accepted protocol for that.

Real-life protocols that use asymmetric encryption (e.g. CMS or OpenPGP) use hybrid encryption: the asymmetric algorithm is used to convey a symmetric key, which is then used with a symmetric encryption algorithm to process the bulk of the data. This has the extra advantage of also working with key exchange algorithms (like Diffie-Hellman) which are not asymmetric encryption algorithms (in a way, DH can be seen as an asymmetric encryption algorithm where you do not choose what you encrypt).

RSA-encrypting data "directly" is encountered mostly in protocols that must live under strict bandwidth constraints (e.g. in smart cards), where every single byte counts; but in that case, messages are very short, and there is no question of splitting messages into blocks.


What are easy yet fool proof ways of ensuring that AES encryption algorithm works like it should and no bugs/developer mistakes have sneaked in? As a developer when it comes to encryption, there is an insane amount of weakness/mistakes/bugs that the programmer can add to the encryption algorithm.

So a pretty general question to the crypto pro’s, do you guys have maybe a checklist/test cases that you go through after implementing AES-Rijndael-CBC into any application/program to make sure that it works correctly.

The reason for this is when I use any kind of programming language such as python, me and probably most others simply use a prebuilt library for encryptions such as AES CBC and trust that it will simply work correct and be safe. But in reality, I have no idea since it’s just scrambled data in the output...

Is there maybe a trusted online tool or analyzing technique or something similar that we can compare the results to indeed see that our encryption works as good as excepted.
For example, I made IV to all zeros and used an online aes program and the ciphertext was indeed the same so that made me certain that my program was working correctly.
But this is the most simple test of string -> cipher... when we add more functionality to the program such as derived keys and etc, it gets harder and harder to find bugs that we may have accidentally put into the program.

Can we maybe analyze the randomness of bytes in the ciphered text to determine if the entropy is high and random etc... to make sure that our encryption still works as it should?

Thanks beforehand for any tips :)

For this kind of problem, the cryptographic algorithm/protocol designers, usually, presents test vectors for their designs. You can find some of them in books, too.

In your case, AES is standardized by NIST on May 26, 2002, and they provide test vectors in Appendix F of NIST 800-38A for various mode of encryption.

Before the standardization on November 26, 2001, the NIST FIPS 197 document provided
 example vectors in Appendix C. This is a more detailed vector for each round instead of just input and output.

input: cipher input
start: state at start of round[r]
s_box: state after SubBytes()
s_row: state after ShiftRows()
m_col: state after MixColumns()
k_sch: key schedule value for round[r]
output: cipher output


Encryption with two meanings without computer or programming Can one create a cipher with two meanings? Not two layers, two phrases in the same cipher in the way that it would have a meaning X, for example, if deciphered using Transposition cipher and meaning Y if deciphered with the Playfair chipher. Is it possible?

This is possible, and it's called deniable encryption. The idea behind this type of encryption is that if you are required (e.g., under subpoena) to provide a key to decrypt your ciphertext, then you can provide an "alternative key" that decrypts it to something else.

However, this is complex, and you cannot do it by hand. In general, it's difficult to do, even by machine.


Modes of operation that allow padding oracle attacks It seems to me that padding oracle attacks are mainly a concern for users of CBC mode encryption. Question: are any other modes of operation vulnerable to padding oracle attacks? And if so, why?

There was some discussion in the comments section of this answer with regards to ECB, but it didn't reach a conclusion. It would be a surprise to me if ECB would allow padding oracle attacks that give more information than the length of the plaintext, but I'd rather be sure.

The answers only have to address symmetric block ciphers and the modes of operation mentioned on the Wikipedia page.

In the padding oracle attack you have an oracle that only tells you whether a particular chosen ciphertext decrypts to a correctly padded plaintext. That oracle is used to build a last word oracle, which used iteratively can reveal a whole message.

The reason it works in CBC mode is that we can make predictable, arbitrary changes to the plaintext of the last block by modifying the ciphertext (of the second to last block, or the IV):

$$P_i = E(C_{i}) \oplus C_{i-1}$$

For another mode to be vulnerable, the same kind of control would be needed.

  It would be a surprise to me if ECB would allow padding oracle attacks that give more information than the length of the plaintext, but I'd rather be sure.

In ECB, the ciphertext only passes through the decryption function, so any change to it makes an unpredictable change to the only block of plaintext it affects.

Except, there is one predictable change we can make: we can substitute any other ciphertext block of a valid message for the last. If it passes the padding oracle, we know it ends with one of 1, 2|2, ... 16|...|16 (assuming that's the padding mode used), but we can make no other checks.

This is unlikely to help because a textual (ASCII or UTF-8) message will never include most of those – 9|...|9 (tabs) and 10|...|10 (newlines) being the only ones I could imagine seeing. In a "random" binary plaintext, it would be likely you'd see some 1s at least, but that would probably not be helpful.

Still, I guess this leaks information, so it should count as an attack.

  Question: are any other modes of operation vulnerable to padding oracle attacks?

As above, ECB is only partially vulnerable, but how about other modes?

CFB, OFB and CTR all allow predictable changes to the last plaintext block. However, they are essentially stream ciphers that don't require padding. If an implementation does use padding, it could be vulnerable. GCM is authenticated, so it doesn't leave room for the attack, and anyway also doesn't require padding.

For example, here's a padding oracle attack on $b$-byte blocksize CTR padded with $p = 1$ to $b$ bytes each equal to $p$, up to a multiple of the blocksize:

The ciphertext is simply the xor of a message and an IV-derived keystream: $C = M \oplus K$. You know the final 1-$b$ bytes of $M$ will be padding, so you can flip a single bit in the last byte, test it; the second last, test; etc. as long as the oracle returns 0. You will find the padding length, and thus know the last $p$ bytes of both $M$ ($M_i=p$) and $K$ ($K_i=C_i \oplus p$).
Set the last $p$ bytes so that they are correct for a $p+1$ byte padding (or if $p = b$, remove the last block of ciphertext). Now you can try every possible ciphertext byte in the next position ($p+1$ counting from the right). One of them will pass the oracle, returning 1. Now you know the last $p+1$ bytes of both $M$ and $K$.
You can repeat step 2. any number of times, to find the whole keystream and message.


Source for PKCS#11 Header Files Is there a known authoritative source for the ANSI C header files for PKCS#11 Cryptoki? Specifically, I am having trouble locating pkcs11.h, pkcs11t.h, and pkcs11f.h for v2.30 and v2.40. Are there known MD5 or SHA hashes for these files?

The PKCS#11 standard has transitioned from RSA to the OASIS group:
https://www.oasis-open.org/committees/tc_home.php?wg_abbrev=pkcs11

I am not sure why RSA/EMC's site doesn't mention this.

I believe that v2.30 was close to finalization, but was never formally released.  I am not sure what happened but v2.40 is now the current release candidate.

v2.20 is the current revision and header files are accessible by following the link that Mr. Stone provided.

CryptSoft (Tim Hudson is a PKCS#11 leader) has a very good resource page:
http://www.cryptsoft.com/pkcs11doc/


Two different keys decrypting same content is there some generally available algorithm which will encrypt a short string and generate two unique keys so that any of the two can be used to decrypt the message again? It doesn't has to be "super secure".

Most public key encryption schemes, such as PGP, support this.

When you are encrypting  a message to Bob, in fact you are encrypting the message with a random key using a symmetric cipher, then including the key encrypted to the public key of Bob.

$$E_{\text{PK}}(\mathit{Bob}, \mathit{key}) \Vert E_{\text{Symmetric}}(\mathit{key}, \mathit{message})$$

where $\Vert$ denotes concatenation.

If you encrypt the message to Alice and Bob, you are encrypting the same random key to each of their public keys:

$$E_{\text{PK}}(\mathit{Alice}, \mathit{key}) \Vert E_{\text{PK}}(\mathit{Bob}, \mathit{key}) \Vert E_{\text{Symmetric}}(\mathit{key}, \mathit{message})$$

Each of them can decrypt the message.


Why are good passwords required if we use good hashing algorithms? Again and again are we adviced to make good passwords: At least 12 chars, numbers, signs, upper and lowercase.

But why is that really needed?

I can see the need, if the system uses a hashing algorithm that can be implemented in ASIC, where an attacker can test trillions of combinations per second.

But using scrypt, Argon2 and similar technologies we ought to be able to make it so expensive for an attacker that testing just billions of passwords will be infeasible. Both can be tuned to require a massive amount of RAM, and in that configuration they are not at all comparable to MD5, SHA-1, or SHA-2. E.g. if we make the hashing take 3 seconds and use 1 GB RAM it will take 100 CPU-years and 100 GB*years to test just 1 billion combinations.

Would it not be relatively easy to trade compute+RAM ressources for allowing simpler (though not completely trivial) passwords?

First of all, password strength rules like "at least 12 chars, numbers, signs, upper and lowercase" are actually counterproductive — they result in passwords that are only slightly harder to guess but significantly harder to remember, and worse, they also often end up also disallowing passphrases generated by actually secure methods like Diceware.

Their one arguable merit is that they disallow very common weak passwords like "password", "abc123" or "letmein".  Alas, preventing a user from choosing these weak but easy-to-remember passwords will typically just result in them choosing the simplest password that the system will accept, like "Password123!", which is still trivially guessable by any half decent password cracking tool (but now the user is much more likely to forget which punctuation symbol they used and whether they put it before or after the number).

(Another arguable historical rationale for such rules is that using a diverse selection of characters allows squeezing a little bit of extra entropy out of a short password, which could be relevant on systems that severely limit password length, like the old Unix DES-crypt scheme from the 1970s that truncated passwords to at most 8 characters.  But such archaic password hashing schemes are fundamentally unsafe anyway, and mixing a few punctuation characters into your password will not make them safe.  Still, this is likely one reason why such rules were originally introduced and popularized in the first place.)

Anyway, as far as it goes, your math it looks more or less reasonable to me: 3 billion seconds is about 95 years, so if testing a single password takes 3 seconds on a fast CPU, a password with about 30 bits of entropy (i.e. chosen uniformly at random from among $2^{30} \approx$ 1 billion possibilities) will take 95 CPU-years, which most attackers may consider too much effort.  That said, however:

Password cracking is an embarrassingly parallel task, so an attacker willing to dedicate 95 CPU cores to it will shorten the time to just one year.  With 5000 cores (which could be easily within reach of e.g. even a fairly small botnet or a server farm) it comes down to one week.

Also remember that processors still continue to get faster (and/or more parallel) and RAM prices still keep going down.  Not only does this mean that the time cost of cracking any specific password hash goes down over time, but you also cannot assume that all your users have the latest and greatest CPUs, whereas any decently motivated attacker probably does have access to those, or at least to something reasonably close.  Some of your users might be (at least occasionally) using 10 or 20 year old devices with slow CPUs and limited memory, and they'll want to be able to log in using them; an attacker with a botnet will have plenty of newer devices at their disposal.
Three seconds is already a rather awkwardly long time to wait for your password to be accepted.  For infrequent use it can be fine, but do you really want to wait that long every time you log in to a website or return to your workstation from a bathroom break?  I've seen one second listed as the maximum delay that most users are likely to find acceptable, and that's probably pushing it a bit.  Personally, I wouldn't aim much higher than 0.3 to 0.5 seconds.

If you'd like to try a quick experiment, count how many times you have to enter a password (even a prefilled one) or a PIN code per day.  Then try counting slowly ("1 mississippi, 2 mississippi, 3 mississippi") to three before pressing enter each time.  See how long it takes before you get tired of those pauses.
In any case, for authenticating to a remote server such as a website, even 0.3 seconds of key stretching per login is really only feasible if you can do the work on the client.  If you try to do the kind of slow and memory-intensive hashing you suggest on the server side, anyone can bring your server to its knees with a trivial denial-of-service attack just by having a bot try to log in with random usernames and passwords a couple of times a second.  Heck, you could probably do that even without a bot just by repeatedly clicking the login button.

With the Web Crypto API and/or WebAssembly implemented in modern browsers, it would be possible for a website to do key stretching on the client side.  I haven't seen any standards or widely used implementations for this, though, and while doable in principle, it has some nontrivial security and usability pitfalls that any custom implementation would need to be careful to avoid.  Also, it basically makes logging in impossible for users who cannot or will not run JavaScript, as any alternative fallback mechanism could also be abused by attackers.  So, at least for a while now, we're still mostly stuck with server-side password hashing.


Relationship between PRF/KDF/MAC? It seems that not every MAC is a KDF. But would any PRF also work as both KDF and MAC? Could someone explain the relationship between these 3 definitions?

A key derivation function (KDF) takes in some secret keying material, which may or may not be uniformly distributed, and where the adversary may also have some auxiliary information about the keying material or its distribution, and outputs a uniformly distributed bit string. See definitions 5, 6, and 7, here.

Intuitively, a KDF's job is to take in some keying material which has some minimum entropy, but which might not be uniform as a bit string (or not be a bit string at all!), and output a "smooth" bit string of essentially the same entropy as the original input. A classic use case is a Diffie-Hellman (DH) secret obtained from a key exchange protocol. This secret is not a bit string, but rather a group element. Moreover, when encoded as a bit string, this group element will not be uniformly distributed over all bit strings of the corresponding length. However, it does have high entropy, and a KDF can then be used to extract from the secret DH group element a nice and uniformly distributed bit string (i.e., a symmetric key).

The security definition of a KDF (Def. 7 in the link above), is essentially that it should behave like a random function when evaluated on the secret keying material and some arbitrary additional input (there are some additional bells and whistles in Def. 7 provided in the link, but what I said contains the gist of it).
A pseudorandom function (PRF) takes in a secret key and a message, and outputs a bit string. The security requirement for a PRF (see Def. 5.6, here) is that it should behave like a random function when evaluated on arbitrary messages---provided the secret key is uniformly distributed.

Notice that PRFs and KDFs are quite similar, but that a PRF has a much more stringent requirement on its secret key. Essentially, a non-uniformly distributed secret key voids all security guarantees of a PRF.
A message authentication code (MAC) takes in a secret key and a message, and outputs a tag. There is also a corresponding verification algorithm that on input the secret key, a message, and a tag, outputs either VALID/NOT-VALID. The security requirement of a MAC is that for someone not knowing the secret key, it should be hard to come up with a message and a tag, such that the verification algorithm outputs VALID. (Note that this is a very weak form of MAC security, and usually we require something stronger called EUF-CMA security, see Def. 9.1 and Def. 9.2 here).

As for the relationships between them, it follows from what I wrote above that KDF $\implies$ PRF $\implies$ MAC. That is, since a KDF is supposed to behave like a random function even when given a non-uniform secret key, it of course also behaves like a random function when the secret key is uniformly distributed. That a PRF allows you to build a MAC is shown in Section 9.6 here.

In the other direction none of the implications hold generally. That is, it is not the case that all secure MACs are secure PRFs (can you think of a counterexample?), and not all secure PRFs are secure KDFs.


Jpbc secure choice of elliptic curve JPBC library describes 6 types of elliptic curves. This is how they describe type A:

Type A pairings are constructed on the curve  $y^2=x^3+x$ over the field  $\mathbb{F}_q$ for some prime  $q=3 \mod 4$ . Both  $\mathbb{G}_1$ and  $\mathbb{G}_2$ are the group of points  $E(\mathbb{F}_q)$ , so this pairing is symmetric. The order  $r$ is some prime factor of  $q+1$ .

They also offer a curve generator implementation that takes in rBits and qBits values and calculates the q,r,h, exp1, exp2 values.

I would like to know, what rBits and qBits values consider to be secure enough for cryptocurrency wallet security? Also, what is the best type that provides the mentioned security and has the best performance?

I recently implemented BLS signature aggregation using JPBC, and I would like to know what would be the best settings to use in cryptocurrency application that will use it?

Since $\mathbb{G}_T$ is $\mathbb{F}_{q^2}$ in the setting you are mentioning, you would have to choose them so large that your implementation will no longer have the performance one would hope for.

I would recommend to switch to the asymmetric setting. Currently the probably best choice regarding performance and existence of optimised implementations is to use BN parings. However, recent progress in solving the discrete log problem in prime extension fields suggests that BLS curves might be an even better choice (see here). In the aforementioned paper you can also find estimations on the impact of the recent improvements on the key length. For BN pairings these estimations suggest that it is required to increase the bit length of $p$ to 461 bit for 128 bit security. There is also an alternative estimation which suggests that it is sufficient to use $p$ of length 383 bits for 128 bit security. The conservative choice would thus be 461 bit.

I would probably also use another library - as far as I know JPBC is not the best choice regarding performance. There are various Java implementations for BN pairings available. One option would be to rely on the bnpairings library. Another option would be to go for the ECCelerate library, which is free for educational and research purposes, and also provides a very recent and highly optimised implementation of BN pairings. Since you mentioned that you implemented BLS signatures: it might also be interesting for you that ECCelerate already offers means to hash to the groups as required by BLS signatures. I don't know whether this is implemented in the BNpairings library.


Who defined semantic security? In my opinion the most important development in cryptography in the last 30 years is the precise definition of semantic security of a cipher. This definition captures the intuitive ideas of Martin Hellman, Ralph Merkle, and Whitfield Diffie of the mid-1970's tying cryptography to complexity theory that gave rise to the new cryptography with all its beautiful applications, multiple use of a key for file encryption, digital signatures, digital payment systems, one-way functions, one-way trapdoor functions, collision-resistant hashing, message digest codes, and so on.

My question is who came up with the precise definition of semantic security? Can you provide the reference to the paper that first defined semantic security precisely?

The source is the paper by Goldwasser and Micali on probabilistic encryption. The definition is of primary importance even though it is rarely used to prove security of encryption. The reason for this is that indistinguishability is much easier to use. However, indistinguishability is not a good intuitive definition in the sense that it is not immediately clear that it means that nothing can be learned about a plaintext from the ciphertext (beyond the length and any existing a priori knowledge). Since this latter notion is what we want to formalize, and this is exactly what is formalized in the definition of semantic security, this is the definition of encryption. Of course, by its equivalence to indistinguishability we can happily use the simpler definition, with the knowledge that nothing is revealed beyond what is already known (and the length).


RSA algorithm implementation $$m^{ed} \equiv m \bmod n$$
$n =pq$, so by Chinese Remainder Theorem it is equivalent to
$$m^{ed} \equiv m \bmod , m^{ed} \equiv m \bmod q$$
where $n=p\cdot q$
So how did 2 come from 1 by the Chinese remainder theorem?
I know Chinese algorithm but How did $m^{ed} \equiv m \bmod p$ and $q$ come?

Observe that for any $n$, $l$, as long as $l | n$, any equivalence $a \equiv b \pmod n$ also holds mod $l$: $a \equiv b \pmod l$ .
To fully see this, we can write
$$
\begin{align*}
    a &\equiv b \pmod n \\
    \Leftrightarrow \\
    a &= b + kn
    \\&=b + ktl \quad(\text{since } l|n\text{, so } n = tl)\\
    \Rightarrow\\
    a &\equiv b \pmod l
\end{align*}
$$
So you could solve $m^e \pmod p \equiv a$ and $m^e \pmod q \equiv b$, then use CRT to get $m \pmod n$.


Does public-key + hashing create a security vulnerability? The title says it all really...let's say I have a packet of data that one of my applications needs to store encrypted with a public key (RSA, say, with the private key kept elsewhere). Let's say the application also then needs a way of determining if said packet has already been stored, so I combine it with a randomly generated salt and save the hash of packet+salt so I can check it later (e.g. MD5). Does storing the combination of these three pieces of data...i.e. encrypted packet, the salt and the hash....result in data that is significantly less secure than the encrypted packet alone?

I realize "significantly less secure" is an arbitrary metric. I'm not after anything military grade (for want of a better nonsensical term), I just want to make sure I'm not doing anything overtly silly.

The hashing does not compromise security in any way. Assuming you're calculating hash(ciphertext+salt), the hash provides no new information that an attacker with access to your ciphertexts doesn't already have.

A secure hash like SHA-3 is a one-way function, safe even on a salted plaintext, and the outputs of such are stored in authenticated encryption. You can actually strengthen your system by using a HMAC rather than just a hash and incorporating an authentication mechanism.

As for whether the whole system is secure, it depends on what you're storing.

Checking if the packet has been stored is likely to create an oracle for a side channel attack. If the attacker can send packets to encrypt and your response or its timing is in any way different for duplicates, they can verify if a certain file of interest or a certain password is being stored in your system.

Whether it's effective depends on the search space for the plaintext. If it's small, e.g. passwords, or files people don't want to be known to possess, that's a vulnerability. Deduplication is generally at odds with security, and creating secure deduplication is a current challenge.

N.B. I've addressed only security, not utility above. Keep in mind that you can only compare hashes with the same salt, so this scheme may have limited effectiveness for deduplication.


How do we reduce the multiplications in the AES mix column layer using $x^4 +1$ I recently learned AES uses $x^4 +1$ to reduce the multiplications in the MixCol layer. However, I used $p(x) = x^8 + x^4 + x^3 + x + 1$ not knowing it was the wrong polynomial and got the correct answer. For example, here is what I did:

\begin{equation*}
\begin{pmatrix}
02 & 03 & 01 & 01 \\
01 & 02 & 03 & 01 \\
01 & 01 & 02 & 03 \\
03 & 01 & 01 & 02
\end{pmatrix}\
\begin{pmatrix}
D4 \\
BF \\
5D \\
30
\end{pmatrix}
\end{equation*}

If, for example,  we consider the last equation $$03 \cdot D4 \oplus 01 \cdot BF \oplus 01 \cdot 5D \oplus 02 \cdot 30 $$
and write it in terms of $x$
we get (after cancelling):
$$x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x$$
Reducing this using $p(x) = x^8 + x^4 + x^3 + x + 1$ I get: $$x^7 + x^6 + x^5 + x^2 + 1 = E5$$.

As far as I know this is the correct answer but I did not use $x^4 +1$ at any point. And when I try to reduce $x^8 + x^7 + x^6 + x^5 + x^4 + x^3 + x^2 + x$ using $x^4 + 1$ I get the wrong answer.

At what point do I use $x^4 + 1$ to reduce the polynomial?
Was my answer just lucky or can we use $p(x) = x^8 + x^4 + x^3 + x + 1$ as I did as an alternative?

The $x^4+1$ is implicit in the matrix.

What you are doing is that you consider formal sums $z_0 + z_1 \alpha + z_2 \alpha^2 + z_3 \alpha^3$ for $z_i$ elements of the field $\mathbb{F}_{256}$, and a formal value $\alpha$ which is not in $\mathbb{F}_{256}$, but is such that $\alpha^4+1 = 0$. You can add and multiply such elements, always keeping the result in the same set by applying the rule that $\alpha^4 + 1 = 0$. If you set:
\begin{eqnarray}
y &=& y_0 + y_1\alpha + y_2\alpha^2 + y_3\alpha^3 \\
z &=& z_0 + z_1\alpha + z_2\alpha^2 + z_3\alpha^3 \\
\end{eqnarray}
then you have:
\begin{eqnarray}
yz &=& (y_0 z_0 + y_1 z_3 + y_2 z_2 + y_3 z_1) \\
&+& (y_0 z_1 + y_1 z_0 + y_2 z_3 + y_3 z_2) \alpha \\
&+& (y_0 z_2 + y_1 z_1 + y_2 z_0 + y_3 z_3) \alpha^2 \\
&+& (y_0 z_3 + y_1 z_2 + y_2 z_1 + y_3 z_0) \alpha^3 \\
\end{eqnarray}

This equation can be expressed as a matrix multiplication. The example in your question really is the multiplication of $z = D4+BF\alpha+5D\alpha^2+30\alpha^3$ by $y = 02+01\alpha+01\alpha^2+03\alpha^3$. By writing it as a multiplication by that specific matrix, you "hide" the polynomial $\alpha^4+1 = 0$ into the matrix (specifically, the matrix columns are $y$, $y\alpha$, $y\alpha^2$ and $y\alpha^3$).

Note: The set of formal sums $z_0 + z_1 \alpha + z_2 \alpha^2 + z_3 \alpha^3$ is actually the ring $\mathbb{F}_{256}[x]/(x^4+1)$, i.e. the ring of polynomials with coefficients in $\mathbb{F}_{256}$ and taken modulo the polynomial $x^4+1$. It shall be noted that this ring is not a field, because $x^4+1$ is not irreducible over $\mathbb{F}_{256}$; indeed, in that field, $x^4+1 = (x+1)^4$ (it's a binary field, addition is XOR, thus $2=0$). The ring not being a field does not prevent the operation from being computed, but it means that there are couple of values $(y,z)$ such that $y\neq 0$, $z\neq 0$, but $yz = 0$. However, the $y$ value used in AES ($02+01\alpha+01\alpha^2+03\alpha^3$) is invertible in that ring, which is a blessing because it means that multiplication by $y$ is a bijection; otherwise, decryption would not always be possible.


Convert a number to sha-1 I have a task to find a the message for which the SHA-1 hash's last 11 symbols in hexadecimal presentation corresponds to an 11-digit number.

I have been given the following example solution:

  For the code 38607310235, a solution is a513b8c4507ea2891fb34cd4612e038607301235, which is the hash of $y$

How can I find $y$?

There is no why it is identical. The input form of the data does not influence what the output of a secure hash function should look like. The input of a hash should be unrelated to the output except for the mapping performed in the hash function itself. There should be no method of calculating the output other than to execute the hash function.

The best way to find another hash with the same property is to brute force it; go through a lot of numbers, convert them to bytes, calculate the hash and compare against the hexadecimal representation of the output. As each hexadecimal digit represents 4 bits, you would have to perform $2^{44}$ calculations (as I don't see how the birthday paradox would help you here). Note that, as CodesInChaos mentioned in a comment, that rainbow tables could speed up searches for cases where the input has properties that are reflected in the output.

If you get the wrong hash output, then it is likely that your conversion from the given number to bytes is failing. You may want to try another encoding.


Are there any methods for constructing a password that can be reconstructed if forgotten and is as secure as randomly generated ones? Is there a formal name for such a thing, so I know what to google? Is it possible to make them as secure as randomly generated passwords?
An illustrative example would be something like picking a random book and then picking the words inside it using some process that can be recreated to generate a passphrase.

What you're asking for is if we can describe for you a process that would allow you to generate a password such that you can later guess it without knowledge of its outcome. But the problem is you have to explain what would stop an attacker from carrying out the same recovery process to guess your password:

If the recovery process used only public information, the attacker would just be able to do it themselves;
So it has to use some secret information, but if that secret is as strong as a random password then that doesn't gain you anything;
And if the recovery secret is weak then the password it reconstructs cannot be strong, because guessing the recovery secret is sufficient to reconstruct the supposedly "strong" password.

The simplest practical solution I can think of to forgetting a strong password is fundamentally low-tech: write the random password down and store in in a location that physically secure and/or guarded by parties you trust. This is not at all a fanciful or hypothetical recommendation; for example, 1Password (who I'm in no way affiliated with) provide a printable PDF "Emergency Kit" for users who wish to write down their master password and put it for example in a bank safe deposit box.
I can think of a more complicated elaboration of this: using secret sharing to split the secret into multiple "shares" so that a minimum number of them need to be brought together, and distributing them to different parties and/or locations and so on. But in this case you'd still be relying on a mix of physical security and trust; it's just a more elaborate version of writing down the password.


Use sha3 for passwords hashing Is use of sha3 justifiable? Is sha3 better than sha2 in (m)any aspects?

P.S. I want to use hashing for passwords in a database

Is sha3 better than sha2 in (m)any aspects?

SHA3 is built on-top of a fundamentally different construction than SHA-2 which has many nice properties. So yes, in many hash-function relevant aspects it is indeed better. As for password-hashing, SHA-3 implementations (without hardware acceleration) also tend to be slower, which is good in this case.

However.

  Is use of sha3 justifiable?

NO. Do not use a fast hashing function for password hashing. Use a dedicated password hashing scheme (PHS) such as Argon2 or bcrypt. These have been heavily reviewed, analyzed and even been built around the idea of being used for password hashing. They do their job really well and give you and your users the best possible security to the standards threats that you have to deal with when handling passwords on standard modern CPUs with fast RAM access.


Security of semantically secure ciphers when the attacker knows the relation between plaintexts This question is about the security of public-key ciphers when related plaintexts are encrypted by the same encryption key. Take Paillier for example. I know that Paillier is semantically secure under the DCRA. Now a sequence of related plaintexts are encrypted by Paillier with the same encryption key, but for each of the plaintexts, a fresh randomness is used in the encryption. The attacker does not know the values of the plaintexts, but he knows the relation between them. The attacker eavesdrops the ciphertexts of the sequence of plaintexts. An extreme case is that the sequence of plaintexts is the same one, in which case the attacker obtains multiple ciphertexts of a single plaintext and he knows this. Will security be reduced in this case where the attacker knows the relation between the plaintexts?

Look at the definition of semantic security. It is for this exact reason that auxiliary information is modeled in the definition. This ensures that nothing is revealed even when the attacker knows partial information.


Diffie-Hellman when $p$ and $g$ are pre-agreed and hidden from Eve During a regular Diffie–Hellman public key exchange, Alice and Bob agree to use a prime number $p$ and a base $g$… which are both made public and are therefore also assumed to be known by Eve. Alice chooses a secret integer $a$ and sends $(A = g^a \mod p)$ to Bob, Bob chooses a secret integer $b$ and sends $(B = g^b \mod p)$ to Alice, etc.

One of the main pitfalls with a Diffie–Hellman public key exchange is, that Eve could try to use $p$ and $g$ for cryptanalysis, potentially learning the DH secret. Eve would have to solve the Diffie–Hellman problem to obtain $g^{ab}$. This makes things hard for Eve, but given enough computing power, it is not impossible.

Now, if Alice and Bob would agree upon $p$ and $g$ in advance (for example, during a face-to-face meeting in a SCIF), they would not have to agree upon $p$ and $g$ in public. As a result, Eve would have no option to learn the values of $p$ or $g$.

Under this condition:

Would it still be possible for Eve to work out the shared secret key that Alice and Bob calculate? After all, Eve would only be able to intercept Alice’s $A$ and Bob’s $B$. Would it be feasible for Eve to learn anything (useful) at all, or would the missing $p$ and $g$ make it impossible for Eve to calculate the secret (even when assuming she had solved the DH problem)?
What would be the impact on security, if Alice and Bob would “reuse” those $p$ and $g$ values for more than a single public key exchange? Would that give Eve any advantage in this scenario?

For the moment assume $g$ is a secret (uniformly random) generator, but that $p$ may be known to the adversary. Then given only $g^a, g^b$, the Diffie-Hellman key $g^{ab}$ is information-theoretically uniform (up to small statistical error), i.e., it cannot even be found by brute force because the adversary does not have enough information to determine it. This is because every generator $h=g^c$ for all $c$ (coprime to the group order) is equally likely to be the "real" one, so the "real" key is equally likely to be $g^{ab/c^2}$. Such values essentially cover all group elements (up to rare degeneracies). So essentially, Alice and Bob have a true one-time pad value.

However, this is not really interesting, because Alice and Bob were able to set up a secret generator $g$ in the first place, which is just as good as (or better than) a one-time pad value.

If Alice and Bob use the same $g$ for two or more runs of the protocol, then there is only one "degree of freedom" in the derived keys. That is, knowing one key (and the public messages) information-theoretically determines all the others. So any hope that the keys would look uniform and independent would have to depend on a computational assumption.

This all assumed that $p$ was known. It's much harder to analyze what happens when $p$ is unknown, because revealing group elements reveals some information about $p$, but it's hard to say what.