In a shamir secret sharing scheme, why can't the secret be a middle coefficient and only the first or the last? In the shamir secret sharing scheme, the Secret s is set as the constant in the equation

$ y_p = s+ \sum_{i=0}^{i = t-1} a_i * x_p^i$

s can only be the constant term or the last coefficient or the secret may be leaked. This is also per question below:

Coefficients in Shamir's Secret Sharing Scheme

How can I show this rigorously in a mathematical way? In the provided answer only an example is given.

Updated:

The mathematical way I currently have to show this is for the case of a (t,n) system where t = 3, sharing between two people, and y defined as

$y_1 = a_0 + s*x_1 + a_1*x_1^2$ mod P

$y_2 = a_0 + s*x_2 + a_1*x_2^2$ mod P

Then by rearranging (or by taking inverse of matrix) we have

$s = (y_2 - y_1)(x_2 - x_1) ^{-1} - a_1(x_2+x_1)$ mod P

and we get the case where S is revealed when $(x_2+x_1)$ mod P = 0.

How would we show using similar (or different) argument for t>=3, t-1 shares, that we will not have similar cases when s is the constant or the very last coefficient?

Here's one way to approach the question: if we have a $(n, t)$ Shamir secret sharing system, and we have $t-1$ shares $(x_0, y_0), (x_1, y_1), …, (x_{t-2}, y_{t-2})$, then all we can deduce that the secret polynomial is of the form:

$$P(x) + c \prod_{i=0}^{t-2}(x - x_i)$$

where $P(x)$ is a computable polynomial (exactly what that polynomial is depends on the known shares), and $c$ is an unknown constant (and which we have no information about).

So, the question is: given that the polynomial is of this form (for some $c$), and the secret we want is the $j$th coefficient, can we deduce the coefficient that's the secret we're interested in?

We know the $j$th coefficient for $P(x)$, and so this reduces to whether we know the $j$th coefficient of $c \prod_{i=0}^{t-2}(x - x_i)$; we can if and only if the $j$th coefficient of the polynomial $\prod_{i=0}^{t-2}(x - x_i)$ is 0.  If it is 0, then (no matter what $c$ is) the $j$th coefficient of the entire polynomial will be the $j$th coefficient of $P(x)$ (which we know); if it is nonzero, then (depending on what $c$ is) it could be any value.

For the linear term ($j=0$), this coefficient is $\prod_{i=0}^{t-2}-x_i$, which (because we're in a field) is nonzero if and only if all the $x_i$ values are nonzero (which they are in Shamir's scheme).

For the highest term ($j=t-2$), this coefficient turns out to be 1, hence the secret is never leaked (even if the share $x_i=0$ was issued).

For the second term ($j=1$), this coefficient turns out to be $-\sum_{i=0}^{t-2}x_i$, that is, the secret is revealed if $x_0 + x_1 + … + x_{t-2} = 0$, which (for the case $t=3$) is what you came up with.  Further note that, if we're in an even characteristic field ($1+1=0$), then $x_0 + x_1 \ne 0$ (unless $x_0 = x_1$, which cannot happen), hence in that specific case, the secret is not revealed.

Since I wrote the original answer, I found yet another corner case which is secure; if the field order is $p^z$ (that is, the field has that many elements), and if $t = p^z-1$, and the share $x_i = 0$ is not issued, then all coefficients are secure.  That's because, for any $k$ $(k$ being the share which is not revealed), we have $\prod_{i \in GF(p^z), i \ne 0, k}(x - x_i) = (x^{t} - 1) / (x - k)$, and that doesn't have any 0 coefficients.  For course, this really is a corner case, as there are only $t$ possible shares, and we need all $t$, hence this is a $(t, t)$ secret sharing scheme (and if so, why are we bothering with Shamir anyways; there are simpler methods).

Other than those cases, it is plausible for me to speculate (although I don't have proof) that for any middle coefficients, one can find a set $x_0, x_1, …, x_{t-2}$ that does leak the secret, assuming that the adversary can pick which shares he gets (which is analogous to the CPA assumption).


Authentication impossible without pre-shared public key Correct me if I am wrong, digital certificates require the user to have the public key for the certificate in their web browser, right?

Which means it has to be pre-shared.

(Say I am designing a cryptosystem which is an application for encrypted chat that uses TLS. However, I want the cryptosystem to be end-to-end, meaning, the client must directly connect to a server of their choice.

How can I make this cryptosystem's authentication work if I allow my clients to create their own servers for direct end-to-end encryption?
In other words, the application does NOT contain a pre-shared public key for the digital certificate.

In this scenario, is my application doomed without a pre-shared public key?

You dont need the public key/certificate to be present in the browser. You just need to devise a method to ensure the public key/certificate which is presented by the peer is valid. In a Web Browser scenario this is typically done by a number of known CAs which sign those certificates. But you can also ask the user to authenticate the certificate by a fingerprint or by registering it at a central directory you trust.

You can also what is called "Trust-on-First-Use" which is basically "install this cert". This has the one-time risk of a person in the middle attack. It is how SSH is used most of the time today.

You do not even need a known/verified certificate but can use instead anonymous key agreement. This has of course the big problem that each time this key exchange is done a person in the middle can spoof the server. TLS has aDH ciphers for this.

And finally you can use TLS based on a shared password as well. It depends if both parties know each other and can actually verify each other out of band or not.

If you do not have a central directory authority the most common method is to use a trust on first use setup with the additional option to manually verify the peers (this is for example also used in Whats App in addition to the weak identity proof with phone number).


If PRESENT had different permutations s would that protect it against Statistical Saturation Attack? The block cipher PRESENT is vulnerable to the Statistical Saturation Attack for up to 15 rounds (PDF) and a simple example is here.

So my questions are, if some (or all) of the permutations were changed:

would this protect it against the Statistical Saturation Attack?
if so, can we then use fewer than 31 rounds without causing a weakness against "other" attacks?

For your first question, there are two permutations in PRESENT that we could consider changing:

The nonlinear layer, i.e. a parallel application of an S-box.
The linear layer, which is a bitwise permutation.

The statistical saturation attack is not really based on the properties of the S-box, so one might not expect that replacing it helps a lot. However, the S-boxes do contribute to the overall diffusion of the block cipher, so the choice of the S-box does have an impact. The paper that you mentioned contains a detailed discussion of the influence of the S-box in Section 4 (starting on page 12). They conclude that

  It is noticeable that the PRESENT S-box is among the worst possible
  choices to resist our attack.

This is very clear from Figure 14 in Appendix D.

A better countermeasure would be to replace the bitwise permutation, as it is the cause of the vulnerability. The linear layer of PRESENT leads to other attacks as well, in particular linear cryptanalysis. For instance, Cho's Linear Cryptanalysis of Reduced-Round PRESENT is based on the limited diffusion provided by this bitwise permutation in combination with the existence of one-bit trails for the S-boxes.

The paper proposing the recent cipher GIFT contains some ideas on how to choose a good permutation in a PRESENT-like block cipher. They don't revisit the statistical saturation attack though.

For your second question (can we use less than 31 rounds), it depends a lot on what the new S-box and linear layer are. The statistical saturation attack can be stretched up to 24 rounds, see these errata and improvements for the correct complexities. Multivariate linear cryptanalysis can reach at most 26 or (maybe) 27 rounds. Replacing the bitwise permutation with a much stronger linear layer could prevent both of these attacks, but it's not possible to rule out other attacks (especially if we don't know what the replacement is).


Is there a reference that prove that the AES Key Schedule generate random looking round keys? Starting from uniformly random generated AES master key, is there a reference that prove that an specific roundkey can be considered as uniformly random generated as well ?

Actually, that's remarkably easy to show.  The AES key scheduling logic is invertible:

For AES-128, you can start at any round, take a specific setting for that round key, and invert it to come up with the unique AES key that generates that round key
For AES-192, you can start at any round, take a specific setting for that round key (and 64 bits from the previous or next round), and invert it to come up with the unique AES key that generates those round key bits
For AES-256, you can start at any round, take a specific setting for that round key (and the 128 bits from the previous or next round), and invert it to come up with the unique AES key that generates those round key bits

Because that is a 1:1 mapping because the master key, and the 128/192/256 round key bits, then if the master key is selected uniformly, so must the round key bits be.


Padding Oracle Attack with AES-128-CTR and MAC Assume Alice and Bob are communicating using 'MAC then Encrypt' paradigm.
Specifically, they are using HMAC with SHA256 as the hash function and the output is truncated to 40 bits. They are using AES-128 in CTR mode as the blockcipher. Specifically,  they do the following:

C=<IV, ENC(M II MAC(M, IV PAD) II PAD)>

I understand this. If we consider the message is 200 bits long. So the first block has 128 bits, the second block has 72 bits of the message, 40 bits of MAC and 16 bits padding. Padding scheme: 16 bits is 2 bytes (0X02). (0X0Z) for all Z bytes.

What I want to know is that if Eve has no idea that the original message is 200 bit long, but Eve knows it's 2 blocks long after 40 bit MAC was added and it is padded.

How will Eve know the length of the message? Will it be done by flipping the last bit and looking for padding error and using the padding algorithm? Or will we try padding oracle attack??

Finding the message size knowing the padding size

With CTR mode the length of the ciphertext is the same as the length of the plaintext, because what you do is XORing bit-by-bit the message with the keystream.

So the length of the second component of C minus the padding length and MAC length is the length of the message.

Quick Python example:

import os

# https://cryptography.io
from cryptography.hazmat.backends import default_backend
from cryptography.hazmat.primitives import hashes, hmac
from cryptography.hazmat.primitives.ciphers import Cipher, algorithms, modes

backend = default_backend()

M = os.urandom(200//8)
MAC_KEY = os.urandom(hashes.SHA256.digest_size)
PAD = bytes([0x02,0x02])
AES_KEY = os.urandom(32)
IV = os.urandom(16)

h = hmac.HMAC(MAC_KEY, hashes.SHA256(), backend=default_backend())
h.update(M + IV + PAD)
# truncated to 40 bits = 5 bytes
MAC = h.finalize()[:5]

cipher = Cipher(algorithms.AES(AES_KEY), modes.CTR(IV), backend=backend)
encryptor = cipher.encryptor()
C = (IV, encryptor.update(M + MAC + PAD) + encryptor.finalize())

print('length of message: %i bits' % (8*(len(C[1]) - len(PAD) - len(MAC))))
# out: length of message: 200 bits

Finding the padding size using the oracle

EDIT: added this question from comment of OP.

Another property of CTR mode is that
flipping a bit in the ciphertext flips the corresponding bit in the plaintext.

So if you flip say the last bit of C[1] you will modify the padding and get a "padding error";
while if you flip a bit that correspond to MAC you get a "MAC error".

As a result if flipping the i-th bit gives you a "MAC error"
while flipping the i+1-th bit gives you a "padding error"
then the padding starts at bit i+1 and you gets the padding length and its value.

Continuing my Python example:

class PaddingError(Exception):
    pass

class MacError(Exception):
    pass

def oracle(ctxt):
    decryptor = cipher.decryptor()
    ptxt = decryptor.update(ctxt) + decryptor.finalize()
    m = ptxt[:25]
    mac = ptxt[25:30]
    pad = ptxt[30:]

    # i'm cheating
    if pad != PAD:
        return PaddingError
    elif mac != MAC:
        return MacError
    elif m != M:
        return 'Message was modified'
    else:
        return 'OK'

def flip(x, i):
    "returns x with its i-th bit flipped (starts at 0)"
    mask = 2**(7-(i%8))
    return bytes([ x[j]^mask if j==(i//8) else x[j] for j in range(len(x)) ])

oracle(flip(C[1], len(C[1])*8-16))
# out: PaddingError

oracle(flip(C[1], len(C[1])*8-17))
# out: MacError

Finding the last byte of the MAC

EDIT added from another comment of OP

When you know the padding length, you know where is the last byte of the MAC, and because of the CTR mode you are able to modify it by XORing it against some byte of your choice.

So you pick a random byte and you XOR it against the last byte of the MAC, and you send the result to the oracle.

Normally you should get a "MAC error", but if the modified MAC byte ends up being the same as the PAD bytes (for instance 0x02 in your example) you should get a "Padding error" instead.

Let B be the byte you used to get this "Padding error", we now know that:

MAC[-1] ^ B = 0x02

(where ^ denotes bit-wise XOR as in Python)

Thus:

MAC[-1] = 0x02 ^ B


What was the first MD5 collision ever constructed? We all know that MD5's collision resistance is severly broken.

But when thinking of "random" strings with great cryptographic importance I've come up with NIST's curve seeds and MD5 collisions. But for this to really work out I'd need the most famous MD5 collision.

So I'm asking: What is the most famous MD5 collision?

As for the definition of famous: The very first published MD5 collision is considered "the most famous" with the only exception of one collision having occured a lot more often and having spread a lot more due to important historical events (Flame?) and being generally considered the most famous one.

Even though Dobbertin could not provide a real collision of MD5, I would say that Hans Dobbertin first publicly described MD5 collision(s) in "The Status of MD5 After a Recent Attack" (PDF) – that was in 1996. To the best of my knowledge he was one of the first who recommended to no longer use MD5 when collision-resistance is needed/expected/required.

On the other hand, the most famous is probably described by Xiaoyun Wang and Hongbo Yu in their paper called "How to Break MD5 and Other Hash Functions" (PDF) (Advances in Cryptology – Lecture Notes in Computer Science 3494. pp. 19–35.) which was published somewhere around 2004/2005 and the spear-head of dozens of alike papers which successively described optimized and related collision-attacks.

When you check their paper, you’ll quickly notice (page 1) that they also reference Dobbertin, which is why I think he should at least be mentioned in this context. His contribution provided the base.

From the paper by Wang and Yu:


Lower defree annihilator of function Suppose $f=x_0x_2(x_1+1)+x_1x_3(x_0+1)$, annihilator is such function $g$, so that $gf=0$ for all $x$

Intuitively solution(for some reason) is obvious - $g=x_0x_1$, which holds true. (Cloud sagemath online script)

It bugs me, that I can't explain this "intuitively". How to arrive at solution properly, not guessing?

PS: We can skip trivial solution $g=0$, function $g$ should depend on $x_n$ variables, at least some of them. Of course $\mathbb{F}_2$ is meant here.

I'm not sure if I really believe that this is of any use at attacking a stream cipher, but I'll answer your question anyways.

What $gf = 0$ means is that, for any input $x$, we have either $f=0$ or $g=0$.

Now, in the case of $g = x_0x_1$, then this $g$ will be 0 unless $x_0 = x_1 = 1$.

In that case, the first term of $f$, namely $x_0x_2(x_1+1)$ will be 0 (as $x_1+1 = 1+1 = 0$).  And, the second term of $f$, namely $x_1x_3(x_0+1)$ will be 0 (as $x_0+1 = 1+1 = 0$).

Hence, whenever $g \ne 0$, we have $f=0$, and so $gf = 0$.

This observation gives a fairly obvious way to create a nontrivial annihilator of any function $f$ (other than $f=1$ for all inputs); namely:

Find a set of inputs that give $f=0$ (technically, this is an NP-hard problem (!), but in practice is fairly easy).
Create a $g$ that is 1 for that specific input, and 0 otherwise.

For example, if $f=0$ for $x_0 = 0, x_1 = 1, x_2 = 0$, then this annihilator would be $g = (x_0 + 1)x_1(x_2 + 1)$


What paradigm does ABE, KP-ABE and CP-ABE fall into Do attribute-base encryption (abe), key policy attribute-based encryption (KP-ABE) and ciphertext attribute-based encryption (CP-ABE) fall into the attribute-based access control (ABAC) paradigm or are they not related?

This is an interesting question. ABAC itself is an access control model, and (at least should be) agnostic to how it is enforced (see some ABAC links below).   ABE-schemes, on the other hand, are cryptographic schemes, where only the terminology links them to attributes (which are, in fact, algebraic group elements mapped into real-life attributes. This mapping is scheme-dependent, and sometimes non-trivial).

However, it seems evident that the designers of ABE-schemes had the ABAC paradigm in the back of their mind, as there are many parallels. I investigated this connection more closely in my dissertation (see the last link below) in connection with RBAC (in some sense, a subset of ABAC).

Currently ABE schemes have difficulties enforcing some RBAC-standardized features, such as role hierarchy and dynamic separation of duty. Thus their support for full ABAC seems dubious. Additionally, ABAC depends on environmental attributes, and obtaining cryptographically verifiable and reliable environmental references is difficult. For example, imagine that a document is allowed to be decrypted only in a certain country. How can the encryptor control the decryption location reliably?

In summary: ABE-schemes represent an independent dimension (an enforcement paradigm) to that of access control models. Yet the current capability to support full RBAC or ABAC features is not there. Core RBAC could, in theory, be supported, though.

Links for ABAC:

NIST guide: "Guide to attribute based access control (ABAC) definition and considerations, NIST SP 800-162", http://dx.doi.org/10.6028/NIST.SP.800-162.
An ABAC dissertation: Jin, X.: "Attribute-based access control models and implementation in cloud infrastructure as a service" (University of Texas at San Antonio Dissertations), https://pdfs.semanticscholar.org/c342/d13a011460df3392815ab74fd6252187d15b.pdf

Link for a RBAC-ABE dissertation

Kiviharju M: Enforcing Role-Based Access Control with Attribute-Based Cryptography for Environments with Multi-Level Security Requirements
http://urn.fi/URN:ISBN:978-952-60-6774-2


How to find key length of a Vigenere chiper? I am trying to decrypt a Vigenere chiper, I saw a lot of youtube videos but I still can get a good value for the key length.
In theory I have to get the repetions of letters shifting the text one place every iteration and then see how many steps there are between the biggest numbers, but it gives me no common path.

First find repeating substrings, longer repeating substrings are better. Look at the differences between the index of repeating subsring pairs. Calculate GCD of the differences.  If it is a reasonable key length you probably have it. If it came out 1 try dropping some outlier spurious substring occurences. If it came out too large to be a reasonable key you may need to find more repeating substrings allow shorter substrings to be considered.

Motivation:
We expect many repeating substrings of common char-grams, in English for instance : th,the,ing and more if these appear in a difference which is a multiple of the key length the cipher text fragments will be identical as well. However such a repeating cipher text is unlikely to appear from encripting some other text in another column.


Are AES-256's related-key weaknesses exploitable if it is used to build a hash? Assume it is made a hash based on AES-256 encryption (perhaps because this is hardware-accelerated, but no standard hash is); and it is used the Merkle–Damgård structure, that is padding of the message into $n$ padded message blocks $M_i$ (appending to the message a 1, a minimal number of 0, and the 64-bit message length in bits), and a compression function per the construction of either

Davies-Meyer for a 128-bit hash with 256-bit blocks $M_i$, that is

$H_0$ is set to a 128-bit nothing-up-my-sleeves constant;
for $i$ from $0$ to $n-1$:
$\text{ }H_{i+1}=\text{AES-256}_{M_i}(H_i)\oplus H_i$
result is $H_n$;

Hirose (FSE 2006) for a 256-bit hash with 128-bit blocks $M_i$, that is

$G_0$ and $H_0$ are set to a 128-bit nothing-up-my-sleeves constants;
for $i$ from $0$ to $n-1$ (with $C$ a non-zero nothing-up-my-sleeves 128-bit constant)
$\text{ }\begin{align*}
G_{i+1}&=\text{AES-256}_{H_i||M_i}(G_i)\oplus G_i\\
H_{i+1}&=\text{AES-256}_{H_i||M_i}(G_i\oplus C)\oplus(G_i\oplus C)
\end{align*}$
result is $G_n||H_n$.

Notice that in both of these constructions, the message that the adversary can manipulate is entered in the key input of the cipher, making related-key attacks a concern.

Question: In these contexts, are any known or foreseeable AES-256 related-key weaknesses exploitable or seriously threatening?

If yes, do we have other hash constructs where AES (any size) related-key weaknesses would be less of a concern?

Note: For the 128-bit hash we expect an effort comparable to $2^{64}$ encryptions to exhibit a collision (that can be efficiently distributed, see Parallel Collision Search with Cryptanalytic Applications); and $\min(2^{128},2^{129}/n+2^{65})$ encryptions to exhibit a (second) preimage (by a generic attack on Merkle–Damgård hashes attributed to R. D. Dean in his 1999 thesis (section 5.3.1), better exposed and refined by J. Kelsey and B. Schneier in Second Preimages on n-bit Hash Functions for Much Less than 2n Work).
For the 256-bit hash we expect an effort comparable to at least $2^{128}$ encryptions to exhibit a collision, and much more to exhibit a preimage.

The most efficient related-key attacks on AES-256 and resulting weaknesses AES-256-based hash functions are summarized in my PhD thesis. Though collision and preimage attacks on hash functions are out of reach yet, the components of these functions still expose some properties that are not expected of good hash functions or random oracles.

Getting to the details, the key schedule of AES-256 allows for numerous related-key differential trails with the most probable one covering as few as 19 S-boxes (page 96) and probability $2^{-119}$. By playing with the first rounds of this trail, one can get various properties of the AES-256-based compression function
$$
F(IV,M) = AES_{M}(IV)\oplus IV
$$ holding with rather high probability.

For example, one can fix values $\Delta I$ and $\Delta M$ and produce a number of pseudo-collisions $\{(IV_i,M_i)\}$ such that  for all $i$:
$$
F(IV_i,M_i) = F(IV_i\oplus \Delta I, M_i\oplus \Delta M).
$$

It can be proved that constructing $q$ such pseudo-collisions with the same $(\Delta I,\Delta M)$ requires almost $2^{n}$ work when $q>2$, whereas for AES-256 in the Davies-Meyer mode the complexity is about  $q\cdot 2^{67}$.

Though this is not a direct threat to the full hash function, a malicious designer may select an IV to maximize the differential properties of the first round. Among nothing-up-my-sleeve values there must be some that allow for higher-probability differential trails.


SSL / TLS digital signature exchange If server is sending its digital signature, in which message / where does the digitally signature is provided to the client.

Is it after the server_hello message because there the public key of the certificate is exchanged which is needed to decrypt the digital signature or  with the initial certificate containing public key.

If cipher suite is mutually confirmed after change_cipher_spec protocol which hash algorithm is used to hash the digital signature ?

There is no separate "digital signature exchange." A certificate is a self-contained thing; it contains an "issuer" field (with a DN of the CA that signed it) and a "signature" field (with a signature from that CA). A server does not just send its certificate in the ServerCertificate message; it sends a whole chain of certificates, starting with theirs, then having their CA, then their CA's CA, and continuing to a trust root (that the server hopes the client trusts).

For DHE and ECDHE (which have signatures used in cipher parameter exchange), the signature on those parameters is part of the ServerKeyExchange message that has the parameters. Again, there is no separate signature exchange.

As for which hash algorithm to use: This doesn't actually inherently have to do with the cipher suite, as certificate signatures are an X.509 thing. The signature algorithm is also included as a mandatory certificate field. An X.509 certificate contains all the information you need to authenticate it except the Issuer's public key. Certain cipher suites don't allow certificates that aren't signed with the right algorithm, but that comes later -- you can still verify the signature as soon as you get the certificate chain.

In response to your comment: The signature verifies a certificate, not a server. The server is implicitly verified because other operations prove they have the private key corresponding to the public key in that certificate. As a separate matter, nothing is at any point encrypted with a private key; this is a popular and wrong idea of signatures. A signature algorithm takes a message (not a hash) and outputs a signature; any hashing is part of the signature algorithm.

Edit 2: Let me try explaining the certificate validation process a bit more. Here's a picture of a sample certificate chain; blue arrows are "is identical" (e.g. Issuer DN is the Subject DN of your CA), and green arrows means "generates" (i.e. by signing, which is not encrypting and you shouldn't call it encrypting):

The server presents all four of those certificates in the Server Certificate message. The client then verifies the server certificate, using the following general certificate-validation process:

If the certificate is identical to something in the preset list of "trusted certificates" (e.g. a trusted root CA cert, or if you've manually added a trusted root certificate), then accept the certificate. If it's not and this is the last certificate in the chain, reject it (you don't trust whoever verified it).
If not, check that the certificate isn't expired and that the date it starts being valid isn't in the future (these are attributes I didn't show).
Check the Issuer, the signature algorithm, and the signature on the certificate. If there's a next cert in the list of certs you received, verify that that certificate's Subject DN is this one's Issuer DN.
Using the public key from the next certificate and the signature algorithm from this certificate, verify the signature on this certificate.
Verify that the next certificate has the CA attribute.
Validate the next certificate down the line using this same process.

If any of steps 2-6 fail, reject the certificate. This is all done using only the information in the Server Certificate message, which contains the full chain of certificates (OK, so technically you can leave out the self-signed root CA and the TLS client will check its trust root for a cert with the appropriate Subject DN, but that's a minor detail). At the end, you know that the server cert is the start of a chain of certs, each signed by the next one, where the last one is one you inherently trust (it's a root CA). There is no separate signature exchange; these signatures are part of the certificates.


When NIST put together the table A.1, they accidentally used a 96 character alphabet for that last column, not a 94 character one.  One way to see this is looking at the bottom most entry; they list that $log_2(b^{40}) \approx 263.4$, where $b$ is the alphabet size they used.  If we solve for $b$, we get $b \approx 96.002...$.


Asymmetric keys (e.g. RSA) must be so much longer than symmetric keys (e.g. AES). Why? I have been reading that RSA has to do with math (prime numbers), while symmetric key encryption deals with blocks of data and modifying the blocks with replacements and remappings, but I still don't understand why asymmetric encryption has to have longer keys because of that, or whether that's even the reason.

Asymmetric algorithms

Asymmetric algorithms rely on mathematical structure. Keys for asymmetric algorithms typically have some kind of structure, as opposed to being uniformly random bit strings. This structure can be exploited to reduce the cost of breaking the system.

Additionally, with asymmetric cryptography, there is more information to work with; The public key has some known relation to the private key, and everyone has the public key. This is in addition to the usual information that you might have from what the system is used for, e.g. plaintext-ciphertext pairs or message-signature pairs.

Symmetric algorithms

Keys for symmetric algorithms do not have structure - They are simply a uniformly random block of bits.

Other than plaintext-ciphertext pairs, you typically do not have any more information about the key. The relation of the key to the bits of the plaintext/ciphertext are extremely complex with no regular or helpful structure to speak of.

Of course, you could have a cipher with a 256-bit key that is vulnerable to an attack that recovers the key in negligible time from a single ciphertext.

Key size

Key size isn't really what is relevant. What is important is the cost of the best attack to break the system.

With a strong symmetric algorithm, the best attack will be brute force guessing the key. So the size of the key more or less directly controls the cost of the best attack against the system.

The structure used by asymmetric algorithms typically results in the existence of attacks better than brute force guessing the key. So the key size has to be increased to compensate. This is visible in RSA as each prime $p, q$ is much much larger than the size required to prevent brute force guessing; Brute force guessing is not the best attack, so the keys are not scaled against the cost estimate that brute force would have.

Note

The above are generalizations that are only approximately true - it is possible to design symmetric algorithms that have structure - But those are not what people usually mean when they say "symmetric encryption".

Additionally, it's also possible to generate at random an AES key that happens to be the product of two somewhat sizable primes; But that won't tend to help cryptanalysis of AES much because that structure doesn't appear to be helpful.


Finding max period of 8-bit LFSR I am a bit stuck there and trying to figure out the approach for given problem.

What is the maximim period of a pseudo-random sequence generated by the
8-bit LFSR with connection polynomial C(X) = 1+X^2 +X^4 +X^5 +X^6 +X^7 +X^8?

Any help would be highly apreciated...

If a connection polynomial of degree $d$ is primitive, i.e., it is irreducible and has a root of order $2^d-1,$ then the period is $2^d-1,$ for any nonzero loading.

There is more information in answer


Base64 with shuffled alphabet I have a base64 'cipher' text. I know that in clear text is a hidden XML document (I know nothing about its structure), but the base64 alphabet was somehow shuffled. Is there any smart way, how to detect the modified alphabet better than checking all 64! permutations? I can slightly reduce the number of permutations by using the knowledge that XML document starts (without doctype, just root element) with opening tag (character '<') and ends with '>'. But there are still 62! permutations which are still not computable.

I have also tried to infer some other characters, but as the tags may be arbitrarily long and the content may be any character, I don't see much space for frequency analysis.

A well-formed XML document is subject to all sorts of constraints.

You can incorporate these constraints into a function that checks a base64 substitution key by looking for invalid syntax, such as improperly nested tags, or a tag name containing control characters, white space, or any of the characters !"#$%&'()*+,/;<=>?@[\]^`{|}~, or that starts with a dot, hyphen or numeral.

Combine this with a backtracking search algorithm, and with a bit of luck you should obtain a solution within a reasonable amount of time.

If it turns out to be too slow, there are other assumptions you could make. For example, most XML documents use only printable ASCII characters in their tag names, and often contain white space after closing tags.


Expandable hash function I have been studying a cryptosystem using Mersenne primes. More specifically, this paper: https://eprint.iacr.org/2017/481.pdf
I have implemented this cryptosystem in python but I am missing the key encapsulation system.
In page 12, they refer to something known as "expandable hash function". It should take as input a $\lambda$-bit string and output an uniformly random $n$-bit string ($\lambda<<n$) of Hamming weight $h$. This weight $h$ is already determined (actually $h=\lambda$).
I am kind of new to this stuff. Is there a way to implement this hash function in python? Many thanks in advance.

Remember: a random permutation (aka "a hamming-weight-preserving one-way function") is known in layman's terms as a shuffle; there are trivially correct algorithms to do this; Python itself, though, makes it quite convenient to just leverage its shuffle implementation by subclassing Random with your choice of deterministic CSPRNG:
from Crypto.Hash import SHAKE256
from random import Random

def deterministic_shuffle(seq, key, alg=SHAKE256):
    """Applies a hamming-weight-preserving random permutation to seq"""
    SpongeBasedRandom(key, alg.new).shuffle(seq)

class SpongeBasedRandom(Random):
    def __init__(self, seed, spongefactory):
        super().__init__()
        self._sponge = spongefactory(seed)
    def getrandbits(self, k):
        n = -(-k // 8)
        # FIXME: squeezes-and-then-wastes k % 8 bits -- Is that
        # a security issue?
        # It'd take about +5 or +6 SLOC to patch it, just dunno if
        # it'd be worth it to bother
        return int.from_bytes(self._sponge.read(n), 'little') & (2 ** k - 1)
    def randbytes(self, n):
        return self._sponge.read(n)

k = b'Hyper Secret Input Key'
h = len(k) * 8
n = 4096
assert n > (8 * h)

bitstream = ([1] * h) + ([0] * (n - h))
deterministic_shuffle(bitstream, k)

print(bitstream)


If pseudorandom functions (PRFs) are deterministic in nature, how can encryption schemes using PRF be CPA secure? I am new to crytography. Can anybody tell me what I might be missing here?

The common way is to use a PRF for encryption is the CTR mode which is introduced by Whitfield Diffie and Martin Hellman in 1979;

Privacy and Authentication: An Introduction to Cryptography as an invited paper on Proceedings of the IEEE, 67 (1979), pp. 397–427.

This is a must-read paper that provides insight into the cryptography during 1970s. CTR mode doesn't need a PRP it can be work with a PRF and actually have better security bounds with the PFF( PRF-PRP switching lemma). To use the CTR mode with a PRF;

Choose a uniform random key on a key $k$

Choose a uniform random nonce ( counter-based are ok)

Generate the keystream $s_i$ as
$$s_i = PRF(key,nonce,i)$$

Encrypt the plaintext bit $p_i$ as $$c_i = p_i \oplus s_i$$

Like everything in cryptography, the CTR mode has advantages and disadvantages and the golden rule never uses an $(IV,key)$ pair again.
A well-known example is the ChaCha20 stream cipher based on the presumed ChaCha20 PRF.
CTR mode is CPA secure. To show the CPA security we need to play the Ind-CPA game.

Set the security parameter $1^n$
Call $Gen(1^n)$ to generate a key $k$
Provide $1^n$ to the adversary and Oracle Access to $E_k(\cdot)$
The adversary outputs the message $m_1$ and $m_2$ of the same length
Uniformly select a bit $b$ and send the ciphertext $c = E_k(m_b)$.
Adversary continue to using the oracle
Adversary outputcal_ $b'$
If $b=b'$ then output 1, else output 0.

Then, a scheme $\pi$ ( here CTR) is said to have Ind-CPA if
$$\Pr\left[ \operatorname{PrivK}^{CPA}_{\mathcal{A},\pi}\right] \leq \frac{1}{2} + \operatorname{negl}(n)$$
The proof is long to write here. See the Theorem 3.33 on the 3rd edition of Introduction to Modern Cryptography by Jonathan Katz and Yehuda Lindell
CTR mode is malleable, i.e. it cannot achieve CCA security. For this either use it together with a MAC like HMAC or use it in Authenticated Encryption mode fashion.

If pseudorandom functions (PRFs) are deterministic in nature, how can encryption schemes using PRF be CPA secure?

Yes, they are deterministic, however, the way we use them for encryption and decryption is probabilistic encryption. This is achieved even with the fixed key by using an IV/nonce per message. This is the sole reason that the advantage of the adversary is negligible.


Does Ed25519 support cryptographic threshold signatures? This is a loaded question so I'll list the concerns, not all of which need to be satisfied.

Does there exist a threshold-signature scheme for Ed25519 that...

Does not require a trusted dealer to set up the key shares (required)
Does not require interaction to set up the key shares (optional: ideally users can independently generate key pairs, but if all n users need to interact to compute the key shares, that's acceptable)
Supports arbitrary m-of-n composition, as opposed to having restrictions on m (required)
Does not require interaction to reconstruct the threshold signature from signature shares  (optional: same as 2, non-interative schemes are preferred)

Some sources claim that this is possible (e.g. https://ripple.com/curves-with-a-twist/) but I haven't seen an implementation yet.

Threshold (robust) m-of-n variant of Schnorr signature scheme is known:

Douglas R. Stinson, Reto Strobl - Provably Secure Distributed Schnorr Signatures and a (t, n) Threshold Scheme for Implicit Certificates

Major hints on intended usage are from Ripple page mentioned. Points 4 and 3 are explicit: produce a signature, in a theshold m-of-n way. This could be solved with Shamir scheme (interpolation) for Schnorr signature, namely re-construct response s from shares of k and x (wikipedia notations). No trusted dealer is straightforward for Schnorr scheme while choosing x and k, to meet points 1 and 2.

Schnorr scheme admits efficient verifiable threshold variant without any trusted dealer (like while signing key generation). Efficient means combining partial signatures needs just a single interpolation for a known linear combination of secrets (that is, signing key and k) and another interpolation for random group element gk. Verifiable means any error (like misbehaving participant) will be detected. Threshold means any m honest participants will produce a signature. At last, "threshold" signature is verifiable as usual one, the same equation.

Let me refer to "High-speed high-security signatures", section "The signature system", subsection "EdDSA keys and signatures". Verification equation is similar to Schnorr scheme, with multiplier 8; signature is response S, initial random r, random group element R, actual secret a. It fits well. Ok, we have "-" sign while calculating response with original Schnorr scheme.


DSA signature computation Reading through the DSA signature specification, one thing stood out for me.

$r = (g^k \bmod{p} ) \bmod{q}$

Then $s$ is computed. In the computation above, why is the modulo $p$ required, given we are anyway reducing it with a modulo $q$?

To clarify, just doing a modulo $q$ will achieve the result of reducing the number to within the bounds of q. Doing a modulo $p$ seems like an extra step and that indicates that a simple reduction of the number to the bounds q is not the only objective. Why is modulo $p$ needed, cryptographically speaking?

The way you should think of it is not as $(g^k \bmod p) \bmod q$ but as computing exponentiation by the integer $k$ of the order-$q$ element $g$ of the group $G = (\mathbb Z/p\mathbb Z)^\times$—which happens to be the multiplicative group of units modulo $p$ and to correspond to reducing the integer $g^k$ modulo $p$—and then randomly projecting that onto $\mathbb Z/q\mathbb Z$.  But for security it is sufficient to work with some more or less evenly distributed function from $G$ into the group $\mathbb Z/q\mathbb Z$ of exponents of $g$ (recall $g$ has order $q$), and the map $h \mapsto h \bmod q$ seems to work well enough as such a function.

In more detail:
The general form of (EC)DSA is the following structure:

Parameters:

Group $G$ in which discrete logs are hard.
Element $g \in G$ of large prime order $q$.
Random function $H\colon \{0,1\}^* \to \mathbb Z/q\mathbb Z$.
More or less evenly distributed function $F\colon G \to \mathbb Z/q\mathbb Z$.

Public key: Element $y \in G$.
Verification: A signature on a message $m$ is a pair of exponents $r, s \in \mathbb Z/q\mathbb Z$ satisfying the equation $$r = F(g^{H(m) \cdot s^{-1}} y^{r s^{-1}}).$$
Key generation: Pick uniform random $x \in \mathbb Z/q\mathbb Z$; public key is $y = g^x$.
Signing: Pick $k \in \mathbb Z/q\mathbb Z$ uniformly at random (reject $0$ and $1$ if you're a stick in the mud); compute $r = F(g^k)$ (reject $0$ if you're a stick in the mud) and $s = k^{-1} (H(m) + x r)$.

For DSA, we have $G = (\mathbb Z/p\mathbb Z)^\times$ and $F\colon h \mapsto h \bmod q$ (taking $h$ to be its least nonnegative residue modulo $p$).  For ECDSA, we replace the exponentiation $g^x$ for integer $g$ by the scalar multiplication $[x]B$ for curve point $B$, so we have $G = E(k)$, the $k$-rational points of some curve $E$ over a field $k$, and $F\colon P \mapsto x(P) \bmod q$.  And, as an additional tweak, in the signature for ECDSA we encode $x(P)$ instead of $F(P) = x(P) \bmod q$, because by Hasse's theorem $\#k \approx q$ (as long as the cofactor is small; for the curves typically used in ECDSA, it's usually 1), so unlike in finite-field DSA the additional reduction modulo $q$ for encoding the signature doesn't save much space.

If the choice of $F$ feels like it's all very arbitrary, you would be right.  (EC)DSA was a wacky bizarro design motivated mainly by a desire to avoid a patent-wielding Claus Schnorr in the early '90s, and nobody would care about this nonsense any more except (EC)DSA has now been carved into the stone of bureaucratic United States federal government standards standards that nobody in the Western world ever got fired for following.


Will I be able to (ab)use a FIDO U2F compliant hardware token to decrypt data? I have heard good things about the emerging "FIDO U2F" standard. I am especially interested in having a JavaScript API for cryptographic functions that I can access through a plug-in in a browser.

However, so far all my efforts to obtaining a physical hardware token supporting the FIDO U2F specs for testing were without success.

What I would be particularly interested in, is decrypting short messages with the app_id specific private key stored in the device through a JavaScript call.

While the "FIDO U2F" Javascript API draft doesn't mention a method for this, I wonder whether I could use a simple sign request and simply provide the data to be decrypted as websafe-base64-encoded challenge?
In my understanding, the response returned from the device would be the decrypted challenge.

Am I correct with this or do I misunderstand the way challenge/response is implemented here?

No, you will not be ble to abuse challenges in that way. You may be thinking about e.g. raw RSA, where signing and decryption are mathematically similar. However, this is not possible in FIDO U2F:

All the defined signature algorithms use SHA256 on the signed data, meaning that you'd have to brute force search for something that produces the correct signature.
Not all the hashed/signed data is controlled or even necessarily known by the server. E.g. the signer has an incrementing counter that's part of the signed data.


What does $\text{PK}=\text{pk}\oplus\text{H}(\text{opk})$ represent in this paper? In Lu, Au and Zhang's 2019 paper (Linkable) Ring Signature from Hash-Then-One-Way Signature, they

…extend [M. Abe, M. Ohkubo, and K. Suzuki's 2019 1-out-of-n signatures from a variety of keys] framework to its linkable variant. Borrowing the idea from [our previous lattice-based linkable ring signature scheme, Raptor], we adopt [some] one-time signature scheme ($\Pi^{OTS}$). We build a generic method of constructing linkable ring signature based on $\Pi^{OTS}$ and $\text{Type-H}$ signature with uniform distributed public key. During the key generation procedure, in addition to the public key and secret key pair $(\text{pk},\text{sk})$, each signer also generates a pair of public key and secret key $(\text{opk},\text{osk})$ of a one-time signature. The signer then computes $\text{PK}=\text{pk}\oplus\text{H}(\text{opk})$ for some appropriate hash function $\text{H}(\cdot)$. The new public key is $\text{PK}$ and the secret key is $\text{SK}=(\text{sk},\text{opk},\text{osk})$.

I take it (perhaps incorrectly in this case) that this symbol, $\oplus$, in that second-to-last equation represents exclusive-or, but how is that implemented here?
They explicitly list RSA as a supported $\text{Type-H}$ signature scheme to underly this linkable ring signature scheme, but this leaves two large questions:

how does one use an RSA public key $\text{pk}$, which is an ordered sequence of two integers, one of which is at least 1024 bits, as an argument to XOR with the output of a hash function such as SHA256, which is merely 256 bits?

How would you interpret the (identically random) result of an XOR with a cryptographic hash digest back into such a particularly constrained sequence of integers as RSA public key $\text{PK}$? (i.e. the first one must be the product of exactly two primes; the second should be less than around 1024 bits) -- and then how would you ensure that $\text{SK}$ comprised its factors?

$\text{PK}_\text{RSA}=\text{pk}_\text{RSA}\oplus\text{SHA-2}_{256}\left(\_\right)$
^ This seems so impossible and ridiculous (despite the authors of this paper listing RSA explicitly as a supported algorithm, and SHA256 being practically "the" standard cryptographic hash) that I am sure I'm misinterpreting something — probably the $\oplus$ symbol, though I cannot fathom what it might mean instead — so, what is represented in that line? Am I misinterpreting what $\text{PK}$ represents?
For instance, how would I, "mechanically", (in, say, pycryptodome) enact or implement this line, if we take SHA256 as $\text{H}$, RSA as the $\text{Type-H}$ signature scheme, and (say) Lamport signatures as $\Pi^{OTS}$?

Reading section III A of the paper (caveat, I've not read the whole paper), it looks like the construction has been generalised so that $H$ maps to the abelian group where the public key operations take place. As such the $\oplus$ operation generalises to the abelian group operation. This notation is unwelcome, but I think in previous work the abelian group in question did combine with XOR.
In the RSA case it would appear that the operation is multiplication modulo $N$ and the hash function maps to $\mathbb Z/N\mathbb Z$.


El Gamal special construction The algorithm:

I have to determine if the following algorithm is secure:

$p,q \in \mathbb{P}$

and

$N = p \cdot q$

$e \in [2, N - 1]$ such that $\gcd(e, N) = 1$

$r_1, r_2$ are random numbers in the range $[2, N - 1]$

$a_1 \equiv e^{r_1(p-1)} \pmod N$
$a_2 \equiv e^{r_2(q-1)} \pmod N$

The public key is $(N, a_1, a_2)$ and the private key $(p, q, r_1, r_2)$

We encrypt a message $m$ as follow:

We take two random integers $s_1$ and $s_2$ in the range $[2, N - 1]$

$d_1 \equiv {a_1}^{s_1} \pmod N$
$d_2 \equiv {a_1}^{s_2} \pmod N$

Then we compute:

$c_1 \equiv m \cdot d_1 \pmod N$
$c_2 \equiv m \cdot d_2 \pmod N$

$(c_1, c_2)$ is the cipher text.

How to recover the message $m$ without the private key?

What I tried:

First, we can decrypt a message (with private key) by using Fermat's Little Theorem.

I tried to compute $\gcd(c_1 + i \cdot N, c_2 + i \cdot N)$ as usually $d_1$ and $d_2$ are coprime.
I found that we can have a linear relation between $a_1$ and $a_2$ (i.e. $\exists k \ a_2 \equiv ka_1 \pmod N$) same for $c_1$ and $c_2$

Since $a_1 = e^{r_1(p-1)} \bmod N$ and since $p$ divides $N$, it follows that $a_1 \equiv e^{r_1(p-1)} \equiv 1 \pmod p$.  We so have $a_1 - 1 \equiv 0 \pmod p$ or, equivalently, $a_1-1$ is a multiple of $p$.  In turn, this implies (with overwhelming probability) that $\gcd(a_1-1,N) = p$ and thus $q =N/p$.

Since $d_1 \equiv {a_1}^{s_1} \equiv 1 \pmod p$ and similarly since $d_2 \equiv 1 \pmod q$, message $m$ can be recovered as $\operatorname{CRT}(c_1 \bmod p, c_2 \bmod q)$, using the values of $p$ and $q$ as obtained above.


How big are the primes used in modern cryptography? I know that this depends on which techniques you're using, but roughly speaking, when modern cryptography makes use of so-called "large prime numbers", how large (in bits or digits) are these primes typically?

For example, recent versions of OpenSSH typically use either

ECDSA with a curve size of 256, 384, or 521 bits, which requires a prime of the same size, give or take a couple bits, or
RSA with a key size of 1024, 2048, or 4096 bits, which requires two (distinct) primes of half the key size (e.g., a 2048-bit RSA key requires two distinct 1024-bit primes).

The reason for the difference in size is that RSA can be broken significantly faster than by brute force, which means it requires larger keys to achieve the same level of security.


Is SpookyHash vulnerable to HashDoS? Aumasson, Bernstein and Bosslet did an excellent job demonstrating fatal weaknesses in MurmurHash and CityHash, but what about SpookyHash?

My first uneducated guess is that it would be much harder to create collisions, but not impossible.

My second uneducated guess is that it would be impossible to create the massive kind of multi-collisions required for a HashDoS. That is, an attacker could possibly create two or three messages that hash to the same value regardless of the seed, but not hundreds or thousands. And since a moderate amount of collisions are expected anyway in any hash table and cared for, the attack would fail.

Am I correct about that? If not, would it help to mix the seed repeatedly
into the state, like here?

Jean-Philippe Aumasson (the principal author of SipHash) has kindly
answered my question by email and acknowledges that he is unaware of
an efficient HashDoS attack against SpookyHash. This does not imply that
no such attack exists, only that he was unable to find one rapidly.


My pencil and paper One Time Pad works fine without modular math ...... or does it? With no background in higher math or computer science, I could not quite grasp the value of modular math for simple OTP systems as described in other posts here.

I have an alphabet size of 40 characters, valued from 0 to 39.
The pad uses alphabetics "A" through "Z", valued from 0 to 25.
I am using modulo 40 math.

If my ciphertext for any given plaintext character is a single digit, I prepend a zero as a placeholder, this yields a consistent ciphertext of a pair of digits for any one character of plaintext.

This system is working just fine.
But then I realized that I could skip the mod math entirely and the system works just as well and is easier and quicker for both parties in the exchange....as far as I can tell.

So: Why bother using the mod math at all if the encryption/decryption is working just fine without it?

And, from an attacker's point of view, if he realized the ciphertext digit pairing and therefore could see the highest pair value of 40  (in the case of using the mod math)  or instead  64 (without the mod math), would one of those cases give him more advantage than the other?

If you are not using modular arithmetic and an eavesdropper observes the ciphertext 64, they immediately know that the plaintext is 39 (encrypted with the key 25). With modular arithmetic, if the ciphertext 39 is observed, the plaintext can range from 14 (with key 25) to 39 (with key 0).

Note also that, since in your system the key space is smaller than the plaintext space, it is not perfectly secret even if you use modular arithmetic. As above, a ciphertext of 39 ensures the plaintext is between 14 and 39, not below (there is no key that encrypts 13 to 39).


What is the proper way to use a client nonce? I've implemented an API for one of my clients, it relies on nonces and a shared secret. The structure:

Client's Site (CS) requests nonce from My App (MA), posting their username
MA verifies the username is valid, then generates a nonce in response

The nonce is only valid for the given username and is only valid for 1 minute.

CS uses the nonce to make a userful API call; the post looks like this:

username, nonce (from step 2), cnonce (Generated by CS), payload (Useful API call), and hash Which is a sha1 hash of the nonce, payload, shared secret, and the client nonce.

MA confirms that the nonce is valid for the given username (and then invalidates the nonce for future use), and then uses the shared secret for the given username along with the nonce and provided client nonce to hash the payload and confirm the hash matches the given hash.

If it matches, it executes the API call specified in the payload.

My question: Am I using the idea of a cnonce correctly? I'm having a hard time seeing its usefulness.

The client nonce is there to protect the client against a replay attack. Without the client nonce, an attacker could intercept the initial request for a nonce by CS, and respond with an old nonce that the server used previously. Then, the client would use that old nonce and make an API call with it, which the attacker would again intercept, and the attacker would send back the response that the true server had actually sent when the nonce was first used. To sum up, the replay attack is about making the client interact with an old ghost of the server. The client nonce allows the client to make sure that he is talking with a "fresh and alive" server.

A client nonce would not be needed if the client had a local memory large enough to recall all previously used nonces -- the kind of memory which resists across reboots, and can store all nonces for the whole duration of the shared secret life. That's rarely practical.


Self-Convergent Hashing What is the name of an algorithm that hashes its result as an embed of larger set of data that results back to the hash?

For instance where $f(x)$ is the hashed result and $x$ is the dataset, and $f(x)=foobar, \\
x={\dots foobar \dots}$

Differently stated: I'm interested in a hashing algorithm that generates a hash code of a dataset with the actual hash value as a subset of the dataset. (If the algorithm doesn't exist, I propose it be named to the GEB hash.)

Maybe a "hands-on" application would help: A barcode embedded in raster graphic.  The barcode signifies the value of the hash code but the hash of the graphic as a whole (barcode too) renders the result value of the barcode.

A more abstract approach is embedding as a pre- or post-output sort of header in the same encoding...

My interest is in ensuring data completeness or cripple else.  No rogue data here--just can't cut off the hash off the end.  In above f(x) example, the dataset would/could be of the abstracted form $$x= {.... oo..b....fa...r}$$  It's interesting in the balance between having a algorithm that's substantive enough in influence/design of the 'original' and yet is not namely obtrusive.  In the world of say books, I would imagine "parity" bits contributing the hash hidden on the edge fonts, sans stenography meets authentication and validation.

In principal, the "hash sentence" in the book would be hashed itself to monitor data tampering in an insulated environment. ie. can't readily look up the hash code from another "verified source" but I can recognize the "thumbs up" image and so can my "compiler".

What you are describing sounds something like a Merkle Tree:
https://en.m.wikipedia.org/wiki/Merkle_tree

Note that the organization of a Merkle tree is fairly arbitrary; the graph can look like just about anything so long as it is acyclic.

The interesting aspect of a Merkle tree is that any change anywhere in the data "bubbles up" the tree to the root, changing the hash value stored there. But there is no requirement to re-hash all of the data in the tree on every change.


Why is the signatureAlgorithm field in X.509 certificates redundant? See the ASN.1 description of an X.509 certificate below:

Certificate ::= SEQUENCE {
    tbsCertificate      TBSCertificate ({ x509_note_tbs_certificate }),
    signatureAlgorithm  AlgorithmIdentifier,
    signature       BIT STRING ({ x509_note_signature })
}

TBSCertificate ::= SEQUENCE {
    version           [ 0 ] Version DEFAULT,
    serialNumber        CertificateSerialNumber ({ x509_note_serial }),
    signature       AlgorithmIdentifier ({ x509_note_pkey_algo }),
    issuer          Name ({ x509_note_issuer }),
    validity        Validity,
    subject         Name ({ x509_note_subject }),
    subjectPublicKeyInfo    SubjectPublicKeyInfo,
    issuerUniqueID    [ 1 ] IMPLICIT UniqueIdentifier OPTIONAL,
    subjectUniqueID   [ 2 ] IMPLICIT UniqueIdentifier OPTIONAL,
    extensions        [ 3 ] Extensions OPTIONAL
}

What's the difference between Certificate.signatureAlgorithm and TBSCertificate.signature?

They appear to have the same value, and Certificate already includes a TBSCertificate in it, so one of the values is redundant.

Why is it included then?

From RFC 5280 r.e TBSCertificate.signature

  This field contains the algorithm identifier for the algorithm used
     by the CA to sign the certificate.

  This field MUST contain the same algorithm identifier as the
     signatureAlgorithm field in the sequence Certificate (Section 4.1.1.2).

I think it's because the authoritative signature is on the contents of TBSCertificate. If the signature algorithm used by the CA weren't included in the certificate to be signed then maybe one could change the Certificate.signatureAlgorithm field to something more amenable to a would-be adversary.

A similar answer has been given before on security.SE


Do hand-based hash functions / MACs exist? Is there research on a hash function or a MAC that can be executed without computers?

I know there's a lot of history on hand-based ciphers and the OTP can easily be excecuted by hand. (By using numbers / letters) But modern cryptography requires authentication as well as encryption.

Now I'm asking myself, is there a (simple) well-studied hash function or a similar MAC that can be executed by hand and operates on letters rather than bits?

Reformulation: Is there a "classical" analogon for hash functions to the classical ciphers.

Note: Resistance against computer-based attacks isn't a neccessary requirement (just like classical ciphers do not resist such attacks).

It depends on the time you want to spend. But most likely, there is nothing with reasonable efficiency. For arithmetic operations, humans are really bad compared to computers, and the difference is at least a factor of $10.000.000$ (very very rough guess, probably even 1+ additional zeros there).

So, since you have to assume that the attacker has access to a computer and will use it, you will have to use a modern scheme and consider classical ones broken.

Anyway, for security in a modern sense, you need a modern scheme, and those require modern tools like computers to achieve any reasonable performance. Of course you can calculate SHA256 by hand... but it will probably take you hours to go through all rounds for a single hash value.

Considering your remark about letters instead of bits: Mostly that is just interpretation, but there is also format-preserving encryption (there are quite a few questions on that on cryptoSE), which operates on arbitrary sets of symbols. If you want to transfer this into a hash fucntion, see this question.

Hash functions in the classic crypto-era?

At the time when classic ciphers were created, cryptography was (as far as I can tell) almost only looking at encryption methods. The idea of hash functions - or its ideal counter part the one-way function - might have been known, but not its range of application. E.g. integrity was not much of a concern: Someone without the key couldn't possibly modify a message in a meaningful way. Other applications of hash functions might seem trivial these days, but as always: developing something new and understanding something in hindsight is entirely different.

I doubt there is a genuine classical hash function.


Why did TLS 1.3 prohibit PGP authentication? There is a specification, in Informational(!) RFC 6091, for using PGP keys in TLS authentication, although I don’t think it has ever been implemented outside of GnuTLS (it’s certainly not in OpenSSL).

Yet the TLS 1.3 RFC 8446 §4.4.2 goes as far as to specifically prohibit this obscure extension with a must not. Normally an IETF document would use a should not to recommend against something that’s not fundamentally broken, but still a bad idea in most cases; and RFC 6091 doesn’t seem broken—it just provokes pointless bloat (given the current state of client support and PGP deployment).

What’s the point of such strong language?

It seems that PGP certificates have the problem that they can be changed by the user. Furthermore, there were extensions for 1.2 that are incompatible for 1.3 (if they were secure in the first place):

I found this on the TLS mailing list from Ilari Liusvaara:

  Ugh, the situation is way worse than what I thought.

  Basically, all three assume they have full control of certificate
  message, worst of all being OpenPGP, which modifies it in more complex
  ways (it isn't a pure element or list anymore).

  And even with RPK, which appiles least severe modifications, still
  modifies the structure in ways that are not obvious in implications
  w.r.t. TLS 1.3.

  Oh, and turns out I had implemented RPK in TLS 1.2 wrong by assuming
  that it doesn't actually modify the certificate message format. Which
  turned out to be wrong assumption (I fixed this after discovering the
  format changes).

  And then certificate types don't currently work sanely for client
  certs, even if you knew how those map to Certificate message.

  Client_certificate_type and server_certificate type aren't the only
  problematic extensions w.r.t. TLS 1.3. The table of extensions has the
  following too (all marked as allowed, I added short reason I think
  those are problematic):

  client_certificate_url: Replaces certificate message. Hardcodes   SHA-1 (which is now provably broken).
  user_mapping: Has extra handshake message.
  cert_type: All the problems of CCertT and SCertT, combined with   fixing both to be the same.

  With user_mapping, applying similar trick as in status_request is not
  completely trivial because extensions that are answered in client
  Certificate are offered in CertificateRequest. Okay, except that
  extension is not an answer to ClientHello extensions, and the
  extension assumes offer-answer relationship between client and server
  extensions. Might need some special-casing.

  ...

Source: https://www.ietf.org/mail-archive/web/tls/current/msg22576.html

In other messages in the thread they talk about disabling OpenPGP until somebody comes up with an extension in a separate RFC. So it doesn't seem to be malice, just a whole bunch of compatibility reasons. In other words: as it is now it looks very broken - until somebody manages to fix it.


What's the advantage of using OFB/CFB/CTR modes over a stream cipher As far as I understand:

The primary disadvantage associated with stream ciphers is the need for a random and unique key for each run in order to protect against reused-key attacks.
OFB/CFB/CTR block cipher modes turn the cipher into a stream cipher. Again, the IV/nonce should be random and unique.

What's the advantage of using the aforementioned block cipher modes over using a regular stream cipher (even though the latter would probably be faster)?

There is no real advantage, other than the fact that it allows you to convert a block cipher into a stream cipher securely.  Since there has been a large amount of research put into block ciphers and ciphers such as AES are commonly implemented in hardware (such as AES-NI), it allows for reuse of the primitives.

Side note: the nonce generally does not need to be random to be secure, it just needs to be unique.  Since it will be irreversibly and unpredictably permuted by the block cipher it can be predictable unlike an IV, but a nonce reuse is significantly more devastating than an IV reuse.


Why doesn't this operation reveal the voter's message? I am working my way through this paper. I am trying to figure out the OR zero knowledge proof in figure 2. The prover is verifying that she has correctly voted, and that her input satisfies
$$\log_gx=\log_h{(y/m_0)} \wedge \log_gx=\log_h{(y/m_1)}$$
The authors' protocol for this makes sense except for one thing. After the prover receives the challenge $c$, she sets $d_2 \leftarrow c - d_1$ if her vote is 1, or $d_1 \leftarrow c - d_1$ if her vote is -1. Because $c \in_R \mathbb{Z}$ and the previously set $d$ is also $\in_R \mathbb{Z}$, the new $d$ could be negative.

However, in the final step, the verifier needs to compute two values to the power of each $d$. This means the prover can't simply send $d \mod p$, and must send $d$ even if it is negative. But the other $d$ value will never be negative.

Doesn't this mean that verifier can learn the prover's vote? If $d_2$ is negative then she voted 1, or if $d_1$ is negative then she voted -1.

What am I missing?

I figured it out, it's quite simple actually.

The $d$ values (and $r$ values) are all exponents and chosen from $\mathbb{Z}_q$. Thus all calculations on them directly take place in $\mathbb{Z}_q$. Applying mod $q$ (not mod $p$) to all of my calculations on $d$ and $r$ fixed any problems with calculations.


How do unkeyed hash functions (for MDCs) provide security? Unkeyed hash functions are, by definition, hash functions computed without a key. SHA-1 is an example. MDCs (message digest codes) are a subclass of unkeyed hash functions. How are unkeyed hash functions secure, when the message is encrypted with a known, open hash function and without a key?

Your question is ill-posed; to determine whether they provide "security", we need a specification of what you mean by security.

So I'll answer about just one potential use of hash functions:

Are you thinking about using hashing together with encryption to try to protect the integrity of the message against tampering?  If so, generally speaking, unkeyed hash functions do not provide security against tampering with the message.  You should not use them for message authentication or integrity protection.

(Some people used to recommend appending an unkeyed hash of the message to the end of the message, and then encrypting, in hopes that this would prevent tampering with the message.  They called the hash function a "MDC".  We now understand that this construction is not secure.  Therefore, you should not use this approach.)

Instead, you should use either authenticated encryption or use a message authentication code (MAC).  Both constructs are keyed functions.

If this is not what you were asking -- or even if it was -- you need to revise your question to clarify what you mean by "security".  Security against what threats?


Big-O Encryption Algorithm I am currently doing a research paper on the Blowfish encryption algorithm and one of the components that I need to include is time and space complexity.

I have tried reading academic articles and journals, but they have the complexity in the matter of kilobytes.

Would anyone have an idea on what is the time and space complexity of the Blowfish encryption algorithm in Big-O notation?

It is $O(1)$ time and space because the Blowfish block cipher has a constant bound on the key size (≤448 bits) and a constant block size (64 bits) and those are the only inputs—there are no variable-size inputs.

If you apply Blowfish in a composition like CBC then it is expanded to work on $n$ blocks by applying the Blowfish block cipher $n$ times, so it costs $O(n)$ time and $O(1)$ space.

P.S.  FYI, Blowfish is obsolete, and has been for decades since the standardization of AES in the late '90s.  There is no reason to use it today, and strong reasons not to use it or any other 64-bit block cipher.


CLEFIA vs AES 128-bit I am running a comparison between CLEFIA(Lightweight cipher from Sony Corporation which is a standard now http://www.sony.net/Products/cryptography/clefia/standard/index.html) and AES 128-bit.

The comparison is done on an android device. (Galaxy S3)

For CLEFIA's code, I have converted their official code which is in C to Java from here http://www.sony.net/Products/cryptography/clefia/download/data/clefia_ref.c, and for AES 128-bit I am using Java's Javax.Crypto packages.

What struck me is that, instead of CLEFIA being lightweight and running faster (needs less resources, less cycles, etc), it was AES which was actually faster, and a lot. (Around 150 times and even more).

I unfortunately was not able to test both on sensors where the computational power and battery life is really minimal compared to a mobile.

Has anyone had an experienced with a lightweight cipher versus AES? (If needed, I do not mind sharing my code)

You benchmarked a highly optimized AES implementation against a reference implementation of CLEFIA:

 * NOTICE
 * This reference code is written for a clear understanding of the CLEFIA
 * blockcipher algorithm based on the specification of CLEFIA.
 * Therefore, this code does not include any optimizations for
 * high-speed or low-cost implementations or any countermeasures against
 * implementation attacks.

On top of that it's possible your phone's CPU has hardware acceleration for AES.


DDH and pairings are not contradictory in RingCT 2.0? As I know DDH assumption and bilinear pairings are contradictory, but I see this in a paper, RingCT 2.0.

How could this be ok? Linkable ring signature will be attacked by bilinear pairings.

For the following explanation, let $e: \mathbb{G}_1 \times \mathbb{G}_2 \rightarrow \mathbb{G}_T$. It depends on the setting you are using whether DDH can hold or not. In the symmetric setting ($\mathbb{G}_1 = \mathbb{G}_2$, i.e., Type 1 pairings) the pairing serves as a DDH oracle for both, $\mathbb{G}_1$ and $\mathbb{G}_2$ and DDH can neither hold in $\mathbb{G}_1$ nor in $\mathbb{G}_2$. In the asymmetric setting, we distinguish two different settings, i.e., Type 2 and Type 3. The important difference in this context is that in the Type 2 setting there exists an isomorphism $\psi: \mathbb{G}_2 \to \mathbb{G}_1$ while such an isomorphism is unknown for the Type 3 setting. Now, in the Type 2 setting, the pairing together with the isomorphism serves as a DDH oracle for $\mathbb{G}_2$, while DDH is assumed to hold in $\mathbb{G}_1$. Finally, in the Type 3 setting, DDH is assumed to hold in both $\mathbb{G}_1$ and $\mathbb{G}_2$.

The particular combination you are asking about is in the Type 1 setting, so DDH can not hold for both source groups of the pairing.

Additional note: In the paper you are citing, actually a group (i.e., $\mathbb{G}_q$) which is independent of the pairing groups is used. In such a setting DDH can of course also hold in $\mathbb{G}_q$. However, using an independent group also means that the order of this group is different to the order of the pairing groups, which makes ZK consistency proofs between elements of the different groups - as required in this paper - quite complicated. I can not find anything in the paper which would address this issue.


Does NTRU provide Perfect Forward Secrecy? Does NTRU provide Perfect Forward Secrecy if the world would use it in an HTTPS connection?

Properly speaking, forward secrecy is a property of a protocol. The protocol is forward secret if compromise of the long term keys does not allow an attacker to decipher any past communications.

(Occasionally a distinction is made between that and perfect forward secrecy, with the latter secure when the attacker also knows e.g. all other session keys.)

You can build a key exchange protocol that provides forward secrecy from any authenticated public key encryption, including NTRU:

Assume the parties have exchanged long term keys.
A generates an ephemeral key-pair and sends the public key to B, using the long term keys for authentication.
B generates a session key, encrypts it for A's ephemeral keys and sends it to A.
A deletes the ephemeral key-pair after decrypting the session key.

However, if you mean the old draft protocol I linked in a previous answer, then, no. Unless I'm missing something, that protocol just encrypts a random secret using the long term keys. That does not provide forward secrecy.


How are the names of cryptographic algorithms (like RSA, AES, SHA-256, Curve25519, etc.) pronounced? I'll have to give a spoken presentation on cryptography and I don't want to make any pronunciation mistakes. Therefore I'm asking how I should pronounce acronyms like RSA, AES, SHA-1, SHA-256, IGE and CBC, Curve25519, ECDH, MAC, HMAC, etc., both in English and in other languages. (The presentation is in Italian, so I'd prefer it.)

However you pronounce them, the important thing is to make sure that your listeners understand you.  In general, it's never wrong to pronounce acronyms letter by letter (and digit by digit), as in:

RSA → "arr ess ay"
AES → "ay ee ess"
SHA-1 → "ess aitch ay one"
SHA-256 → "ess aitch ay two five six" (or "ess aitch ay two fifty six" or even "ess aitch ay two hundred and fifty six")

If the acronym could also be pronounced as a word, and the resulting pronunciation is clear and distinct enough, you can also do that.  So "shuh two fifty-six" for SHA-256 is OK, too.  Certainly this is true for longer acronyms that "just happen to" spell out an English word; I'd much rather hear e.g. SHAKE256 pronounced "shake two fifty six" than "ess aitch ay kay ee two five six", even if the latter isn't strictly speaking wrong, either.

Curve25519 is a bit of a special case.  Obviously the word "curve" should be pronounced as the English word, and I would say that it's perfectly fine to just read out the numbers one by one, as in "curve two five five one nine", although "curve two five five nineteen" or "curve two fifty five nineteen" would also be OK.

As yyyyyyy notes in the comments, though, the number 25519 in the name is really made up of the two numbers 255 and 19, so you should not read it as e.g. "curve twenty-five thousand five hundred and nineteen".  You can thank D.J. Bernstein for this naming ambiguity; his Poly1305 MAC is arguably even worse named, since the two numbers concatenated into that name are 130 and 5, but pronouncing it e.g. as "poly one thirty five" would just invite naïve listeners into parsing it as "Poly135".  I don't know how DJB himself pronounces that name, but I'd probably just read it digit by digit as "poly one three oh five". Peter Schwabe pronounces it at "poly thirteen oh five".

Of course, where it gets really tricky are names like Rijndael or Grøstl which are not acronyms, and which even (or perhaps especially) native English speakers have trouble pronouncing.  In those cases, I'd suggest either looking up an audio sample of the "official" pronunciation and imitating it as well as you can, or just giving up and pronouncing the name according to the standard pronunciation in whatever language you're speaking.


Is a known plaintext, ciphertext, and public-key a viable attack on RSA? Assume Alice and Bob are using RSA to create a common session key and Cindy is listening, attempting to obtain the session key.

Alice and Bob each have their public- and private-key pairs ($\left[pub_{A}, pri_{A}\right]$ for Alice and $\left[pub_{B}, pri_{B}\right]$ for Bob) and Alice, Bob, and Cindy all know everyone else's public key.

Alice generates a random $n_{A}$ and sends out $En_{pub_{B}}\left(n_{A}\right)$ ($n_{A}$ encrypted with Bob's public key).
Bob generates a random $n_{B}$ and sends out $En_{pub_{A}}\left(n_{B},n_{A}\right)$ and sets the session key to $n_{A}\oplus n_{B}$.
Alice sends out $En_{pri_{A}}\left(n_{B}\right)$ and sets the session key to $n_{A}\oplus n_{B}$.

My thinking is, Cindy decrypts message 3 with Alice's public key to obtain $n_{B}$.  Now Cindy has a plaintext, ciphertext pair and the key that decrypts the ciphertext.

My question is, is it possible with this information for Cindy to find $pri_{A}$ in order to decrypt message 2 and find $n_{A}$?

No matter how bad a protocol built on top of RSA is, there is no known risk that a private key leaks from valid plaintext/ciphertext pairs, even if the adversary chooses plaintext or ciphertext; that's one of RSA's virtues. Thus to the question is it possible with this information for Cindy to find $pri_A$ we can answer: as far as we know, no; and more, Cindy can not find an equivalent to  $pri_A$.

More precisely: even with access to an oracle accepting any $x$ and answering with $x^d\bmod N$, a computationally bound adversary can not (as far as we know):

factor $N$;
or otherwise compute any of the several equivalent private exponents $d$ or private keys;
or compute $x^d\bmod N$ for some random $x$ submitted to the adversary after access to the oracle has been denied.

That does not answer if Cindy can decrypt message 2 or otherwise find $n_A$ (which was not asked :-).

It is now asked if Cindy can find $n_A$. The answer is yes, at least in some setup matching the question. To justify that claim, I'll explain one such a setup, and how Cindy proceeds.

Assume that:

$En_{pub}$ and $En_{pri}$ are the public (encryption) and private (decryption) operations of textbook RSA;
the modulus in the public keys of Alice and Bob have the same bit size $m$;
the random $n_A$ and $n_B$ have (at most) fixed bit size $r$, with $2\cdot r<m$;
at step 2., $n_B,n_A$ designates the integer corresponding to the concatenation of the $r$-bit strings representing $n_B$ and $n_A$, using little-endian convention;
Bob verifies that applying $En_{priv_B}$ to the cryptogram he obtained at step 1. yields an alleged $n_A$ of at most $r$ bits, which he proceeds to use during step 2.;
Alice verifies that applying $En_{priv_A}$ to the cryptogram she obtained at step 2. yields an alleged $n_B,n_A$ of at most $2\cdot r$ bits, from which she extracts $n_B$ that she proceeds to use during step 3.;
Cindy can play the role of Bob with respect to Alice, and of Alice with respect to Bob, and further Cindy can persuade Bob to engage in a protocol where Bob acts just as Alice does (e.g. because Alice and Bob use the same program and parameters save for the value of their public key pairs, and Cindy persuades Bob to use his program to establish a session key with Alice in the manner Alice uses her program to establish a session key with Bob).

Cindy does the following:

Impersonating as Bob to Alice in a protocol initiated by Alice, Cindy gets the cryptogram $En_{pub_B}(n_A)$ generated by Alice at step 1;
Impersonating as Alice to Bob in another protocol this time initiated by Bob, she gets (and ignores) the cryptogram generated by Bob at step 1, then passes the aforementioned $En_{pub_B}(n_A)$ as the cryptogram allegedly generated by Alice for Bob at step 2. of that other protocol;
In preparation of step 3. of that other protocol, Bob applies $En_{priv_B}$ to that cryptogram, yielding $n_A$;
that $n_A$ is just the same as $n_A,0$ that Bob would legitimately receive at that step should he have chosen his random number as $0$ in the first step of that other protocol (which he likely did not);
as nothing in the protocol asks Bob to check that the random he has chosen appears in what he obtained, Bob dutifully compute $En_{priv_B}(n_A)$, and sends it to what he believes is Alice, and in reality is Cindy;
Cindy persuades Bob to start over, this time in a protocol where Bob acts as Alice expects Bob to act;
Cindy passes $En_{pub_B}(n_A)$ to Bob as the cryptogram of the first step of that new protocol, as if it was from Alice (which it was in the original protocol started by Alice, which meanwhile is still waiting for Bob);
from then on, Cindy let Bob and Alice communicate normally;
Cindy has $En_{priv_B}(n_A)$ (obtained from Bob at step 3 of the fake instance of the protocol), applies $En_{pub_B}$ to that, and now has $n_A$ in the protocol now being used by Alice and Bob;
Cindy has $En_{priv_A}(n_B)$ (obtained from Alice at step 3 of the real instance of the protocol), and as noted in the question applies $En_{pub_A}$ to that, obtaining $n_B$ in the protocol now being used by Alice and Bob;
Cindy can thus obtain the session key $n_A\oplus n_B$.

That attack can sometime be adapted to big-endian conventions (unless I err, at least when the public exponent $e$ is such that $3^e<2^r$; thus with $m=2048$, $r=512$, $e=257$ or less).

Towards turning that protocol into something safe, we are missing:

A check before step 3. by Alice (and every legitimate party performing her role), that the random $n_A$ she generated in step 1. is found by deciphering with her private key the cryptogram received in step 2., allegedly from Bob;
An additional step 4. where Bob (and every legitimate party performing his role) checks that the random $n_B$ he generated in step 2. is indeed found by verifying, with Alice's public key, the cryptogram received in step 3., allegedly from her;
Forward secrecy, that is insurance that past session keys do not leak should one of Alice's or Bob's private key leak at some point in time. One technique towards that goal, which more generally avoids that the authentication step 3. turns into a decryption oracle (that's how the above attack could be outlined), is to split $n_A$ and $n_B$ into two parts: one used only to build the session key, another used for authentication purposes.
A proper encryption at steps 1. and 2., rather than textbook RSA;
A proper signature (possibly with message recovery) at step 3, rather than textbook RSA.

It is left as an exercise to the reader to exhibit attacks working with the first two tweaks alone (that's trivial unless $r\cdot e\gg m$ holds, but I fear there could be other cases).


Asymmetric algorithm to generate compact unique messages that can be validated I have a cryptographic problem with the following characteristics:

I need to generate a set of relatively short messages; say 20 bytes in length
The contents of the messages themselves is not important to me as long as they are unique within a certain set.
These messages will be sent to a consumer.
The consumer must be able to (with a certain degree of confidence) verify that the message was generated by the producer - again, the contents themselves are actually not important.
An asymmetric algorithm must be used, so that the private key does not have to be shared with the consumer.

I must emphasise that I'm (obviously) not looking for perfection here - the most important thing is for the consumer to get as much confidence as it can in the identity of the producer using a very small footprint of data, and without needing to hold the private key.

I was thinking something like:

generate a unique message [M] (could just be an integer) within a bounded set
generate a digital signature using a private key e.g. RSA and sign the message [S]
"compress" the signature into a smaller space by taking a hash of it using a well known algorithm that has a smaller footprint e.g. something simple like MD5 [CS]
append the "compressed" signature onto the message e.g. M,CS packing these into the number of bytes available as appropriate
the consumer does the opposite to verify

Am I way off the mark? Is there a well known algorithm to do something like this? If it isn't completely ridiculous then is there a good way to evaluate what the actual chances of brute-forcing this would be?

EDIT

Having just re-read my own posting I've noticed a bit of a fatal flaw here :-) how can I use the public key to verify a signature I've "compressed"? I can't see how that could work, but the rest of my question stands.

Is there another more suitable algorithm to do this that is asymmetrical? Is there even a name for what I'm describing?

EDIT 2

I'll try and add some more detail as to WHY its important that this is attempted.

Essentially this is a backup scheme for when the primary method of validating a message is not available. The primary is a request/response over a secure channel back to the producer. This callback would provide meta-data associated with the message. If this is not available then it would be advantageous to us to have a best-effort validation that the message at least came from the producer in the first place - even if we can't get at any of the meta-data we'd like.

We can't trust the consumers with a shared key, and we have a very limited bandwidth/method of transmitting the messages themselves (the primary lookup occurs over a different channel).

It sounds like the main obstacle to using RSA signatures is the size of the signature. If that's the case, consider using Elliptic Curve Digital Signature Algorith (ECDSA).

EC signatures are much shorter than RSA signatures with equivalent strength. For example, an ECDSA signature with a 256-bit key is about 70 bytes long in its standard encoding. This is as strong as an RSA signature with a 3072-bit key, which is 384 bytes long. ECDSA is also a NSA Suite B recommendation, while RSA is not.


Any side effects of switching from Rijndael to AES in a .net application? Our company would like to update our .Net apps so that they can run on Windows machines that require FIPS compliance. Currently we are using the System.Security.Cryptography.Rijndael class. I changed our encryption methods to use Cryptography.Aes instead and our apps are able to run on machines with FIPS compliance enabled and appear to function exactly the same.

That seems too easy. So my question is: are there any side effects to switching to AES that aren't readily apparent? Or does the encryption method not matter as long as the inputs and outputs are the same?

are there any side effects to switching to AES that aren't readily apparent?

Key sizes: AES is only defined for 128, 192, and 256 bit keys. Rijndael supports other key sizes. There is not much benefit to using the key sizes in between these two, but if you use AES they will not be available anymore.
Block size: Rijndael allows a wider range block sizes than AES
Performance: Using AES could lead to (notable) performance increases. Modern CPUs support a hardware instruction for evaluating AES that will be significantly faster than a software implementation. This will be dependent on the machine that is executing the code, as well as the implementation.

  Or does the encryption method not matter as long as the inputs and outputs are the same?

The encryption method very much does matter. Different ciphers are not compatible with each other.

AES and Rijndael are not different ciphers per se. AES is the title given to the standardized variants of Rijndael.


Can a shift cipher attain perfect secrecy? On a practice question for my intro cryptography exam, it asks the following:

Assuming that keys are chosen with equal likelihood, the shift cipher provides:
   A) computational security
   B) perfect secrecy
   C) semantic security
   D) none of the above

I chose "none of the above", though I wasn't too sure. But I was certain it was not "perfect secrecy". However, when I review the exam solution key, it says "perfect secrecy" is, in fact, the answer.
Given that the message space of a shift cipher is huge, and the key space's cardinality is only 26, how can it possibly provide perfect secrecy under any circumstances?

The Caesar cipher (aka Shift cipher) has, as you said, a key space of size 26. To achieve perfect secrecy, it thus can have at most 26 plaintexts and ciphertexts. With a message space of one character (and every key only used once), it would fit the definition of perfect secrecy.

For the usual use with messages longer than one character, or multiple messages with the same key, none of the given options fit (other than the "None" option).


"Power of one" as input to functions of a cryptosystem What does $1^\lambda$ mean when you pass it as a parameter to the functions of a cryptosystem. The cryptosystem in question is this and a picture reference is this.

I have been told it signifies the "security parameter of the cryptosystem" but this is not clear to me. In this picture, you can see that

$\lvert p \rvert = \mu$ bits

$\lvert q \rvert = 2\lambda - \mu$ bits

which means $\lvert \Delta_K \rvert = 2\lambda$ bits

So does all this mean that if I want 128 bits of security,
$\lambda$ has to be 128 and $\Delta_K$ 256 bits?

If yes, this would not make sense with their results they mention and also all the work I have done with this system. For a 128-bit security in this system, the size of $\Delta_K$ has to be 1828 bits. This is something I can strongly assure you of.

Any pointers would be greatly appreciated. Lastly reiterating the question,

"What does the notation $1^\lambda$ mean when it is passed to KeyGen(), Encrypt() and Decrypt() ?"

The notation $1^\lambda$ means a string with $\lambda$ characters all of them equal to 1. For instance, if $\lambda = 3$, then $1^\lambda$ is $111$.

And yes, it typically stands to the security parameter, from which the probability of "breaking" the system is measured (as well as the resources needed to do so and also to execute the cryptosystem's procedures).

The reason to use $1^\lambda$ instead of $\lambda$ is theoretical. The point is that the functions run by the users (KeyGen, Enc, Dec, etc) are supposed to run in polynomial time and the best attacks are usually supposed to take exponential time. But polynomial/exponential time regarding what? Regarding the size (length) of the input. So if you say that the input is simply an integer $\lambda$, what is the input's length? But using $1^\lambda$ as the input, the size is clearly $\lambda$, because the input has $\lambda$ characters (or letters, or bits...).

And about this specific scheme that you've cited, I would say that the authors are probably miss-using the notation. It seems that $\lambda$ measures how many bits the integers used there have. So, the algorithms run in poly$(\lambda)$ as expected. But, as it happens often (e.g. with RSA), for a security level of $\lambda$ bits, the integers used in the scheme must have much more than $\lambda$ bits.


Using SHA384 as an asymmetric cipher? SHA384 is a hash function that can be (and is) used to verify data by checking it. Can it also be used as the background for a public-key crypto system? Here is what I mean:

A 48-byte string is generated randomly. This is the private key.
That 48-byte string produces another piece of data through SHA384: the public key.
The keys can be shared secretly by exchanging keys (example: Alice tells Bob her private key and it is encrypted with her public key.)

I want to know if this is possible because RSA is currently secure but can be broken by quantum computers in the future. Quantum computers can factor large primes but they can't break hash functions. Also, I picked SHA384 because it can't be broken with a quantum computer.

Stream cipher from hash functions: possible

For any cryptographically strong pseudo-random function (PRF) the CTR mode of encryption can be defined. You can build such a PRF from a hash function.

One can achive to produce a key stream by :

$$H(k,0) || H(k,1) || ... || H(k,m)$$ where the $k$ is your symmetic key. Salsa20 and ChaCha20 are examples.

Public key from hash functions: your method? No

  A 48 byte string is generated randomly. This is the private key.
  That 48 byte string produces another piece of data through SHA384: the public key.
  The keys can be shared secretly by exchanging keys (example: Alice tells Bob her private key and it is encrypted with her public key.)

What do we do after this? Do you remember that we need a system to encrypt the data with the public key and decrypt with the private key like RSA.

  I want to know if this is possible because RSA is currently secure but can be broken by quantum computers in the future. Quantum computers can factor large primes but they can't break hash functions. Also, I picked SHA384 because it can't be broken with a quantum computer.

What about quantum-resistant public-key cryptography

NTRU (lattice-based cryptography)
McEliece (code-based cryptography)
Ring Learning with Errors (R-LWE) (lattice-based cryptography)
Multivarite Cryptography
Isogeny-based cryptography such as SIKE conjectured to be infeasible even Shor is ever implemented.

and AES256 which has $2^{128}$ bit security against Grover's algorithm if ever built and run efficiently for the queries.

Now you can use these to achieve Hybrid Cryptosystem.

Also note that to have a resistance for hash functions against the quantum attacks, you need to consider the Brassard et al. method on hash functions. That has $\mathcal{O}(\sqrt[3]{n})$ attack time for n-bit hash function. whereas the Grover's method has $\mathcal{O}(\sqrt{n})$-time.

This cost calculation of the quantum attacks hides some metrics like Brassard, the attack requires a huge Quantum circuit. Grover for AES-128, not clear how one will run the $2^{64}$ evluations.


Is there a difference in the security provided by a OTS vs a MTS or FTS? Or are they all just different ways of providing the same service? Is there a difference in the security provided by a One Time signature vs a Many time Signature or a Few time signature? Or are they all just different ways of providing the same service?

The question is quite broad, but the main difference in well designed schemes should be that an OTS can be used once, FTS can be used a few times, and MTS can be used many times.
As an example, with SPHINCS+ you can sign up to $2^{64}$ messages before any degradation in security.
The goal of an FTS scheme (created from an OTS) isn't to add security but to allow one public key to sign a few messages.  Similarly for a MTS scheme (built from OTS and/or FTS), to sign many messages.
That is not to say there is not any difference in security.  It is difficult to answer generally. An MTS scheme built in a stateless way from a combination of OTS and FTS is really it's own beast.  Although it's security will obviously rely on the underlying schemes and how they are used.


Finding multiple smaller collisions equal work as finding a bigger collision? Problem A:
I receive two hash digests $H(x), H(y)$ and the corresponding preimages $(x, y)$.
$H$ is a 128-bit cryptographic hash function: $H: \{0,1\}^{*} \longrightarrow \{0, 1\}^{128}$
I need to find two second preimages $(x', y')$ such that $H(x) = H(x')$ and $H(y) = H(y')$, where $x \neq x'$ and $y \neq y'$.
Problem B:
I receive one hash digest $H'(x)$ and and the corresponding preimage $x$.
$H'$ is a 256-bit cryptographic hash function:
$H': \{0,1\}^{*} \longrightarrow \{0, 1\}^{256}$
I need to find one second preimage $x'$ such that $H(x) = H(x')$ , where $x \neq x'$.
Are problem A and B equivalent?  In other words, do both take $2^{256}$ work?

Are problem A and B equivalent?  In other words, do both take $2^{256}$ work?

No; in the first case, you can find the first collision with $2^{128}$ effort and then find the second collision with $2^{128}$ effort, yielding a total effort of $2^{128}+2^{128} = 2^{129}$
Actually, you'd likely start hashing arbitrary values, and stop after both a second preimage of $x$ and a second preimage of $y$ came up; this expected effort is slightly less than $2^{129}$...


AES 128bit round level recommendation we don't want change standard just after every attack, now for AES 128bit blocks i think 16 round is secure, but what is best round amount ? we had attack for 7 round then 10 round and it going so on i think so is better we use a better standard. how many round you think we use is better for a long time ?

The AES standard specifies the use of 10 rounds with 128-bit keys. Anything other than this is, by definition, not AES. There are no known effective attacks against standard AES-128.


Authentication in Lattice PQC candidates I am looking into Authentication in lattice cryptography. Specifically in the NIST KEM finalists. I was specifically looking to see if there was a GCM (Galois counter mode) equivalence in the lattice space.
As I understand, GCM will also be broken by quantum computing and therefore may need investigating also.
Do the NIST finalists have some sort of authentication process that is comparable to GCM? Or am I misunderstanding some aspect of how lattice cryptography works?
(I am specifically interested in hardware implementations of these methods, so if there is anything specific to hardware I'd love to hear it!)

As I understand, GCM will also be broken by quantum computing

The idea that GCM would be broken is, at best, questionable; it is broken only in the scenario where you allow the attacker to make entangled queries, and is returned entangled answers.  That is, for this to be an applicable attack, the implementation under attack must also be a Quantum implementation; that is, it must receive the entangled state from the adversary, it must maintain it throughout the encryption/decryption process, and then return the entangled result back to the adversary.
This is in contrast to RSA/DH/ECC - there, you can take the public key, load it into your Quantum Computer, run Shor's, and directly obtain the private key - the only cooperation you need from the device under attack is the public key (which we generally assume is public).
In a white-box scenario, this attack against GCM is plausible (because the adversary would be able to install the entire implementation-under-attack within his Quantum Computer and make entangled queries at will).  Outside of that, this would seem (to me) to assume an extraordinary amount of cooperation from the device under attack.  In some ways, this could be considered a side channel attack; only much easier to defend against than most side channel attacks (just don't implement GCM in a way that preserves Quantum entanglement - given that we currently don't know how to preserve entanglement over that many operations even if we wanted to, this sounds quite easy).
No one thinks GCM is broken because DPA probing can, given a sufficient number of queries, generally recover the key - it's not clear to me why this easier-to-defend against attack is more of a concern.