Hmm, that's a good point, since the bloom filter check is CPU-harder than the action taken on lookup, you could just do all the lookups in parallel and then do all of the copies separately.
508 karma · joined August 12, 2015
It seems like this would make the compression lossy and discard, e.g., transitions from #ffffff to #fffffa, and the line above it where the mean of pixel data is taken would discard, e.g., transitions from #ff0000 to #00ff00 regardless of the threshold used.
Am I misunderstanding the role of that line of code? It doesn't seem like anything that is a 0 in the resulting mask would be encoded into the bloom filter.
Ultimately the data they are storing is tuples of (x,y,r,g,b), which means that it is not sufficient to ask "does (x1,y1) pass the bloom filter?" which would be embarrassingly parallel; you have tobe able to match it to an index in your list of (r,g,b) data.
The way this is done is to iterate over all (x,y) in a consistent order for encoding and decoding, and for each (x1,y1), if it passes the bloom filter, then the next (r1,g1,b1) tuple is the pixel data for that pixel.
This looks like it is not storing the diff for any pixel that had the mean of its r,g,b values change by less than 10, which means that if a pixel goes from pure blue (#00ff00) to pure red (#ff0000) in consecutive frames, it would decode as pure blue in both frames.
You could store all of that in a single map from (x,y) to (r,g,b), which would cost you, say, 4 bytes per pixel for the (x,y) data and then, say, 30 bits or (rounding up) 4 bytes per pixel for the (r,g,b) with 10-bit color. A hash map would optimize lookup, but for efficient storage you really just want an array of 8-byte chunks where the first two bytes are x, next 2 are y, next 10 bits are r, then g, then b. To decode, you just start with the previous frame and then iterate down the list and apply each diff in the list.
If you iterate over (x,y) in a consistent order, you avoid the need to store it because you can simply say that the next (r,g,b) tuple in your list is the pixel data for the next (x,y) value that passes the bloom filter. This effectively cuts the amount of data you have to store per pixel in half, but increases the number of pixels you have to store by a probabilistically small amount because bloom filters have false-positives.
Motivational Interviewing is an evidence-based clinical technique for helping people move through ambivalence during the contemplation, preparation, and action stages of change under the Transtheoretical Model.
In Chapter 2 of the 3rd Edition, they define Acceptance as one of the ingredients for change, part of the "affect" of Motivational Interviewing. Ironically, people do not tend to change when they perceive themselves as unacceptable as they are. It is when they feel accepted as they are that they are able to look at themselves without feeling defensive and see ways in which they can change and grow.
Nearly all that they describe in chapter 2 is affective—it is neither sufficient nor even necessary in the clinical context that the clinician feel a deep acceptance for the client within themselves, but the client should feel deeply accepted so that they are given an environment in which they can grow. The four components of the affect of acceptance are autonomy support, absolute worth (what Carl Rogers termed "Unconditional Positive Regard"), accurate empathy, and affirmation of strengths and efforts.
Chapters 5 and 6 of the third edition define the skills of providing the affect of acceptance defined in Chapter 2—again, not as a feeling, but as a skill. It is something that can be taught, practiced, and learned. It is a common misconception to believe that unusually accepting people become therapists, but what is actually the case is that practicing the skill of accurate empathy trains the practitioner to be unusually accepting.
The chief skill of accurate empathy is that of "reflective listening", which essentially consists of interpreting what the other person has said and saying your interpretation back to them as a statement. For an unskilled listener, this might be a literal rewording of what was said, but more skilled listeners can, when appropriate, offer reflections that read between the lines. Very skilled listeners (as measured by scales like the Therapist Empathy Scale) will occasionally offer reflections that the person being listened to did not think, but will recognize within themselves once they have heard it.
In that sense, in the way that we measure empathy in settings where it is clinically relevant, I've found that AIs are very capable with some prompting of displaying the affect of accurate empathy.
Identity theft would become essentially impossible. Then if it were adopted by things that are fundamentally associated with your real identity (e.g., banks, payment processors, insurance providers, government institutions) then whole classes of phishing scams would become impossible.
Then there are the use cases where it's convenient for the user. Public transit, event admissions, membership cards.
Then there are the use cases where it's convenient for the provider. Alcohol sales, social media, adult content.
... Yeah, that would turn into a dystopia incredibly fast.
I would need to selectively generate grammatically valid zstd streams for this to be tractable at all.
But a gzip decompressor is not turing-complete, and there are no gzip streams that will expand to infinitely large outputs, so it is theoretically possible to find the pseudo-Kolmogorov-Complexity of a string for a given decompressor program by the following algorithm:
Let file.bin be a file containing the input byte sequence.
1. BOUNDS=$(gzip --best -c file.bin | wc -c)
2. LENGTH=1
3. If LENGTH==BOUNDS, run `gzip --best -o test.bin.gz file.bin` and HALT.
4. Generate a file `test.bin.gz` LENGTH bytes long containing all zero bits.
5. Run `gunzip -k test.bin.gz`.
6. If `test.bin` equals `file.bin`, halt.
7. If `test.bin.gz` contains only 1 bits, increment LENGTH and GOTO 3.
8. Replace test.bin.gz with its lexicographic successor by interpreting it as a LENGTH-byte unsigned integer and incrementing it by 1.
9. GOTO 5.
test.bin.gz contains your minimal gzip encoding.
There are "stronger" compressors for popular compression libraries like zlib that outperform the "best" options available, but none of them are this exhaustive because you can surely see how the problem rapidly becomes intractable.
For the purposes of generating an efficient zip bomb, though, it doesn't really matter what the exact contents of the output file are. If your goal is simply to get the best compression ratio, you could enumerate all possible files with that algorithm (up to the bounds established by compressing all zeroes to reach your target decompressed size, which makes a good starting point) and then just check for a decompressed length that meets or exceeds the target size.
I think I'll do that. I'll leave it running for a couple days and see if I can generate a neat zip bomb that beats compressing a stream of zeroes. I'm expecting the answer is "no, the search space is far too large."
As you said, same effect: the scheme you have described is not an alternative to AEAD. It is an example of AEAD. You're still using the offset as associated data, you just happen to be composing your AEAD scheme out of another AEAD scheme into which you pass an empty string as associated data.
Other than differences in the limit to the number of messages you can encrypt before nonce exhaustion or the number of bits of secrecy or authentication strength provided, the external interface and use case of your system perfectly matches that of AES-GCM or other popular AEAD constructions.
If you are using an AEAD cipher mode, then you always have AD, but sometimes that AD might be the empty string. In that case, the advantage to using contextual AD as opposed to using the empty string as AD and then doing additional verification on the decrypted object is that it prevents some kinds of timing attacks, because cryptographic libraries will often implement AEAD constructions to fail in constant time, where as your scheme will take longer if post-decryption validation of contextual data encoded in the plaintext fails compared to if decryption fails.
That guarantee is not provided with unauthenticated stream ciphers. For example, some stream ciphers work by essentially using a deterministic but unpredictable PRNG seeded with the key and IV to generate a bitstream, and then XOR the plaintext with that bitstream to generate the ciphertext.
With such a stream cipher, If Eve knows that the data format is, e.g., the an 8-byte unsigned integer user ID followed by the rest of the payload, Eve can take the first 8 bytes of the ciphertext and XOR it with Bob's user ID (public information) and her own user ID to corrupt the message in such a way that the ID in the resulting cleartext would contain her user ID instead of Bob's, and thus pass the validation that it seems like you are proposing.
Let C[] be the cipher text, K[] be the key stream, B be Bob's ID, and E be Eve's ID:
C[:8] = B ^ K[:8]
C[:8] ^ B = K[:8]
C' = C[:8] ^ B ^ E ++ C[8:]
C' would decrypt, validate as "belonging" to Eve, and contain Bob's data.
If Alice saves some data to her account, but Eve manages to access the database, Eve can change the database state to convince the application to retrieve Alice's data for her (by cloning it into a row with her own user ID). However, when the application attempts to decrypt that data, it will fail because of the AEAD. This ensures that both the database and some service with access to the encryption key (or the encryption key itself) would have to be compromised in order for Eve to exfiltrate her illicit copy of Alice's data.
You can find an implementation of AES-CTR-HMAC (at a high level where AES-CTR and HMAC are both given) here: https://github.com/tink-crypto/tink-go/blob/main/aead/aesctr...
Even if I gain access to the database, if the keys are managed securely, I can't read another user's data (or even really my own). I have to go through the authorization logic of the application that will decrypt it on my behalf.
However, if I can create a row in the database with my ID and another user's data, I can then convince the server I am authorized to view that cell, and it will happily decrypt it on my behalf, assuming something like AES-CTR or some other stream cipher without authentication.
Authenticated encryption like AES-CTR-HMAC solves that problem, because now the application will see that I am authorized to view that cell (because it sees the user ID matches mine) and it will decrypt it for me (using that user ID as the associated data), but the decryption will fail because the associated data does not match, leaving me unable to exfiltrate the data that I convinced the server belonged to me, and probably setting off some kind of alarm because that sort of decryption should never fail unless things have been tampered with.
I'm not overly fond of the example and I find it confusing as well. I think the example may be a bit confusing because the term "authentication" is overloaded between application-level authentication and cryptographic authentication, i.e., "if the chat protocol authenticates the user ID" sounds like it is talking about the user logging into the server securely. The user is authenticated by having a secret negotiated with the server. In the next bullet, they talk about "authenticating" the associated data, referring to it in the cryptographic context, but they don't indicate why that would be a problem because in their example, the malicious actor still doesn't have the key. The article handwaves it as "the attacker might be creative."
If they had the key, but not the associated data, you'd still be in a relatively bad situation, because the associated data is not secret. It doesn't serve as a second key because it is not high enough entropy and is ideally zero entropy conditional on already having all information from the originating context.
Another source of inspiration (and something I use in production) is the Tink family of cryptographic libraries by Google [1]. Their Go implementation [2] is not without its warts, but it's very difficult to run into any of those security bugs that exist around cryptography. Where the Go documentation lacks, there are some examples in the developer docs that help fill some of the gaps [3] [4].
The documentation isn't 100% complete, but I find it more discoverable than the standard library because while the standard library requires you to read both `crypto/cipher` and `crypto/aes` or `golang.org/x/crypto/chacha20poly1305` depending on what kind of cipher you want, Tink organizes it by use cases [5] and generally groups together all the things you need to do cryptographic operations under the use-case-named interfaces in the `tink` package [6], with the corresponding key generation templates located under the top-level packages of the same name [7].
[1]: https://developers.google.com/tink
[2]: https://github.com/tink-crypto/tink-go/
[3]: https://developers.google.com/tink/key-management-overview#g...
[4]: https://developers.google.com/tink/encrypt-data#go
[5]: https://developers.google.com/tink/choose-primitive
[6]: https://pkg.go.dev/github.com/tink-crypto/tink-go/v2/tink#AE...
[7]: https://pkg.go.dev/github.com/tink-crypto/tink-go/v2@v2.4.0/...
But in a corporate environment where repositories are often authenticated, the fact that dependency fetch issues are reported as Java exceptions (having the wrong password in your netrc file shows up as "IOException occurred during fetch of ... Code 401") is a deal breaker for a C/C++ development staff unfamiliar with Java.
They happily take their ten minute incremental builds and "it works on my machine" issues in return for a build process they can understand, and as much as I want them to be wrong (I use Bazel all the time at home), I can't blame them for wanting tooling they understand.
I dread running builds because it takes like ten minutes to run `make all`. I spent like four hours writing Bazel build files for it and all of a sudden my clean rebuilds were taking like five minutes and my incremental builds were taking a couple of seconds. It was fantastic.
Ultimately it was rejected because other people on the project hated working with bazel and weren't familiar enough when it to debug any problems. If a build didn't work, the only solution was to call me because no one else was used to interpreting the bazel errors: if a curl command failed in a script in a docker file somewhere, everyone knew what that meant. But I was the only one who would see "IOException fetching... Error 401" and immediately know that they provided the wrong password.
I also consulted for another project where people were using containers as VMs, running systemd and copying in updated binaries, because they, too dreaded rebuilding the containers. Bazel, again, made it so that they could rebuild everything in a matter of seconds. That project is still happily using bazel last I checked.
The fact that they needed to make a map a part of the language in order to allow it to be generic and statically-typed proves that generics are useful and should therefore have been a language feature much earlier than they became one.
There are a variety of things that the standard library or compiler deal with using weird workarounds that seem to indicate missing language features.
The thing is, the features are only "missing" if the language is designed to do the things those features permit. So the counterargument is that Go is a very opinionated language designed to do solve a few classes of problem very easily, like writing database-backed web services, and the reason the standard library or compiler teams have to do weird hacks at times is because Go wasn't made for writing those things, and designing to make those use cases easy would pollute the language from the perspective of someone using it for its intended purpose.
This came with some changes to open up the developer license program for RHEL so that it could be used for small scale production workloads.
The big problem was that the latter was only hinted at by the time the CentOS EOL was announced and didn't get spelled out in precise language for a few more months, which led to a lot of very angry sysadmins who had been using CentOS in production franticly searching for a new platform in the meantime.
Now that compilers know cleverer optimizations, undefined behavior is often impossible to reason about because the compiler can change your logic into something else that is more optimal and is equivalent to your logic only in well-defined cases.
In the instance under discussion in that section of the book I'm referencing, allowing the user to instantiate the special string type was precisely the behavior intended to avoid. The idea being that in the following three examples, the first succeeds and the rest fail at compile time:
Query("SELECT * FROM Users WHERE id = ?;")
id := "6"; Query("SELECT * FROM Users WHERE id = " + id + ";")
id := 6; Query(fmt.Sprintf("SELECT * FROM Users WHERE id = %d;", id))In Go, the solution was very tidy: it aliases string to an unexported internal type that consumers cannot instantiate. String literals can be coerced to that type, but variables that already have type information associated with them are rejected at compile time.
The C++ solution was a bit more complicated and involved templates.
The certificate is indeed stored in a TPM:
> Desktops and laptops use an X.509 machine certificate and a corresponding private key stored in the system certificate store. Key storage, a standard feature of modern operating systems, ensures that command-line tools (and daemons) that com- municate with servers via the AP can be consistently matched against the correct device identifier. Since TLS requires the client to present a cryptographic proof of private key possession, this implementation makes the identifier non-spoofable and non-clonable, assuming it’s stored in secure hardware such as a Trusted Platform Module (TPM).
I'd be interested to hear more about how they are trivially exploited. I had not heard that was the case, and from the quote above it seems that information had evaded Google's engineers as well since they are considering credentials stored in TPMs to be non-clonable.
The primary trouble with SSH keys is that they can only authenticate one thing: they're either something the user can exfiltrate from the machine, in which case they authenticate the user and trust the user to authenticate the machine, or they are locked to the machine, in which case they authenticate the machine and trust the machine to authenticate the user. This was a common difficulty that Google ran into when implementing Inventory-Based Access Control for their BeyondCorp system: protocols are typically designed to authenticate a single identity, which may be the user or the machine but not both, which leaves the door open for users connecting from unauthorized endpoint devices whose security posture cannot be validated (if only authenticating the user) or adversaries stealing authorized endpoint devices. The point of the Access Proxy is to provide two distinct authentication steps: one to authenticate the device via mutual TLS and one to authenticate the user via their SSO credentials.
> In the cases of gRPC and TLS traffic, we wrapped the bytes in an HTTP CONNECT request. Wrapping has the obvious downside of imposing a (negligible) performance penalty on the transported protocol. However, it has the important advantage of separating device identification and user identification at differ- ent layers of the protocol stack. Inventory-based access control is a relatively new concept, so we frequently find that existing protocols have native support for user authentication (e.g., both LOAS and SSH provide this), but extending them with device credentials is non-trivial.
The value added by private networks is not only the fact that all of the people on them are trusted, but also that (at least in enterprise systems) all of the devices on them are trusted as well. In the absence of network trust, the policy decision point needs a different way to authenticate the device to replace the authentication step that would normally be done at the time when the device attempts to connect to the VPN or the internal network. In an equivalent system that used a VPN, the database utilized to make device access control decisions would already exist, but the policy would be applied when the device attempts to join the network, and then the never again as the device freely interacts with other resources on the network. The access proxy applies that device authorization policy at resource access time instead of network admission time.
When someone tries to connect to a service, instead of having a firewall verify their device is trusted by checking the IP address is within a trusted range, the device is authenticated by the Access Proxy using mutual TLS.
Authorization decisions incorporate both device and user privileges. A machine that isn't registered as being physically bolted to the floor inside a physical security domain won't be able to access certain highly restricted resources. A machine that isn't registered as being up to date on security patches will also have privileges restricted. A machine which does not present a client certificate or presents a client certificate that is no longer trusted will only be able to access services intended for the public.
Instead of treating the subnet as a de facto database of trusted machines, there's an actual database of trusted machines that is incorporated into authorization decisions at access time.
I've also frequently seen "most" used to mean "a majority", though, in which case GP's use of the term is precisely consistent with the facts in their source.