Encrypted Data length in a CBC Block Cipher The RFC5246 states the following:

The encrypted data length (TLSCiphertext.length) is one more than the
sum of SecurityParameters.block_length, TLSCompressed.length,
SecurityParameters.mac_length, and padding_length.
Example: If the block length is 8 bytes, the content length
(TLSCompressed.length) is 61 bytes, and the MAC length is 20 bytes,
then the length before padding is 82 bytes

What is the extra byte and what should it be?
Also, the maths doesn't quite seem to add up. The first section says the length is the sum of the block length, the contenct length, the MAC length and the padding length. So why in the example is the 8 byte block length ignored in the calculation?

What is the extra byte and what should it be?

That is due to the way padding is specified. The last byte is the padding length, from 0 to 255. That is the length of the padding without the length byte itself. So with "zero padding" there's still the padding length byte.

  The first section says the length is the sum of the block length, the contenct length, the MAC length and the padding length. So why in the example is the 8 byte block length ignored in the calculation?

The quote continues "this does not include the IV". That is because unlike the rest of the data, the IV is not encrypted.


AMD's implementation of RDRAND instruction The latest AMD programmer manuals, dated June 2015, include the RDRAND instruction in the instruction set. For completeness, it lacks RDSEED. Confer, AMD64 Architecture Programmer’s Manual Volume 3: General-Purpose and System Instructions, page 278.

The description includes the text:

  Loads the destination register with a hardware-generated random value.

I'm having trouble finding information on AMD's circuit and other design/implementation details. I'm not getting specific hits when searching AMD's site, and a general web search is returning a lot of noise dominated by Intel (not Intel's fault, its just the way it is).

What is known about AMD's circuit?

Based on @Richie comments (it was a good lead): according to NIST's Validated FIPS 140-1 and FIPS 140-2 Cryptographic Modules, AMD does not have an approved module. Additionally, according to NIST's Modules In Process, AMD does not have something in evaluation.

These circuits use an asynchronous counter that is ringing, and are sometimes combined with a seed from the unique processor ID (you blow these with e-fuses during test)

If you take 32 ring oscillators in parallel that each supply a single bit, you will see a random 32-bit value every time you sample.  The randomness introduced is due the Poisson process of charge arriving at different times across the channel of the device, and this is why ring oscillators are "noisy".  This is why do not need a seed, you just need a few moments that taken when the CPU resets to achieve electrical chaos.  I would probably even keep a few ground ties weak to substrate through the resistors to increase the charge distribution.

I also have seen an implementation of this were the a few inputs were then put into SHA-1 that was XOR'd with the processor ID, but just from the standpoint of physics, you could have just have the ring oscillators.  I assume this approach was used because it's outlined in a NIST spec.

addendum:

The most approachable discussion of this noise is probably this paper:

R. Sarpeshkar, T. Delbruck, and C. A. Mead, “White noise in MOS transistors and resistors,” IEEE Circuits and Devices Magazine, vol. 9, no. 6, pp. 23–29, 1993.


How does the user get the private/public key with HMAC based request signing? I need to implement a HMAC signing of requests and I have read this article which explains the basics of what it is and how to achieve on theory.
https://blog.andrewhoang.me/how-api-request-signing-works-and-how-to-implement-it-in-nodejs-2/
But I have no idea how the user initially gets their public/private key pair. Is it during login or during registration? Do they change? If yes how do you send them the new private key?

Each site, users and the server, generate their public and private keys and announce them, by sending the public keys. This can be executed during the registration process. The server should not generate the keys for the users, otherwise, the servers must be totally trusted and you have to securely send the private key, somehow.

You can use the  Diffie-Hellman Key exchange protocol or the Elliptic-curve Diffie–Hellman to generate the keys to use in HMAC or any other process.

Due to the man in the middle attack, you may need  to apply the improved version; Station-to-Station protocol


How does CTR-ESSIV work? I'm using Wikipedia and Handbook of Applied Cryptography as references. I know that ESSIV generates an initialization vector (IV) by combining a hashed key with the sector number.

However, I only see an IV in CBC, PCBC, CFB, and OFB modes of operation e.g. chained modes. CTR and ECB are not chained modes, so where does the IV go?

Comparing two files encrypted with CTR-ESSIV versus ctr-plain with a plain unsalted key, the entire stream is different, not just the first block. This means the IV is applied to all blocks in CTR mode. However, when doing the same with ECB mode, the two files are identical. This means the IV is not used in ECB mode at all.

So, where and how exactly is the IV applied in CTR mode?

For key $k_0$, nonce $n$ (‘initialization vector’), and message $m = m_0 \mathbin\| m_1 \mathbin\| \cdots \mathbin\| m_{\ell - 1}$, the AES-CTR ciphertext is $c = c_0 \mathbin\| c_1 \mathbin\| \cdots \mathbin\| c_{\ell - 1}$ where $$c_i = m_i \oplus \operatorname{AES}_{k_0}(n \mathbin\| i),$$ where $n \mathbin\| i$ is some unique encoding of $n$ and $i$ as a 128-bit block.  ESSIV means we derive $$n = H_{k_1}(\mathit{sector\ number})$$ to encrypt each disk sector.  We usually call $n$ a nonce instead of an IV because the only rule is that it must never be repeated with the same key; the consequences of nonce reuse are catastrophic.

This means that ‘CTR-ESSIV’ not terribly useful for disk encryption unless you never rewrite a disk sector: the standard threat model for disk encryption is disclosure of multiple versions of a disk, which would be the case if the border police confiscate your laptop whose SSD had queued up old versions of many disk sectors for deferred erasure.  In this threat model, CBC-ESSIV leaks only how long a prefix of each sector changed between the two versions; in contrast, CTR-ESSIV may allow arbitrary decryption of disk sectors depending on what the adversary knows about the different versions.


Security of the shared secret key for a smart meter (Linky) Reading the specs of a new electricity smart meter (called Linky in France), I was surprised about the chosen encryption method (128 bits symmetric key AES), based on a single secret key (called CCC in the specs), that is shared between the meter and the central system, used to generate session keys to encrypt data.

Some context from the documentation:

  5. PLC COMMUNICATION SECURITY - Each meter must have a CCC secret key, a unique CC_LAN  key, a unique  CC_LOCALE key and two session keys for the LAN interface and a session key for the Local interface, transmitted when the application association with the Client concerned was created

  5.1 Encryption method - 128-bit AES symmetrical key algorithm, GCM operation mode. It is used to ensure data confidentiality and authentication.

  5.2 "CCC" secret key - The CCC key is used to reprogram the "CC_LAN" key or the "CC_LOCALE" key in a meter. This key is never used to encrypt the communications between the concentrator and the meter. It is known only
  to the meter and the IS (Central server). When the CC_LAN (and the CC_LOCALE respectively) is generated, the IS encrypts it with the CCC and transfers it to the meter via the concentrator. This transfer is completely transparent for the concentrator which sends the encrypted data to the meter. The meter that knows the CCC is responsible for decryption the data in order to retrieve the CC_LAN (and the CC_LOCALE respectively).
  The CCC key is not accessible in read mode.

  5.3 Unique "CC_LAN" and "CC_LOCALE" keys - The CC_LAN and CC_LOCALE keys are only used during the application association phase between the  concentrator and the meter, and the TSP and the meter respectively. They are used to crypt the service allowing this application association. This service transfers the session key that will then be used, in the context defined by t
  his application association, to crypt the communications between the concentrator/TSP and the meter.
  The CC_LAN and CC_LOCALE keys cannot be accessed in read mode.

A quick note on the architecture: the meter communicates with the local transformer using PLC on open power lines, the transformer communicates with the central system with GPRS. The local transformer, apart from local network management, only forward data packets "as-is" to the central system.

(More information on the architecture is available here. Security is chapter 5, pages 39-40).

What is the security implication of having a central repository of secret keys?
If the central key database is hacked, would the attacker be able to decrypt the communication of any meter? (For example, to tamper with it?)
Is there any reason why not to choose an asymmetric public key mechanism instead, where the central system does not have to know the secret key of all meters? Does this has to do with the complexity of securely communicating the public key once generated? (since the central system has to ensure the authenticity of the public key maybe a manual intervention would be needed?)
Is there any potential security risks of the chosen architecture?

Note: This question has been also asked on security.stackexchange.com.

In addition to the other answer

Using asymmetric cryptography in the meters would have some benefits:

it can make passive eavesdropping of meter/server communication useless, even to a party holding or able to use the server's private key; something not achieved with secret-key cryptography.
it can ensure that any central key leak can not compromise the capability to authenticate messages from the meters.

But that's about all I see. In particular, even a full blown asymmetric public key mechanism can not solve the most serious problem that if the central system is hacked, and the hacker can communicate with the meters as the central system does, then all the capabilities the central system has (including reading any meter, or/and making any parametrization of the meters) are available to the hacker. A complete hacking of the central system is thus a disaster, no matter what.

That's why such central systems should be designed with multiple layers of security. In particular, they should hold secret keys, and the server's private key if some asymmetric cryptography is used, within devices intended to never leak such secrets, like HSMs or Smart Cards. That way, penetration of the outer layer (e.g. server's OS) simply can't leak secret or private keys (only, at worst, allow their use). After an attack, restoring the integrity of the server can hopefully restore security and functionality (unless the hacker managed to change the highest-level individual meter keys).


Key Derivation Functions vs. Password Hashing Schemes Key derivation functions, such as HKDF (standardized in RFC 5869), are meant to stretch some initial keying material having enough entropy, like a Diffie-Hellman shared value, into one or more strong cryptographic secret keys.

Password-hashing schemes, such as the PHC winner Argon2, are meant to hash usually low-entropy passwords with the goal of making the hash digest inversion as costly as possible for an adversary with respect to CPU and memory consumption, as well as parallelization.

Is it exact to consider that password-hashing schemes are actually key derivation functions specialized for low-entropy inputs? Or is there any other essential difference of theoretical nature between these two types of cryptographic schemes?

Key-stretching key derivation functions must produce results that have certain randomness properties, and be very difficult to reverse. Password hashes only need to satisfy the property "difficult to reverse", without randomness requirements. This is why all key-stretching key derivation functions work as password hashes but not the other way around.
Note that there are also key derivation functions that are non-stretching. Stretching functions are inherently slow, and this is necessary for password hashing. Fast key derivation functions such as HKDF are not suitable when the input has a low entropy, for example a password, regardless of whether the goal is to derive key material or a password hash.


RSA PCKS1 v2.1 RSAES-OAEP algorithm Using RSA public key (n,e) the encryption of a message is

c= (m^e) mod n

and the corresponding message is decrypted as

m = (c^d) mod n

How does the RSAES-OAEP algorithm specified in PKSC#1 v2.1 differ from the above basic method?

Is it possible to decrypt a text encrypted using RSA PCKS1 v2.1 RSAES-OAEP algorithm with Raw rsa decryption method (ie, m = (c^d) mod n ) ?

Directly applying the RSA-function to a message is not secure in real life. The function leaks all kinds of information about the underlying plaintext and is particularly vulnerable to active attacks (where the attacker might be able to learn something about some related message also encrypted under RSA, and use this to learn what the original message was). Unfortunately, some textbooks only present RSA as you have done above and leaves it at that, hence the term textbook-RSA is often used for this raw application of the RSA-function to the message.

However, the good news is that if your message was somehow chosen completely at  random within $\mathbb{Z}_n$ (the full plaintext space), then applying the RSA-function would actually be secure. Unfortunately, in real life, our messages are seldom   completely random, but rather chosen from a very tiny subset within $\mathbb{Z}_n$. The solution is to randomize the message using padding so that our messages takes up a much larger possible subset within the plaintext space. Additionally we make it so that equal messages encrypt to different ciphertexts each time which is important.
In real life we use RSA like this:

Encrypt: $m \mapsto$ randomize message using some padding scheme $\mapsto x$ $\mapsto c = x^e \pmod n$

Decrypt: $x = c^d \pmod n \mapsto$ check whether $x$ has the approptiate padding $\mapsto$ if yes: strip of the padding from $x$ and return $m$; if no: return Fail.

The question then becomes: how should we pad the message $m$? OAEP is one such padding scheme (there are actually many ways how this can be done, but not all of them are secure. RSA-OAEP fortunately is). So how does OAEP-work? You should check out the description on Wikipedia, but this picture goes a long way of explaining it:

$\hskip 2 in$

After the message you pad with some zero's then append a completely random string $r$. Then feed these through a couple of hash functions $G$ and $H$ and some XOR-applications and output the padded message $x \| y$. Then you encrypt this padded output. When you decrypt you basically reverse the whole process and verify that you have the right number of zeroes at the end (before the $r$).


Encryption and decryption of Request and response for REST API I am working on encryption/decryption for the rest of the API.
The client here can be mobile, desktop, web browsers, etc and all the requests will be made to an https endpoint.
The main goal here is that the encryption/decryption has to be performed in client-side applications. The user himself should not be able to monitor the request/response made from his device(phone, browser, etc) and be able to perform encryption/decryption by himself. He should not be able to see the request/response in cleartext. Everything should happen in the client-side application.
For every request it should follow the steps as follows :

Client application encrypts the request data and makes an API call
Server decrypts the data and performs operations
Before sending the response back to the client application, the server encrypts the response and sends it
Client application decrypts the response and uses it

I had planned to use AES-256 but faced the following problems :

Secret key has to be stored hardcoded in the client-side applications. Doing so won't be safe
Getting the secret key every time from a rest API is not safe either as the request can be monitored and the key can be fetched from the response

I had planned to use AWS KMS service but faced the following problems :

For every encryption/decryption to be performed the client side has to login to AWS and then use the KMS service
If the login request is made then the request can be monitored again and the access key and secret key can be fetched from the response/request and then once the login access is gained, anyone can use the KMS service to encrypt/decrypt data

I did check articles where the secret key should be separate for each user and should be based on password but in my case User can log into to client-side application as a guest user so there won't be any password, email that has to be provided.
Not very sure how separate keys can be used for each user as the encryption/decryption has to be performed every time on both the client and server-side.
AES-256 is considered to be safe but I still didn't find any ways on how can a private key be managed on the client-side.
Any help here on how can AES, KMS be used? Any other solutions would be fine too.

In case you want to use AWS KMS without the raised issues, you can use AnonyFlow API for encryption/decryption. it is using the AWS KMS in the background and manage the private keys for you in order to avoid the keys issues you have raised, therefore you enjoy the service without worries.
It's very easy to consume the api, you can use the anony-value for encrypting one or more string values (string array) or use the anony-packet for encrypting json data - you can even define specific keys in order not to encrypt the entire json.
the best practice would be to consume it in your server side code. you can even create a serverless service on aws or any other platform to handle it.
Disclosure: I'm part of AnonyFlow creators.


Is SHA256 good enough to shrink a key? I have a key that is the combination of two shorter keys generated by PBKDF2, which together are long more or less 64 bytes. Now I need to shrink it down to 32 bytes and I'm not sure what to use to do it. I was thinking of SHA256. I know that SHA256 is not safe to generate keys by itself, but since what I have is a combination of two proper generated keys, then SHA256 would be just fine. Am I right or I should use something else to accomplish this goal?

I agree with the comments that SHA-256 should be fine here.

However, if you already use HMAC-SHA-256 for PBKDF2, you could use HKDF Expand, which despite its name is defined even for output lengths shorter than input. In your case the output would be simply:

$$\operatorname{HMAC-SHA-256}(\text{key}, \text{info} || \text{0x01}),$$

where 'info' is an optional, arbitrary string to specify this particular key in case you ever need to derive another key from the same material and '0x01' is the byte with value 1.


Should text be hashed before being used as an encryption key? Let's say I have an API that provides an encryption wrapper around another API. I give the consuming programmer the option of either passing a string or byte array as an encryption key.

The byte array must be the correct size, and is used directly as the encryption key.

However, if they pass a string, I hash it using SHA256/SHA192/SHA128 before passing it to the encryption function.

Is it correct to hash text of arbitrary length before using it as a key?

Or should it be accepted as is, even if it means the encryption key will either have a large amount of \0 bytes if it is too short, or be truncated if it too long?

The underlying cipher is AES/Rijndael

Considering that someone will probably end up supplying a password for that argument at some point, it would be better to use a proper slow key derivation function like pbkdf2/scrypt/argon2.

Even if they don't end up sticking a password in there, meaningful/arbitrary text and passwords should be treated the same in regards to an adversary's ability to guess the string. If the string is not actually a random value - meaning it's not the output of /dev/urandom - then it will not have 8 bits/byte of entropy, parts of it are guessable, and it should not be used directly as a key. Hashing an easily guessed value with SHA256 does not make the result unguessable - all it will do is make the output more appropriately sized.

Note

With that being said, if the option is available, you should prefer to use pre-existing crypto libraries such as libsodium. They have already handled all of these sorts of details (as well as all sorts of obscure pitfalls, side channels, and other black magic) and produced a succinct interface that more or less removes all of these sorts of questions for the developer.


Why do we use one transformation to hide the structure in UOV? Why do we use just one affine transformation in Oil and Vinegar (UOV) scheme to hide the structure of the map? Doesn't it cause any security problems, and isn't it better to use two transformations?

The public key in Oil-Vinegar was proposed as $F\circ L$, where $L:\Bbb F^n \to \Bbb F^n$ ($n = o + v$) is an invertible linear transformation and $F:\Bbb F^n \to \Bbb F^o$ is an Oil-Vinegar map.

I think you are suggesting that another transformation $T:\Bbb F^o \to \Bbb F^o$ is used at the end of the composition so that the public key becomes $P = T\circ F \circ L$. This is natural (and necessary!) in other similar schemes like Hidden Field Equations (HFE). However, this is not necessary in Oil-Vinegar since $F$ is uniformly random among all Oil-Vinegar maps and the composition of an Oil-Vinegar map with a linear transformation (on the left) yields another Oil-Vinegar map.

To be more precise, if you let your public key be $P = T\circ F \circ L$, then by definining $F' = T\circ F$ your scheme will have the shape $F'\circ L$ where $F'$ is an Oil-Vinegar map, so we can assume without loss of generality (or, without losing security strength) that the transformation $T$ does not exist.


Are all block ciphers FPE (format preserving encryption)? A FPE preserves the format. There is a correspondence between the format of the ciphertext and the plaintext.

Given that a message in some binary enconded format can easily be divded in some l blocks of n bits which will be encrypted to l blocks of n bits I would call (some necessary padding issues ignored) pretty much a format preserving encryption).

Is this true? Are block ciphers considered to be FPE?

Or are the ciphers working on blocks which have a disparity of the input->output ratio of either block numbers and block size?

The formal definition of a block cipher is a function
$$
E_K(P) := E(K, P): \{0,1\}^k \times \{0,1\}^n \rightarrow \{0,1\}^n
$$

The input and output spaces are by definition n-bit blocks, so the operation of the cipher in Electronic Code Book (ECB) mode is technically "format preserving".

That is not however what "Format Preserving Encryption" (FPE) generally refers to, nor does it mean that all block ciphers modes of operation are format preserving, nor that all symmetric encryption functions are format preserving.

NIST SP800-38G, which recommends FPE modes of operation for block ciphers, defines FPE as "Given any finite set of symbols, like the decimal numerals, FPE transforms data that is formatted as a sequence of the symbols in such a way that the encrypted form of the data has the same format and length as the original data."  In other words FPE is a function

$$
E_K(P) := E(K, P): K \times M \rightarrow M
$$

where M is not necessarily a block of bits.  For example M could be a 16-digit credit card number, or a Social Security Number.  The ciphertext - rather than being a block of bits - will have the same size and alphabet as the input; that is it will look like a credit card number or SSN.

A typical use of FPE is to selectively add data encryption to fields within legacy messages without modifying the message format or the validation functions of your legacy systems.

Many block cipher modes of operation cause ciphertext expansion - where the ciphertext is larger that the plaintext - are are not format preserving. Any mode that includes a checksum or requires a message-unique Initialisation Vector (IV) will cause ciphertext expansion.


Importance of block size in CBC mode Why is it necessary to use a sufficiently long block size when implementing a CBC block cipher with a truly random initialization vector? In ECB mode it's easy to get information about the message if you can encrypt arbitrary plaintexts and look for matching blocks, but I'm not sure how this applies to CBC mode.

CBC mode encryption is defined as:

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

(with $P_i$ being the $i$th plaintext block, and $C_{i-1}, C_i$ being the ciphertext blocks.

What might happen if we have a lot of ciphertext encrypted with the same key is if two ciphertexts happen to be the same, that is:

$C_i = C_j$

If we see that, we can then immediately deduce that:

$E_k(P_i \oplus C_{i-1}) = E_k(P_j \oplus C_{j-1})$

or

$P_i \oplus P_j = C_{i-1} \oplus C_{j-1}$

Now, the attacker knows the values of $C_{i-1}, C_{j-1}$, and hence the attacker can then deduce the relationship between those two plaintext blocks.  If he happens to know one of the plaintext blocks, he can immediately deduce the other.

Is this information leakage fatal?  Well, maybe, maybe not, the attacker has no control over what data blocks are leaked, even with chosen plaintext (because he can't predict $C_{i-1}$ before the encryption process).  However it's more leakage than we want.

And, how likely is this?  Well, that's where we come to block size.  $C_{i-1}$ is effectively random and uncorrelated to $P_i$, and so $P_i \oplus C_{i-1}$ is also effectively random; if the block size is $n$ bits, this is a random value between $0$ and $2^{n}-1$; by the birthday paradox, we would expect a collision after about $2^{n/2}$ block encryptions.

That is the point in not using too small of a block size; if we were to take $n=32$ bits, we would expect a collision (and hence some leakage) after about $2^{16}$ blocks; since we generally want to encrypt more than that with a single key, that's not enough.  For $n=64$, we would expect a collision after about $2^{32}$ blocks; that's getting better, however by today's standards, that's not that much data (and there is a chance of leakage with less data).  For $n=128$, we probably won't get a leakage until we get close to $2^{64}$ blocks; we'll never encrypt that much with a single key.


Is it safe to reuse the password when using AES-CTR with scrypt? I want to encrypt several files with the scrypt encryption utility. Here is an overview of its file format, which gives an indication of what it does:

scrypt encrypted data format
----------------------------

offset  length
0   6   "scrypt"
6   1   scrypt data file version number (== 0)
7   1   log2(N) (must be between 1 and 63 inclusive)
8   4   r (big-endian integer; must satisfy r * p < 2^30)
12  4   p (big-endian integer; must satisfy r * p < 2^30)
16  32  salt
48  16  first 16 bytes of SHA256(bytes 0 .. 47)
64  32  HMAC-SHA256(bytes 0 .. 63)
96  X   data xor AES256-CTR key stream generated with nonce == 0
96+X    32  HMAC-SHA256(bytes 0 .. 96 + (X - 1))

AES256-CTR is computed with a 256-bit AES key key_enc, and HMAC-SHA256 is
computed with a 256-bit key key_hmac, where
  scrypt(password, salt, N, r, p, 64) == [key_enc][key_hmac]

Can I safely reuse the password for encrypting different files? I'm concerned that nonce is set to 0 and I know that reusing the key in the CTR mode is a big no-no. However, the key is generated by scrypt, which uses randomly generated salt. Is that enough to mitigate the problems with reusing the passphrase and having a fixed nonce?

CTR is insecure if you reuse a key/iv pair. Since the salt is random, a different encryption key will be derived every time you encrypt something. Therefore it is safe even if it always uses the zero IV. Of course, the password must be strong enough to resist brute force attacks.


Government root SSL certificate possible vulnerabilities I'm writing an article about new government law in Kazakhstan. The law was accepted in December, but now one of our providers announced information for small and medium business how to install government-provided root SSL certificate: https://www.beeline.kz/b2b/sme/ru/press_centers/10040

Yes, they really want to listen the whole traffic of all citizens.

I want to show in my article that this is really-really bad solution. And I need all information about possible vulnerabilities of it.

The certificate is valid for 4 years, data size, as I think, 1024 bytes.

Link to the cert: https://www.beeline.kz/uploads/document/file/11120/QAZNET.rar

First - please REALLY check the certificate, download it, open and have a look into details (4096 bit, 30y validity). I don't think your government wants to be insecure themselves (so other parties will act on behalf of it).

If the certificate is to be used as a root (or issuing) certificate for other nationally issued certificates, you need it to be trusted (otherwise all national sites won't be recognized as trusted). It cannot be used to decrypt your traffic (as man in the middle) itself.

The only question to be answered, how trustworthy is the "Qaznet" issuer. Nothing prevents them (except the law and they would loose all credibility) to issue e.g. a google server certificate which will be trusted to all having the root / intermediate certificate as trusted (see http://arstechnica.com/security/2013/01/turkish-government-agency-spoofed-google-certificate-accidentally/ ). It is all about the trust. If you trust the CA provider or not (Qaznet).


Are there any known security issues when doing the following chaining of BCrypt Hashes: 'bcryt(bcrypt(user-pw, work-factor1), work-factor2)' I am currently developing a protocol which would be able to "upgrade" the strength of a bcrypt password hashes without the knowledge of the user-password so a system may upgrade it without user interaction.

Bcrypt requires the password as input to calculate the hash, if you already have a hash, there is no way to "calculate some more rounds" to increase the work-factor (see here).

Example

So the idea is to just chain the bcrypt hash with a stronger work-factor und using the old bcrypt hash as input like:

bcryptHashOld = bcrypt(pw, 4);
bcryptStronger = bcrypt(bcryptHashOld, 10);

Which would be the theoretical strength of 2^4 = 16 and additionally 2^10= 1024 => 1040 iterations.

Is there any issue with this protocol, ie. hashing the hash WITHOUT the user password? Does the work-factor increase as I have shown in the example above?

Theoretical Problem Statement

As SEJPM added in the comment a better problem statement would be: "whether chaining two PRFs yields another PRF and whether this chain can be evaluated using less work than two successive PRF calls. In formulas: Whether $F_{k1}(F′_{k2}(m))$ is a PRF that requires evaluations of $F$ and $F′$ to be evaluated"

(Note: I'm not asking how to increase the work factor, but if this approach is cryptographically sound)

First there are a few technical hurdles to deal with. Nominally, bcrypt takes three inputs: the password itself, a work factor, and a salt. To hash or to verify a password, you need the salt. Usual bcrypt implementations generate the salt randomly when first processing a password, and encode the salt along with actual function output into an aggregate string. If you use the whole string from the first bcrypt as input to the second bcrypt, then the final output will not contain the first salt, and you will never be able to recompute that hash for password verification.

Also, bcrypt works over "passwords" that it uses as sequences of up to 72 bytes. However, since passwords are normally text, some (most) implementations will accept a character string. In the C language, a character string stops at the first character of value zero. If the first bcrypt output, in binary, happens to contain a byte of value zero at the start, then in fine you will get the bcrypt hash of an empty string, and the hashed password will match one in 256 input passwords, which is bad. This is the kind of mistake that destroys your security but has a high chance of not being detected in unit tests.

You could avoid the "byte zero" effect by encoding the bcrypt output into a character string, e.g. with Base64 or hexadecimal. This enlarges the output, and can bring you dangerously close to the input size limitations for the second bcrypt. Compounding the effect, some bcrypt implementations have lower limits (56, 55 and even 51 bytes maximum size have been spotted in the wild) and may silently truncate the input.

All of that being said, yes, you could expand a bcrypt instance by cascading a second one, assuming that you take care to manage salts externally (it's unclear whether using the same salt for both bcrypt would be safe, so you might have to manage a longer aggregate salt).

However, it's better to start with a password hashing function that already includes work factor increases as a design feature. In the password hashing competition, at least Makwa had that feature (Makwa is not "the" winner of PHC, but it got a "special recognition" and, like many other candidates, was not broken).


Avoiding replay attack on certified announcements Suppose two agents A and B share a common secret and A makes a regular unique 16-byte announcement to B every 10mins which B must verify authenticity.

I'm thinking of letting the first 8 bytes be the message and the last 8 bytes be the HMAC(key, msg). The message itself contains an increasing counter, which B uses to reject all future messages with a lower counter.

Given the uniqueness of each message and the strict monotonicity of the counter, should this scheme avoid replay attack?

Overall, is this a secure approach?

Thanks

[let] the last 8 bytes be the HMAC(key, msg)

64 bits is a pretty small tag size, and not considered "cryptographically strong".  I would suggest using the full HMAC output if possible, or see here for some discussion of reduced tag length.

  should this scheme avoid replay attack?

Assuming that the HMAC cannot be broken (which would imply that the key is kept secure and a sufficient tag size is used), this scheme looks fine against replay attacks.

(I suggest opening a new question with regard to your key derivation scheme)


How to go about encrypting a digital exam? I'm building a Digital Examination system and I'm having problems understanding some concepts in cryptography.

I want use to Asymetric Cryptography and my questions are

Do I encrypt the entire file?

When I do my encryption is it that I should make the entire file encrypted with the private key of the sender of the exam? (as it passes through different hands e.g. lecturer to exam department)

Or do I just generate some kind of code that the recepient would compare it to?
Is that what digital signing is?
Do I need a public and private key for every party the exam passes through?

(lecturer, student, exam dept etc)

Let's see if we can clear up some of the basic crypto concepts for you. (Though you should probably do a bunch more reading on your own, and maybe hire a crypto consultant if this system is more than just a course project. Sloppily done crypto can get an institution into big legal trouble.)

Public Key Encryption:

In public key encryption, you encrypt something with the recipient's public key, so that the recipient can decrypt it with their private key. Think of it like a mail slot in your front door: anybody can send you stuff by slipping it through the slot (ie encrypt with public key), but only the person who lives there can unlock the door and get it (ie decrypt with the private key). -- The idea of "encrypting with the private key of the sender" does not make any sense - you push it out the mail slot so anybody walking by your porch can look at it?

For your second question:

  2.Do I need a public and private key for every party the exam passes through? (lecturer, student, exam dept etc)

If you want all of those people to be able to read it, then yes, you will need to issue each of them keypairs and have a system like this:

Person A encrypts for person B --> Person B decrypts then re-encrypts for person C --> Person C decrypts then re-encrypts for person D --> etc

(Note that a scheme like this would be considered insecure in any other setting because any of those people could modify the exam before re-encrypting it, and there's no way to prove who changed it. So this likely isn't what you want either.)

System design:

In my opinion, the proper way to do this would be to assign every student a keypair - maybe attached to their user account? Or maybe every exam invigilator gets a keypair if that makes more sense. Then your central server encrypts N copies of the exam: one per student / invigilator. If there are intermediary people who need to see it (lecturer, dept, etc) then you make a copy encrypted for their keypair also. This way, once you encrypt a copy of the exam for Student X, then regardless of how many hands it passes through, only Student X will be able to open it. This is the type of usage that Public-Key encryption is designed for. (As a side note: this would work very well if each copy of the exam had a random number embedded in it so you know that Student X is handing in their copy of the exam, not their friend's copy.)

Edit:

Looking over your question again, the line

  Or do I just generate some kind of code that the recepient would compare it to? Is that what digital signing is?

doesn't fit with the rest of your question. Signatures are an anti-tamper system: they guarantee that this is the original document, and hasn't been modified, but does nothing to hide it (ie everybody can see the text).


What are the different uses of MAC and Digital Signature? I know both of them can be used for Integrity and Authentication.
In which practical cases is preferred a MAC? and a Digital Signature?

Thank you in advance

A MAC is a form of symmetric or secret key cryptography. It uses the same key for signing and verification. It's fast and produces a small signature. Almost all algorithms are post-quantum secure.

A digital signature is a form of asymmetric or public key cryptography. It uses the private key for signing and the public key for verification. It's slow and produces a slightly larger signature. The popular algorithms get broken by quantum-computers and the replacements all have significant downsides like large signatures.


Recover plaintext from truncated ciphertext using AES for FPE I am trying to implement an FPE for a 19-digit long number. I am trying to follow the lecture of Prof. Dan Boneh and here is how I understand it:

Get the nearest power of two greater than $10^{19} \rightarrow 2^{64}$,
Get the binary representation of the 19-digit number,
Split the 64-bit long binary representation into two 32-bit for Feistel network,
Perform 7 rounds of Feistel network with AES (PRF),

pad zeroes to left of 32-bit until 128 bits for AES,
truncate cipherText obtained to the 32 Least significant bits for Feistel XOR and next rounds,

Convert the output of the Feistel network to Decimal and check if it is in the range of $0 - 10^{19}$ (some values are between $10^{19}$ and $2^{64}$), if not perform Feistel on the cipher text until it is within the range.

I am trying to do pad-encrypt-truncate for step 4 but I was not able to recover the plaintext from the truncated ciphertext. I am doing these decrypt steps right now:

Pad zeroes to the left of the 32-bit ciphertext (truncated) until 128-bits,
Decrypt using AES,
Truncate to Least Significant 32 bits (this is different from the ciphertext).

In the decrypting steps use AES_encrypt itself instead of AES_decrypt, AES decrypt is never needed.

Remember while encrypting, AES_encrypt is only used as a Pseudo Random Function, we don't really need AES_decrypt method even in decrypting phase. This might seem little confusing at first but not needed. Please check the proof given for this answer


AES or One-time-pad for encrypting a single 128bit block? I just started my network security course and came across the below question. Could some one help me here.
User A wish to send a 128-bit secret message, S, to user B. As the preliminary step, both A and B agree to use a 128-bit secret key, K, selected uniformly at random. At the time of transmission, A considers two different ways to secure the secret message, S. The first way is to encrypt S using the key, K, as one-time pad and send S ⊕ K to B. Alternatively, the second method is to directly use AES algorithm to encrypt S. In this case, the secret message, S, needs to be encrypted as a single 128-bit block. Despite of using either one-time pad or AES, suppose that an adversary, C, knows some initial portion of the original secret message, S, and can see the entire encrypted message during transmission. The primary intention of the adversary, C, is to recover full secret message from the encrypted message by trying every possible key. In this situation, which method among the one-time pad and AES would be more secure?
Select one:

Both methods are equal. The adversary can decrypt the ciphertext in
both the methods
One-time pad
AES
Both methods are equal. The adversary cannot decrypt the ciphertext in both the methods

My understanding:
In case of one time pad, as the attacker already knows the initial portion of plaintext and complete cipher text, attacker can just XOR them to get the initial portion of key. Attacker has to use  brute force for the remaining key bits.
But in the case of AES, the attacker has to try 2^128 combinations to get the complete plain text.
So, AES is more secure than one-time-pad in this case.
In course content, answer is given as :

Both methods are equal. The adversary cannot decrypt the ciphertext in both the methods

So, AES is more secure than one-time-pad in this case.

No, the one-time pad is perfectly secure, so it cannot be less secure than AES.  What's tripping you up is you're not understanding a subtle detail of what perfect secrecy means. People often misunderstand it to mean "the attacker cannot learn what the plaintext is," but in reality it means this:

No matter how hard they analyze the ciphertext, it cannot help the attacker learn anything more about the plaintext other than what they can figure out through other means.

Take your argument here:

In case of one time pad, as the attacker already knows the initial portion of plaintext and complete cipher text, attacker can just XOR them to get the initial portion of key. Attacker has to use brute force for the remaining key bits.

Here the initial portion of plaintext is something that the attacker learned not by cryptanalysis, but through some other means.  So the question is whether analyzing the ciphertext can gain them additional knowledge about the plaintext.  And the perfect secrecy of one-time pads tells us that it cannot, because given just the ciphertext and initial portion of plaintext, every possible remaining portion of plaintext is equally likely.
Another way to put this is that given the initial portion of plaintext, analyzing the OTP ciphertext isn't any more effective than just looking at that initial portion of plaintext and guessing how it might continue. Like, if the initial portion says ATTACK AT D, you might guess the full plaintext is likelier to be ATTACK AT DAWN than ATTACK AT DUSK just because dawn attacks are more common than dusk attacks. But no matter how hard you analyze the ciphertext, it won't help to settle this any further.

In course content, answer is given as :

Both methods are equal. The adversary cannot decrypt the ciphertext in both the methods

I think this answer is wrong, depending how we interpret the question though.  A brute-force attack might learn something about the plaintext in the AES scenario; but "might" is a key word there, there's no guarantee.
The idea would be to do this. Given ciphertext $C$ and partial plaintext $P'$ of length $l$ (in bits), go over every possible AES key $K_i$, and:

Compute $P_i = \mathrm{AES}^{-1}_K(C)$ (the AES decryption of $C$ with key $K_i$);
If the first $l$ bits of $P_i$ matches $P'$, then add $P_i$ to the set $S$ of candidate plaintexts; otherwise, discard $P_i$.

Now, for the security of AES in this scenario to be the same as one-time-pad, the resulting set $S$ must be of size $2^{128-l}$—the set of candidate decryptions must be the same as the set of all possible 128-bit strings that start with $P'$.
But all it takes for this to fail is that there exist a single collision—a pair of keys $K_1$ and $K_2$ such that $\mathrm{AES}^{-1}_{K_1}(C) = \mathrm{AES}^{-1}_{K_2}(C)$ (i.e., that $C$ decrypts to the same plaintext for both keys). And such collisions are indeed possible. And if there are such collisions, then there will also be "missing" plaintexts in $S$, which the attacker therefore learns are impossible given $C$ and $P'$.
Ultimately the course's question is vague, because it has these problems:

"Can the attacker decrypt the ciphertext" is a simplistic goal. As I mention above, the sort of goal that cryptography normally contemplates is "can the attacker learn something about the plaintext by analyzing the ciphertext," which may fall short of a full decryption.
In the AES scenario the question poses, it's possible but not certain that the attacker could rule out some candidate plaintexts. But the question isn't formulated in a way where we know for sure whether to count that as "the attacker can" vs. "the attacker can't."

There's two key certainties here, though:

The one-time pad is perfectly secure but AES is not.
Network security textbooks often don't teach cryptography exactly right


Will the non-colluding servers communicate in IT-PIR schemes ? The current literature around Information Theoretic Private Information Retrieval (IT-PIR) schemes assume the existence of multiple copies of the database distributed across non-colluding servers. Much of the research seems to be around the servers not communicating with each other but only with the client.

Can the results be improved (or are there known results) ? when the the multiple servers communicate among themselves without breaking the security assumptions (say using multiparty computation) ?

When the servers may collude then if they are all corrupted it's exactly the same as 1-server PIR. Thus, in information-theoretic PIR, it is always assumed that only some subset of the servers are corrupted.

It is unclear to me what you would gain by running MPC between the servers. One possibility is to simulate a single-server PIR with many servers. But this would just cost more.


If hash functions append the length, why does length extension attack work? I have understood that it's trivial to reconstruct the internal state of a hasher for many hash functions, if one only knows the output hash. Then, one can append data after the original data and obtain a valid hash for the original data plus the appended data.

However, recently I became aware that hash functions including MD5, SHA1, etc. actually append the length.

If hash functions append the length, why doesn't that stop the length extension attacks? For a good hash function, if the attacker knows hash(message || length), there should be no way to obtain hash(message) to be able to calculate hash(message || appended_data) which would allow calculating hash(message || appended_data || total_length).

Related: Understanding the length extension attack ...although the related question doesn't discuss appending of the length which MD5, SHA1, etc. do.

Let hash be the raw hash function, as you're referring to. You mentioned that the attacker knows hash(message || length), but to be more precise, they know hash(message || padding || length). Let full_hash be the proper hash with padding and length, i.e. full_hash(message) = hash(message || padding || length).

You're correct that if the attacker knows hash(message || padding || length), then they can't compute hash(message || appended_data).

But they can compute hash(message || padding || length || appended_data || actual_padding || actual_length) which is equal to full_hash(message || padding || length || appended_data), which may be enough for an attack. The inner padding and length become "garbage" which can be ignored depending on the attack scenario.

In order to carry out the attack, start from hash(message || padding || length) (i.e. the original hash), use it as the initial state for the hash, and then feed the remaining data (appended_data || actual_padding || actual_length).


Orthogonal generators of a group in Lelantus protocol In the Lelantus Paper, the authors mentionned this:

  In our case, the commitment key ck specifies a prime-order group G and three orthogonal group generators $g, h_1$ and $h_2$.

G is mentioned in the performance section of the paper to be the famous elliptic curve secp256k1. Hence, I don't understand the notion of "group generators" that are orthogonal.

Indeed the group G is of prime-order and obviously commutative (even in the general case). Hence, non-trivial generators are of prime order p as well, and their generated subgroups are the whole group G.

Am I missing something here or is the "orthogonal" notion useless or even wrong?

Note: For me, it would make sense if the sentence meant that $\langle g,\ h_1,\ h_2\rangle\ = \ G$ and the subgroups $\langle g\rangle, \langle h_1\rangle, \langle h_2\rangle$ have trivial intersections together, but the prime order of the group $G$ forbids that, no?

A GUESS: the author meant that three numbers $a,b,c \in \mathbb{Z}$ such that $$g^a\cdot h_1^n \cdot h_2^c =1$$ are infeasible to compute. While the term "orthogonal" seems inappropriate, This is a fairly standard assumption.


Is it safe to use a deterministic salt as an input to KDF (Argon2)? I'm prototyping an app that uses client-side password hashing in order to hide the "real" account password from a server (the server hashes any recieved password anyway, so no plaintext records in the database). It seem to be a controversial thing to do but I didn't find any convincing arguments against it (I'm new to cryptography so please correct me if I'm wrong).

I'm trying to figure out what would be an appropriate salt for Argon2i. Many implementations generate random salt by default but it won't allow users to log in again because using new salt produces new hash. That's why I can't avoid using deterministic salt.

My understanding is: each salt value is better to be globally unique for each user so it seems like an email address could make an OK salt in a sense that it's unique, but not globally. Email + password would certainly lower the chances of a collision but some users might have the same passwords in many apps. I'm thinking about sha256(app name + email). Would it make a good salt?

My main question is about the implications of using a deterministic salt in general. Does it make the resulting hashes easier to crack? And if it's OK, what would be an appropriate way to generate such a salt?

Another related thing I'm wondering about is how easy is it to crack the hash and not the password itself? Let's say I use Argon2 to hash a password and use the same exact password as hash (argon2(pwd = "foobar", salt = sha256("foobar")). Would it help an attacker to reveal that password by any method except using a rainbow table?

It seem to be a controversial thing to do but I didn't find any convincing arguments against it

It can be a good solution if you can transmit the salt from the server to the client, e.g. in apps or desktop apps and has some nice load-distribution properties.

  the server hashes any recieved password anyway, so no plaintext records in the database

This is actually important so a leaked database doesn't immediately allow for logins.

  Would it make a good salt?

It would work. However the "issue" is that it allows for targeted pre-computation attacks. So suppose you have an adversary who already knows a set of target users. For them they can now pre-compute a lot of password hashes so once the password database is compromised there's a very low latency to password recovery for the targets if the precomputed hashes contain a match. If you're not worried about such attacks uniqueness is the only property required from salts and may be achieved in any arbitrary way.

Indeed if you have control over the client and have bidirectional communication, using a protocol like OPAQUE is preferred as it also hides the salt.


How does Boneh–Lynn–Shacham work? As described by Wikipedia, BLS uses Diffie-Hellman in some way. I understand how Diffie-Hellman works in both its normal and elliptic curve forms. But what is the "pairing function"?

BLS signatures work in any so called gap group, i.e., a group where the computational version of the Diffie-Hellman (DH) problem - the CDH - is hard, but the decisional version of the DH problem - the DDH - is easy. Below I'm using the notation from the wikipedia article on BLS.

Just recall, that the DDH in a group $(G, g, r)$ (where $g$ is a generator and the group $G$ is of prime order $r$) is that, when given $(g, g^a, g^b, g^c)$, it's hard to decide whether $c=ab$.

If you look at the BLS signature verification, one checks whether the signature $\sigma$ for message $m$ has the form $\sigma=H(m)^x$ and writing it as $(g,h=g^x, H(m), \sigma)$, one sees that verification is to check for a valid DDH tuple (CDH needs to stay hard for unforgeability). Note that $H$ is a hash function modeled as a random oracle that maps strings to elements of $G$. So $H(m)$ can be written as $g^\gamma$ for some unknown $\gamma$.

Now, the existence of a pairing $e: G\times G \rightarrow G_T$ (symmetric for simplicity) exactly makes $G$ such a gap group. The check $e(\sigma, g) = e(H(m), h)$ in the signature verification exactly allows you to test if $(g,h=g^x, H(m), \sigma)$  is a valid DDH tuple. Using bilinearity of $e$, this should be easy to see, and I leave it as an exercise to you.

Pairings used in cryptography have evolved into a large (rather quickly changing) field and requires some time to study them. But the above symmetric pairing can be instantiated e.g., by setting $G$ as a subgroup of a supersingluar elliptic curve group, $e$ being the Weil pairing and $G_T$ a subgroup of the multiplicative group of a quadratic extension field of the curve's base field (you may want to look here for details). The choice of $H$ also depends on the setting, but it is crucial that $H$ is constructed such that one does not learn the discrete logarithm to the base $g$ from $H(m)$. You could look at the original BLS paper,who instantiate the scheme in a so called Type-2 pairing setting (in their setting, $G_2$ is the gap DH group). You may also want to look at this paper for how you can instantiate BLS in other Types of pairings.


SVP=SIVP in ring lattice (ideal lattice) SVP (shortest vector problem) is equivalent to  SIVP (shortest independent vectors problem) in ring lattice (ideal lattice). How to prove this? Could someone explain it to me?  Thanks!

Consider the ring $R = \mathbb{Z}[x]/(f(x))$ for $f(x)$ an irreducible monic polynomial of degree $n$.
Fix a basis $\{1,x,\dots,x^{n-1}\}$, and define the following transformation:
$$L(x^i) = x^{i+1}$$
Extend this transformation to all of $R$ via linearity.
Cayley-Hamilton theorem [1] states that the characteristic polynomial $p(t) = \det(L - tI)$ is such that:
$$p(L) = 0$$
One can explicitly compute the square matrix corresponding to $L$ (it is the companion matrix of $f(x)$), and it is known that:

The characteristic polynomial of $L$
The minimal polynomial of $L$
$f(x)$

Are all identical.
It follows that $f(L) = 0$, and this is the smallest polynomial $f(x)$ for which this holds, so among other things $\{1,x,\dots,x^{n-1}\}$ are linearly independent over $R$.

Now let $v(x)\in R$ be any vector (including a candidate "shortest vector").
We have that $\{v(x), xv(x), \dots, x^{n-1}v(x)\}$ are linearly independent over $R$.
This is because if there were some linear relation between them:
$$\sum_i a_iv(x)x^i = 0\implies v(x)\sum_i a_ix^i = 0\implies \sum_i a_i x^i = 0$$
Contradicting the linear independence.
As $\| x^i v(x)\|$ are all the same, we've exhibited a basis of vectors of the same norm.
So finding one short vector is enough to find all $n$ short vectors.

[1] Technically we need to make sure that Cayley-Hamiltonian holds over modules over general rings. Fortunately it is known to hold for commutative rings, so we're fine.


gnupg: display digest of key How can I display what digest algorithm has a key? If I import a public key which has MD5 as digest, I get a warning about this weak algorith. But how can I check, what digest algorithms all my keys use in my keyring?

You can use gpg --list-packets [keyfile] to see a list of all packets and their contents. All hash algorithms have numbers which you can look up in section 9.4 of RFC 4880, "Hash Algorithms".

Alternatively, use pgpdump [keyfile] to create a similar output, but already containing the algorithm names instead of their numeric identifiers.


Difference between lightweight, online and low memory Authenticated Encryption schemes What is the basic difference between the following types of Authenticated Encryption (AE) schemes?

Lightweight Authenticated encryption
Online Authenticated Encryption
Authenticated Encryption for low memory devices

Are they all the same or is there a specific difference between them?

Thought I'd begin with some references for you that might be of interest. These terms are used as key 'selling points' for a number of schemes, including many of the CAESAR submissions. Some examples using the terms specifically are given below - most of which are from CAESER because I have the zoo in-front of me:

"Online": OCB, Ascon, CBA, APE, NORX
"memory-constrained devices": Ketje / Keyak / Spongewrap,
"lightweight": PRESENT, JAMBO, APE, BLINKER (presented CT-RSA14)

Also, there was an eCrypt report on Lightweight crypto.

I can't provide a decent distinction between the 1 & 3, since low memory footprint is a more specific sub-aim of lightweight. Both of these are types of schemes designed to be run in highly restricted environments, such as on embedded devices. These often have constraints that actually affect what operations you can/cannot run on them, such that more efficient algorithms than an AES-based mode may be preferred.

Online AE deals with something completely different. Let A be some associated data, $M=(M_1,\dots,M_n)$ a message, encrypting to $C=(C_0,\dots,C_n)$ and tag $T$. The scheme is online if $C_i$ can be calculated without knowledge of $M_j$ for any $j>i$.

Often lightweight or small footprint ciphers are 'online'. This is because it allows them to process plaintext blocks as they come through. In contrast, an offline cipher would have to collect the complete plaintext before calculating the ciphertext, which means it must have enough memory to store $n$ blocks of data, which not all devices will do - especially for example a small industrial sensor reporting on large amounts of data.

Recently there has been some controversy about the validity of an online decryption function, since they release unverified plaintext (for example, see the CAESER mailing list or this paper). For categorization of some schemes under development, see here.


Do I need to prove this? I am using ABE scheme that has already proven under BDHE assumption. Here is the scheme https://eprint.iacr.org/2008/290.pdf

In the key generation algorithm, I want to tie the user secret key components with a message $m∈GT$. $m$ is different from the one used in the encryption algorithm.
I did like this

$S=M.e(g^t, g^d) = M.e(g,g)^{td}$  where $t,d∈Z$ are randomly chosen.
$t$ is used to tie all other secret key components together.

$S$ will be given to the user along with the secret key which have these components $(K=g^bg^{at}, L=g^t, h1^t, h2^t, …)$

$d $ and $g^d$ will be kept secure with the authority.

My question, do I need to re-prove the security of the scheme considering $S$

I purposefully did not look at the details of the change you are proposing because whatever the change is, the answer is a resounding YES. If you make any change to a cryptographic construction, then you must prove the security of the modified scheme. If you are lucky, you may be able to reduce the security of the modified scheme to the original scheme, or you may be able to reuse a lot of the intermediate claims of the proof of the original scheme. However, you must prove!


Coefficients in Shamir's Secret Sharing Scheme Sorry if this is a stupid question, but: in Shamir's scheme, we construct a polynomial and make our secret $S$ the zero-th coefficient $a_0$. What, if anything, necessitates this - in other words, can we make include $S$ as $a_1$ or any other coefficient?

In Shamir's scheme is a secret sharing scheme, that is, someone that has fewer shares than is required get no information about the secret.  For example, if we have a system where we require 3 shares to reveal the shared secret, then someone with 2 shares cannot be able to reconstruct it.

This is true if we make the shared secret the zero-th coefficient; with $N-1$ shares, every possible value for the zero-th coefficient is equally possible.

This turns out to be also true for the (N-1)th coefficient; however it turns out not to be true for any intermediate coefficient.

Here's a simple example to illustrate this; suppose we pick the field $GF(5)$, and we select $N=3$ (and is, 3 shares are required to reveal the secret); hence we pick a quadratic with the secret as one of the coefficients.

Then, we distribute the shares; in this example, two of the shares we distribute are $(1, 1)$ and $(4, 0)$; that is, the holder of those two shares know that, for the secret polynomial $P$, we have $P(1) = 1$ and $P(4) = 0$.

Now, the holder of two shares should not be able to reconstruct the secret; however what they can do is list all the quadratics that are consistent with the values he does know.  There are five possible polynomials with degree at most 2 that meet the criteria:

$$0x^2 + 3x + 3$$

$$1x^2 + 3x + 2$$

$$2x^2 + 3x + 1$$

$$3x^2 + 3x + 0$$

$$4x^2 + 3x + 4$$

It is easy to confirm that plugging in $x=1$ and $x=4$ into the above polynomials will result in the known values 1 and 0.

Now, our attacker knows that one of these five equations are the secret one, but he has no information on which it can be.  If the shared secret were the 0th or the (N-1)th coefficient, we can see that he learns nothing; all values are equiprobable.   However, if the shared secret were the middle coefficient, well, all these polynomials have a middle coefficient of 3, and so the attacker would have learned the secret, even though he shouldn't have been able to.

This sort of thing can happen to any of the middle coefficients; the only safe coefficients are the first and the last.

---- UPDATE ----

Ok, I found a case where a middle coefficient is also safe; that is the case where the field has characteristic 2 (i.e. is $GF(2^n)$ for some $n$), and $N=3$.  In that specific case, it turns out that the behavior I listed above cannot happen; all $2^n$ possible equations (when $N-1$ shares are known) will have different values for the $x$ coefficient.  I believe that this specific case is the only example of a situation where an intermediate coordinate is safe; that in all other cases, you can find $N-1$ shares so that an intermediate coordinate is determinable with $N-1$ shares.


How to check a file was encrypted (really & correctly) I would like to audit how an implementation of an encryption algorithm is really performed with the following given data of the problem:

the encryption mechanism is reversible (this isn’t a signature),
the algorithm is pretended to be AES, but might be implemented correctly or not, or worse something else,
the key is not known (in the case I am interested in, I want to check that all files are really and correctly encrypted, but I could play with specifically designed ones),
I don't have access to the source code.

At least I would like to be able to detect that the file is not encrypted.
Next I would like to be able to detect that the RNG is running in a tiny set or not really random.

In a first approach I thought to make an analysis of the randomness quality of the encrypted file: average value + standard deviation (with a tool like ent).
But I immediatly thought of artificial files with a perfect average value
and standard deviation which are perfectly regular and not the result of any encryption.
Then my first approach is wrong.

The environment in which I will make this audit is a Unix one.
( I cannot use tools or algorithms I cannot read, compile and check myself. )

Practical case:

I would like to check that my iPhone is correctly encrypted and what is the AES key derived from either a constant, my password, a hardware uniq identifier.
I would like to perform the same validation of an iPhone of any staff member which will ask me to make the same validation for his professionnal iPhone. This is a service toward users to provide them trust in what they think is encrypted and has to be.

If you can't get access to the key for at least some sample uses, there's no way to be sure. For example, it's impossible to distinguish AES-128 from AES-256 if you don't have access to the key. That's true of any encryption method: without knowing the key, you can't distinguish the ciphertext from random data of the same length.

A professional auditor would normally get access to some test keys, if they can't normally access those keys through some administration interface.

You can make a statistical test, but all this will tell you is that the encryption is not completely botched or skipped.

If your vendor is not completely dishonest and they claim to have used AES, they probably did use AES. A far more common problem than not using AES is using AES wrong. Here too, you can't be sure that they got it right, but you can at least check for some common problems.

Check how the length of the ciphertext varies depending on the length of the plaintext. The ciphertext should include an initialization vector and an authentication tag, each of which normally adds 16 bytes. If the ciphertext is not 32 bytes larger than the plaintext, something is probably wrong, but there are cases where it can be ok (e.g. for disk encryption where the sector number is used to build unique IVs and no threat requires authentication).

Pass the same inputs in different conditions and make sure that the resulting ciphertexts are completely different. If you can arrange to encrypt multiple messages with the same key, make sure that identical messages result in completely different ciphertexts. This validates that initialization vectors are generated, if not correctly, then at least non-stupidly.

If there's a way for you to submit modified ciphertexts, do that and check that they are rejected with a generic “invalid ciphertext” error, rather than a specific error due to invalid content. This validates that authenticated encryption is used. There are threat models where it's ok not to have authentication, but you need to tread very carefully.

Two things that you definitely cannot know by looking at the output is whether the keys are generated and stored securely. (As opposed to e.g. using a non-cryptographic random generator to generate keys, and writing a copy of the secret keys to an unprotected location.) You can only audit this by looking at the behavior of the system.


Lattice generation from basis? This might be a very short very obvious answer, because I've yet to come across a question similar to mine in my searches.

Given a lattice L, with a good base B1 and a bad base B2, what stops an attacker from simply re-creating the lattice structure from the public base B2?

It might just be a terminology mix-up on my part, but that's what I recall being the purpose of basis's in regular algebra.

I'll turn my comment into an answer:

  Given a lattice L, with a good base B1 and a bad base B2, what stops an attacker from simply re-creating the lattice structure from the public base B2?

There's nothing stopping them, the lattice structure isn't secret. Like you say, examining the lattice structure is trivial. The use of lattices in cryptography derives from the fact that even if you know the lattice's structure (i.e. have some basis B), deriving a "good" basis is hard.

  Still, deriving the lattice structure wouldn't mean that one could, for example in a CVP problem, easily output the closest vector?

No. :) When you visualize this problem in low dimensions, like 2, it seems like it should be that way, no? But in high dimensions, this problem is very difficult when you have a random (i.e. bad) basis.

Try out your technique. Suppose we have $n$ dimensions. Our basis $B$ is a bunch of vectors going in random directions. We want to enumerate the points close to $\mathbf{t}$. How many points could potentially be "close" to the target? How do you generate these points efficiently with your basis $B$?


PBKDF2 Salt and Password Ordering I am currently reading about PBKDF2, and understand that the salt is used only once, while the password is used multiple times in the computation of the final key (see this question). How would the integrity of PBKDF2 change if the roles of password and salt are changed?

PBKDF2 is defined for an arbitrary PRF, but in practice HMAC is usually used. Either with SHA-1 (original definition), SHA-256 (e.g. in scrypt) or even SHA-512-256 (NaCL). So first you can look at how swapping key and message affects HMAC.

HMAC has two cases depending on the length of the key: if it's no longer than the block size of the hash, it is used as is; if it's longer it is first hashed. After that, two keys are derived by XORing it with pads and the final function is:

$$H(k_1||H(k_2||m))$$

This leads to two reasons to prefer the defined order to the swapped one:

For every key shorter than the blocksize, there's an equivalent key $k' = k||0$, where a zero byte is appended. For every key longer than the block size, there's another key $k' = H(k)$ which is equivalent.

For randomly generated keys, or even passwords, these do not matter in practice. If you used a message in that position, however, it would be malleable – you could swap a long message with a gibberish one and use the same MAC value.
The key derivation through hash and/or XOR, as well as the initial block of each of the two hashes can be calculated once for a given key and used for many messages. In the swapped order everything would have to be calculated again.

Neither of these is a problem in PBKDF2, if you use a constant width salt, like a 256-bit random number. The first can only happen if two distinct salts can collide, which – barring an actual hash collision – requires them to be different length. The second doesn't matter, since many iterations are done with the same $k$ whether it's the password or the salt. (Swapping makes it an inconsequential amount faster to try multiple passwords against one salt.)

Additionally, swapping the order will not make finding a preimage any easier, unless the hash is broken. Since preimage resistance is what a password hash in concerned with, HMAC with arguments swapped should be OK.

(The above is not true for all MACs. For example, it is trivial to find some preimages for CBC-MAC with a known key.)

Regarding PBKDF2 itself, there's the additional fact that the password (i.e. HMAC key) is a part of every hash iteration, while the salt is only used once. This affects the cycles the hash can enter. With a constant salt as the HMAC key, every possible password would enter the same set of cycles. Since it only happens after around $2^{80}$ iterations for SHA-1, it too doesn't matter, even if it was somehow exploitable.

In conclusion, then, swapping the password and salt with PBKDF2-HMAC seems secure. With another PRF it could be insecure. Swapping them in HMAC for many other uses is also insecure. However, there is no good reason to swap them, so you should still use the normal defined order.


Zero Knowledge Proof - Offline Data I've been reading about Zero Knowledge Proofs with some interest, but I'm still unclear if it can be used to solve my real-life problem.

I'm wondering if someone can help me understand a little better how they work - intuitively it seems possible.

Let's assume I have 3 bank accounts with different balances, 1 balance is known, as read-only credentials to access the account are made public, but the second and third accounts are private, with the credentials kept secret.

Would it be possible to use a Zero Knowledge Proof to conclusively prove that the balances of the second and third accounts are what I say they are?

Including a brief description of what a ZKP is (quoting the ZKP article at Wikipedia):

  In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that a given statement is true, without conveying any information apart from the fact that the statement is indeed true.

So, extending this definition, the statement in my example would be: the balance of account A = X. Which the verifier would require the prover to prove is true.

You would need something to prevent do what you would do if those balances were what you said they are from causing the verifier to accept.

That main way of getting that is the prover and verifier both have a statistically binding encapsulation for each of those balances, as described in the paper Improved Efficiency for CCA-Secure Cryptosystems Built Using Identity-Based Encryption (PDF), and the prover additionally has a decapsulation string for each of those.

If you weaken from proofs to arguments as described in the paper Zero Knowledge and Soundness are Symmetric (PDF), then you could let the encapsulation scheme(s) be only computationally binding or instead have the balances be signed in a suitable format, where the prover and verifier both know the signature verification key(s).


Manually creating a GPG Public Key I want to manually create a GPG public key that can be imported into GPG, i.e. I want to create a file with a Public-Key Packet, a User ID Packet and a Signature Packet (for an example see here). I already managed to correctly create a Public-Key Packet with a User ID Packet and a Signature Packet, except for the hash/signature of the Signature Packet.
I tried to hash data as described in RFC 4880, however the description there is rather imprecise. For example it does not state what exactly constitutes a public key body (is it only n or also the public exponent e?) or if "tags" are to be hashed as well. With tags I mean fixed data preceding certain elements of a packet (e.g. for the public exponent e the tag is 00 11; see here).
Unfortunately the GPG source code and its resulting binary are also not very helpful for understanding what data exactly is hashed. I am currently tracing the export function (i.e. gpg --export) but I can't find the function that is used to hash the data for the Signature Packet (interestingly enough, neither the hash_public_key() function in g10/keyid.c nor the make_keysig_packet() function in g10/sign.c seem to be used for that).
Does anyone know what exactly is hashed and can exemplify it?

Based on the example given in the question (see here) the following (hex-encoded) bytes would be hashed:
From the Public-Key Packet
Ciphertype Byte: 99

Key Length: 01 0d

Version: 04

CreatedAt: 5e f4 a2 c6

Algorithm: 01

n (with tag): 08 00 a8 14 6d b3 75 12 72 33 1e 92 54 c5 43 f6 44 d2 22 5d 4d 9b 0c b8 5d 60 60 8b f0 39 08 1e 31 29 e2 f5 4c 83 e0 71 b7 22 e3 f8 78 9b c4 a2 c1 aa 70 72 3a eb c5 1e ec d1 65 9b 58 50 20 f4 d0 36 db 79 c8 24 6a bd 43 3f 08 28 6c 35 b2 16 30 6b 14 4c 94 74 5a fa 85 5a 05 8d 06 3b 94 29 f1 98 71 f4 04 48 9b 84 ef b9 94 65 eb 9c 0a 97 b6 d2 46 13 64 42 57 13 ea 08 48 62 5f 24 ea f3 d5 f5 2b 72 b6 96 e0 af ac 4b 68 41 af fc 64 cd 55 a1 75 05 33 ed 0b 78 a2 6c d4 33 d5 db 6a 72 78 78 9c ae 45 74 08 d2 40 72 30 4d f2 62 ea 29 6e d9 e8 5d 12 cf a0 7a e6 60 44 29 06 75 4f d0 71 c8 9f 35 8a 45 52 45 20 04 7a 79 cc 54 8e ba 10 1b ae f0 9e 24 68 56 98 18 10 2b f5 95 c1 5a 50 57 5a 47 6f e5 61 44 f7 2f 86 fe 8c 54 a1 4d a8 13 68 e6 e2 b4 57 aa 2f fa c5 06 fc 13 47 98 23 c7

e (with tag): 00 11 01 00 01

From the User ID Packet
Ciphertype Byte: b4

Length: 00 00 00 1c

UserID: 47 50 47 20 54 65 73 74 20 4b 65 79 20 3c 74 65 73 74 40 74 65 73 74 2e 63 6f 6d 3e

From the Signature Packet
Version: 04

Signature Type: 13

Public Key Algorithm: 01

Hash Algorithm: 0a

Hashed Data Count: 00 38

Undefined Subpacket Length: 16

Undefined Subpacket Type: 21

Undefined Subpacket Data: 04 43 3f bc 55 ab 6d 09 17 21 13 18 3a 79 1a 5a be 3e 62 44 95

Creation Time Subpacket Length: 05

Creation Time Subpacket Type: 02

Creation Time Subpacket Data: 5e f4 a2 c6

Key Flags Subpacket Length: 02

Key Flags Subpacket Type: 1b

Key Flags Subpacket Data: 2f

Preferred Symmetric Algorithms Subpacket Length: 05

Preferred Symmetric Algorithms Subpacket Type: 0b

Preferred Symmetric Algorithms Subpacket Data: 09 08 07 02

Preferred Hash Algorithms Subpacket Length: 06

Preferred Hash Algorithms Subpacket Type: 15

Preferred Hash Algorithms Subpacket Data: 0a 09 08 0b 02

Preferred Compression Algorithms Subpacket Length: 04

Preferred Compression Algorithms Subpacket Type: 16

Preferred Compression Algorithms Subpacket Data: 02 03 01

Features Subpacket Length: 02

Features Subpacket Type: 1e

Features Subpacket Data: 01

Key Server Preferences Subpacket Length: 02

Key Server Preferences Subpacket Type: 17

Key Server Preferences Subpacket Data: 80

Other Data
Trailer: 04 ff

Big-Endian Count of Hashed Signature Packet Data: 00 00 00 3e

Full Byte Array
(i.e. a concatenation of the bytes in 'From the Public-Key Packet', 'From the User ID Packet', 'From the Signature Packet', and 'Other Data'):
99 01 0d 04 5e f4 a2 c6 01 08 00 a8 14 6d b3 75 12 72 33 1e 92 54 c5 43 f6 44 d2 22 5d 4d 9b 0c b8 5d 60 60 8b f0 39 08 1e 31 29 e2 f5 4c 83 e0 71 b7 22 e3 f8 78 9b c4 a2 c1 aa 70 72 3a eb c5 1e ec d1 65 9b 58 50 20 f4 d0 36 db 79 c8 24 6a bd 43 3f 08 28 6c 35 b2 16 30 6b 14 4c 94 74 5a fa 85 5a 05 8d 06 3b 94 29 f1 98 71 f4 04 48 9b 84 ef b9 94 65 eb 9c 0a 97 b6 d2 46 13 64 42 57 13 ea 08 48 62 5f 24 ea f3 d5 f5 2b 72 b6 96 e0 af ac 4b 68 41 af fc 64 cd 55 a1 75 05 33 ed 0b 78 a2 6c d4 33 d5 db 6a 72 78 78 9c ae 45 74 08 d2 40 72 30 4d f2 62 ea 29 6e d9 e8 5d 12 cf a0 7a e6 60 44 29 06 75 4f d0 71 c8 9f 35 8a 45 52 45 20 04 7a 79 cc 54 8e ba 10 1b ae f0 9e 24 68 56 98 18 10 2b f5 95 c1 5a 50 57 5a 47 6f e5 61 44 f7 2f 86 fe 8c 54 a1 4d a8 13 68 e6 e2 b4 57 aa 2f fa c5 06 fc 13 47 98 23 c7 00 11 01 00 01 b4 00 00 00 1c 47 50 47 20 54 65 73 74 20 4b 65 79 20 3c 74 65 73 74 40 74 65 73 74 2e 63 6f 6d 3e 04 13 01 0a 00 38 16 21 04 43 3f bc 55 ab 6d 09 17 21 13 18 3a 79 1a 5a be 3e 62 44 95 05 02 5e f4 a2 c6 02 1b 2f 05 0b 09 08 07 02 06 15 0a 09 08 0b 02 04 16 02 03 01 02 1e 01 02 17 80 04 ff 00 00 00 3e

Resulting Hash
2f 9b ad fd 89 90 e9 34 f3 15 c6 9c c5 8e 45 12 47 29 fe ab e6 18 a2 e2 71 fb bf e1 9e 20 10 8a 86 ea d9 dd 5b 87 58 87 45 85 98 2a 68 14 e9 e2 ef 9e b6 07 12 1d 9b 7c 15 8f 58 79 c2 92 c5 e9

The two first bytes of the generated hash are shown in the signedHashValuePrefix of the used example (which was generated with the GPG CLI).


Can you tell if this ECB mode mitigation idea is "OK"? The context: you have to encrypt passwords (reversible, for accessing external services), and also some customer data for privacy reasons, and you need to use AES-ECB mode...

The idea to mitigate the worst of ECB is, we encrypt each single ''message'' with a new random key. Then we encrypt this unique key with a master key, and store it alongside the ''message'', while the master key is kept somewhere else completely.

(As additional measure, also ensuring that the encrypted unique key has its padding block filled with randoms, so the padding doesn't show up as repeating pattern either between the unique keys.)

When considering the general ECB issues, I take note of the fact that:

the master key will ever encrypt only random, single-block ''messages'' (the unique keys), and that
the most critical data to be protected is passwords, also of a single-block nature.

Makes any sense? Has any major issue? I was mainly concerned with avoiding the textbook-messup situation of an ecb mode password db where you could see every repetition of common passwords, making for extremely easy, non-specialist ''attacks''.

As already mentioned, if you've got ECB you can certainly design other modes of operation. Probably the easiest one to implement is CTR mode: you simply line up a number of counters (each of the block size of the underlying cipher) and then encrypt them using ECB. You can XOR the result with the plaintext to encrypt or decrypt data.

You'd still have to use a nonce for the initial counter value of course, if you want to reuse the same key.

Limiting passwords to a certain size is a bad idea. So is storing an encrypted password instead of storing a hash of the password.

If you use CTR mode I'd say limit the password size to 64 bytes and pad the password to that size using zero padding - then encrypt the result. That way you'd allow longer passwords and you would not leak the password size right away.


Is the concatenation of PRG output still a PRG? I am puzzled by the following question, since I am not very familiar with proof methods of Pseudo-Random Generators (I only know how to use the inequality from the PRG definition to prove or disprove, but it may not work in this case?).

For any PRG $G$, if we partition an input binary string $s$ with length $n$, into substrings $s_1$ and $s_2$ with $s=s_1||s_2$ and where $|s_1|\leq|s_2|\leq|s_1|+1$, which means almost half and half, then is the following new generator $G'$ a PRG as well?
$G'(s)=G(s_1)||G(s_2)$,which means use the two sub-strings as input to $G$, and concatenate the results. Assume $|G(n)|=n+1$, and here clearly $|G'(n)|=n+2$

I think such $G'$ is a PRG but I do not know how to prove it, and I also wonder if it could be generalized like $s=s_1||s_2|| \ldots s_m$ and $G'(s)=G(s_1)||G(s_2)||\ldots G(s_m)$, is $G'(s)$ a PRG as well?

The function $G'$, as you intuited, is indeed a PRG. The standard way to establish such results is through the hybrid argument. Details follow.

Let $G_n:\{0,1\}^n\rightarrow\{0,1\}^{n+1}$ be an $\epsilon(n)$-secure PRG; that is:
  $$G_n(U_n)\approx_{\epsilon(n)}U_{n+1},~~~~~(1)$$
where $\approx_{\epsilon(n)}$ denotes computational distance$^*$ of $\epsilon(n)$, and $U_n$ is the uniform distribution on $\{0,1\}^n$.

Given $(1)$, we show that $G'_n$ is an $2\epsilon(n/2)$-secure PRG (for even $n$ for the moment); that is:
  $$G_{n/2}(U_{n/2})\|G_{n/2}(U_{n/2})\approx_{2\epsilon(n/2)}U_{n+2}.~~~~~(2)$$
This is accomplished in two steps using a hybrid (intermediate) distribution $U_{n/2+1}\|G_{n/2}(U_{n/2})$. We first show that
  $$G_{n/2}(U_{n/2})\|G_{n/2}(U_{n/2})\approx_{\epsilon(n/2)}U_{n/2+1}\|G_{n/2}(U_{n/2}),~~~~~(3)$$
and then that
$$U_{n/2+1}\|G_{n/2}(U_{n/2})\approx_{\epsilon(n/2)}U_{n+2}.~~~~~(4)$$
$(2)$ follows by an application of the triangle inequality to $(3)$ and $(4)$. Since the arguments for $(3)$ and $(4)$ are similar, we prove just $(3)$.

Suppose for contradiction that $G_{n/2}(U_{n/2})\|G_{n/2}(U_{n/2})$ is not $\epsilon(n/2)$-close to $U_{n/2+1}\|G_{n/2}(U_{n/2})$; then we show that $G_{n/2}(U_{n/2})$ is not $\epsilon(n/2)$-close to $U_{n/2}$ contradicting $(1)$. To be precise, given a distinguisher $\mathsf{D}$ for the former, we construct a distinguisher $\mathsf{D}'$ for the latter. The construction of $\mathsf{D}'$ is straightforward: given a challenge $y\in\{0,1\}^{n/2+1}$ (which is either $G_{n/2}(U_{n/2})$ or $U_{n/2+1}$), run $\mathsf{D}$ on $y\|G_{n/2}(U_{n/2})$ and return whatever $\mathsf{D}$ returns. If $y=G_{n/2}(U_{n/2})$ then $\mathsf{D}'$ presents  $G_{n/2}(U_{n/2})\|G_{n/2}(U_{n/2})$ to $\mathsf{D}$; otherwise, it presents $U_{n/2+1}\|G_{n/2}(U_{n/2})$. Thus, $\mathsf{D}$'s ability to distinguish the distributions in $(3)$ helps $\mathsf{D}'$ distinguish the distributions in $(1)$.

A similar argument can be made for odd values of $n$, and together you get that $G'$ is a PRG. The argument can be extended for $G'(s)=G(s_1)||G(s_2)||\ldots G(s_m)$ for $s=s_1||s_2||\ldots s_m$: one has to define a $m-1$ hybrid distributions, where the $i^{th}$ hybrid replaces the first $i$ calls of $G$ with a uniformly random string; i.e., assuming $m$ divides $n$,
  $$\underbrace{U_{n/m+1}\|\cdots\|U_{n/m+1}}_{i \text{ terms}}\|G_{n/m}(U_{n/m})\|\cdots\|G_{n/m}(U_{n/m}).$$
Also, this PRG is only $m\cdot\epsilon(n/m)$-secure.

$^*$A distribution $X=\{X_n\}$ is $\epsilon(n)$-computationally-close from another distribution $Y=\{Y_n\}$ if for every computationally-bounded distinguisher $\mathsf{D}$,
 $$\big|\Pr[\mathsf{D}(X_n)=1]-\Pr[\mathsf{D}(Y_n)=1]\big|\leq\epsilon(n).$$
In particular $X$ is computationally indistinguishable from $Y$ if $\epsilon(n)$ is negligible in $n$.


multiplicative inverse in galois field $2^8$ I am trying to compute the multiplicative inverse in galois field $2^8$.The question is to find the multiplicative inverse of the polynomial $x^5+x^4+x^3$
in galois field $2^8$ with the irreducible polynomial $x^8+x^4+x^3+x+1$. To get it I used the Extended Euclidean division but with operations used in galois field $2^8$ My answer is $x^7+x^6+x^5+x^4+x$ while the other answer is $x^6+x^4+x^2+x+1$. I am not sure if this answer is right so i need to make sure. If my answer is not right can someone please show me the details of getting to the solution. Thank you

Set $g(x)=x^8+x^4+x^3+x+1$ , $p(x)= x^5+x^4+x^3$.

Applying Euclidean algorithm,

$g(x)=p(x)(x^3+x^2+1) + (x+1)$,

$p(x)=(x^4+x^2+x+1)(x+1)+1$.

Therefore, $1=p(x) + (x^4+x^2+x+1)(x+1)
            = p(x) + (x^4+x^2+x+1)[g(x) + p(x)(x^3+x^2+1)]
            = [(x^4+x^2+x+1)(x^3+x^2+1)+1]p(x) + (x^4+x^2+x+1)g(x)$

Setting $q(x) = (x^4+x^2+x+1)(x^3+x^2+1)+1$ (please expand yourself),
$p(x)q(x) = 1  \text{mod}  g(x)$.
So $q(x)$ is the inverse of $p(x)$.

Maybe there are some errors in my calculations because I didn't do double-check, but I'm sure of the process.

Sorry for bad editing. I'm a newbie to this site.

To check the answer, multiply the result polynomial to p(x) and divide by g(x).
The answer must be 1.


HMAC-SHA256 vs HMAC-SHA512 for JWT API authentication Which algorithm is recommended to use when encoding / decoding JWT web application tokens? Is using HMAC-SHA256 enough or would using HMAC-SHA512 provide more security? And on 64bit machines, is it true that HMAC-SHA512 is faster than HMAC-SHA256?

Both algorithms provide plenty of security, near the output size of the hash. So even though HMAC-512 will be stronger, the difference is inconsequential. If this ever breaks it is because the algorithm itself is broken and as both hash algorithms are related, it is likely that both would be in trouble. However, no such attack is known and the HMAC construct itself appears to be very strong indeed.

SHA-512 is indeed faster than SHA-256 on 64 bit machines. It may be that the overhead provided by the block size of SHA-512 is detrimental to HMAC-ing short length message sizes. But you can speedup larger messages sizes using HMAC-SHA-512 for sure. Then again, SHA-256 is plenty fast itself, and is faster on 32 bit and lower machines, so I'd go for HMAC-SHA-256 if lower end machines could be involved.

Note that newer x86 processors also contain SHA-1 and SHA-256 accelerator hardware, so that may shift the speed advantage back into SHA-256's favor compared to SHA-512.


AES CCM Mode (CTR with CBC-MAC) For CCM mode of AES can anyone explain what the difference is between $B_i$'s and $m$? Is the nonce value for $B_i$'s and $A_i$'s the same?

What is $l(a)$ and $L$? What is the minimum value of size of $m$?

Does authentication process use the data of $m$?

The standard definition of CCM is NIST SP800-38C.  Not all of the symbols you cited appear in NIST SP800-38C.  If you're using a different reference, you'll need to cite it to get a more specific answer.

  [C]an anyone explain what the difference is between $B_i$'s and $m$?

The $B_i$ are the blocks of input for CBC-MAC, derived from encoding the nonce, associated data, and payload uniquely into a bit string.

$m$ is the number of 128-bit blocks needed to cover the payload to be encrypted.

  Is the nonce value for $B_i$'s and $A_i$'s the same?

The CCM encryption operation takes a nonce $N$, an associated data string $A$, and a payload $P$, and returns an authenticated ciphertext.  These inputs are all uniquely encoded into a sequence $B_0, B_1, \ldots, B_r$ of 128-bit blocks for authentication.  Thus, the nonce $N$ is used to compute some of the $B_i$ blocks, and the associated data string $A$ is used to compute some of the other $B_i$ blocks.

The symbol $A_i$ does not appear in NIST SP800-38C.

  What is $l(a)$ and $L$?

These symbols $l(a)$ and $L$ don't appear in NIST SP800-38C.

  What is the minimum value of size of $m$?

The minimum value of $m$, the number of 128-bit blocks needed to cover the payload $P$, is zero: the payload may be empty, in which case CCM reduces to a message authentication code.

  Does authentication process use the data of $m$?

$m$ is a number of blocks.  CCM does authenticate the nonce $N$, the associated data $A$, and the payload $P$.  Without knowledge of the secret key, changing the lengths of any of these strings will, with high probability, cause the recipient to reject a message as a forgery.

Details.
For a 128-bit block cipher $E_K$, the inputs to CCM are:

a key $K$,
an octet string $N$ of between 7 and 13 octets inclusive, the nonce;
an octet string $A$ of any length, the associated data; and
an octet string $P$ of any length, the payload.

The authentication tag in CCM is computed first by encoding the tuple $(N, A, P)$ as a sequence of 128-bit blocks $B_0, B_1, B_2, \ldots, B_r$, as described in §A.2, pp. 12–14; then by computing $Y_0 = E_K(B_0)$, $Y_1 = E_K(B_1 \oplus Y_0)$, $Y_2 = E_K(B_2 \oplus Y_1)$, etc., setting $T = Y_r$, and revealing $$T \oplus E_K(N \mathbin\Vert 0).$$  $T$ is effectively the CBC-MAC tag for the string $B_0 \mathbin\Vert B_1 \mathbin\Vert B_2 \mathbin\Vert \cdots \mathbin\Vert B_r$.  Since CBC-MAC on variable-length messages is not itself a secure MAC, the actual authentication tag in CCM is the CBC-MAC tag $T$ concealed by the single-block one-time pad $E_K(N \mathbin\Vert 0)$.

The ciphertext is computed by adding to the payload $P$ the first $|P|$ bits of the one-time pad $$E_K(N \mathbin\Vert 1) \mathbin\Vert E_K(N \mathbin\Vert 2) \mathbin\Vert \cdots \mathbin\Vert E_K(N \mathbin\Vert m)$$ generated by the block cipher $E_K$ in CTR mode, where $|P|$ is the number of bits in $P$ (written $\mathit{Plen}$ in the standard) and $m = \lceil|P|/128\rceil$ is the number of 128-bit blocks needed to cover the length of the payload $P$.


Security of CBC-MAC fixed length with zero padding I see everywhere that fixed length CBC-MAC should be more or less secure against forgery. But is it really ?

Could you forge a message assuming by example that you use CBC-MAC with let's say always 100 blocks (if it is less than 100 you pad with 0 until it reaches 100 block, so you can authenticate message from 0 to 100*block length bits) if you have access to an oracle?

You don't know the key(it is fixed), the IV is fixed to 0 and the Oracle only returns the MAC.

Let's simplify this to one-block messages with a 128-bit block.  Your scheme to authenticate a message whose length in bits $n$ is anywhere from 0 to 128 is $$\operatorname{MAC}_k(m) = \operatorname{AES}_k(\operatorname{pad}(m)),$$ where $\operatorname{pad}(m) = m \mathbin\Vert 0^{128 - n}$, and $0^{128 - n}$ means a string of $128 - n$ zero bits.

Note that for any message $m$ of fewer than 128 bits, $\operatorname{MAC}_k(m) = \operatorname{MAC}_k(m \mathbin\Vert 0)$.  Thus if I can learn, via an oracle, the tag of any message, the same tag will authenticate the same message with zeros appended, or, if it has trailing zeros, the same message with trailing zeros stripped.

The problem is not with AES, or CBC, or CBC-MAC, or the fixed block size, or anything like that.  The problem is that $\operatorname{pad}(m) = \operatorname{pad}(m \mathbin\Vert 0)$.  For each padded message, there must be a unique unpadded message.  This padding scheme fails that.


PostQuantum Lattice-based schemes and Nguyen-Regev like attacks As far as I know NTRUSign is considered to be a Post-Quantum scheme but it's vulnerable to the Nguyen-Regev attack that allow to recover private key when there is an access to signature oracle (as it stated in the original paper, 400 message-signature pairs are enough).

After that paper some improvements were proposed and cracked and now NTRUSign seems to be broken.

Do other lattice-based Post-Quantum schemes suffer from the attack by Nguyen-Regev or similar attacks? Signature and key agreement schemes should also be considered.

NTRUSign does not have a security reduction of the type "if one can break the scheme then one can find short vectors in some lattice."  There are several other lattice schemes that do have such a reduction, and are therefore unaffected (as far as we know) by the Nguyen-Regev attack.  If they were affected, then we would have a better algorithm fro finding short vectors in lattices.


What is the difference between a random oracle and a probabilistic algorithm? What is the difference between a random oracle and a probabilistic algorithm?

Essentially a probabilistic algorithm is simply an algorithm that makes random choices (i.e., takes some random bits). So any algorithm that involves sampling random numbers or the like is a probabilistic algorithm.

A random oracle is a theoretical construct mostly used to analyze cryptographic schemes. It is an oracle that on all inputs gives a uniformly random output, but gives the same output each time its queried on the same input. Often this is used as a model of an idealized hash function. There is a more thorough description of it in the answer here.


Ring signatures in ECC Are ring signatures possible with elliptic curves? If so how. The original paper by Rivest, Shamir, Tauman seems to require an invertible trapdoor function. But I've only seen algorithms for secret agreement (ECDH for example) with elliptic curves. That doesn't seem to be adequate to complete the ring - don't you need invertibility?

As suggested, here is a hopefully entry-level precis of the paper linked in the comment above.
A Discrete Logarithm based asymmetric key system lacks a true trapdoor function - you can't compute a pre-image for an arbitrary image. Instead, a Schnorr signature relies on a slightly weaker condition. A generalized Schnorr signature can be considered to have two parts:

a function $O_{K}(i, s)$ taking public key, $K$, an input $i$ and a signature $s$. In ECC, the main component of $O_K(i,s)$ is a bit representation of $s\cdot G+i\cdot K$, where $G$ is the canonical generator for the ECC group and $x\cdot h$ is multiplication of the curve point $h$ by the scalar $x$. Other data may be appended to this bit representation, such as the message to be signed and the list of candidate keys in the ring signature. Generally, it must contain enough information to precisely specify the claim the signature is intended to prove, so that the signature can't be replayed in any other context.
a hash function $H(o, m)$ which takes $o$, any output of $O$, and $m$, the message to be authenticated.

$O$ has the additional property that, knowing the secret key corresponding to $K$, it is possible to construct arbitrarily many $o'$ where it is possible to find $s$ for any given $i$ s.t. $o' = O(i, s)$. i.e. there are specific outputs where we can solve for the signature given any input. Call this a preimageable output.
In a standard Schnorr signature we...

construct such a preimageable output $o'$ and pass to $H$
take $i = H(o', m)$ and solve for $s$.
Our signature is $(i, s)$

We verify by checking $i = H( O_{K}(i, s), m )$, i.e. that the input to $O$ is equal to the output of $H$.
Assuming we know the secret key for $K_{1}$ in a set of $K_{1 ... n}$ public keys, we can construct a ring signature as follows:

Construct $o'_{1}$, a preimageable output of $O_{K_{1}}$
Calculate $i_{1} = H(o'_{1}, m)$
Calculate each $i_{j+1} = H( O_{K_{j}}(i_{j}, s_{j}), m )$ for a randomly chosen $s_{j}$
Finally, with $i_{1} = i_{n+1}$ solve $o' = O_{K_{1}}(i_{1}, s_{1})$ for $s_{1}$

The ring signature is the sequence of $(i_{j}, s_{j})$ and is verified by checking that for a chosen $i_{j}$ a round-trip of the ring gives the starting value.
The actual construction is a little more complex. The hash includes the complete set of public keys, for example. But this should give the idea of how it works.