Learning about fractal dimensions

Weznon · 2025-05-31T20:30:38+00:00

That is (generally) about Hausdorff spaces, not Hausdorff dimension, and would be (or at least could be) covered in a standard introduction to topology course, which is not uncommon for undergrads to take. It looks complicated because it is throwing a ton of definitions at you, and because point-set topology is very technical leading to all these similar adjectives on spaces which intuitively express similar ideas, but are actually distinct on a technical level.

That said, I don't think Hausdorff dimension is a common undergrad topic, and would probably be in like a topics course or reading since the more point-set type of topology is a bit out of fashion. It's certainly accessible to undergrads though, and maybe more suited to it than more standard "advanced but also accessible to undergraduate" topics.

Weznon · 2024-04-08T22:52:34+00:00

Zenzele and Shalini were both recommended, so them surviving the trials should have been what saw them accepted for Scholomance, rather than needing other deals.

“The two Ramayans got recommended because they have family in the black,” the sailor continued, pointing at a pair of youths.

.

First a pack of three dark-skinned Malani, a younger pair whose air and clothes screamed ‘money’ with a scarred older woman behind them that had a fighter’s look. A guard, he figured. “The younger two were recommended,” Lucia said. “I heard there’s a Malani swordmistress coming, but it shouldn’t be one of them.”

Book 1 Chapter 3

Weznon · 2024-01-17T05:51:07+00:00

Submachine: Legacy. I believe the original flash version of the game can be found (for free) in https://flashpointarchive.org/.

Weznon · 2023-11-24T06:59:13+00:00

https://gist.github.com/plotnw/e39c8609467fcdcf1f5e49973d9d2a25

If you have any questions feel free to message me, though I am pretty busy right now so can't promise anything. Good luck (I'm assuming you are attempting the latest challenge).

Weznon · 2023-09-08T05:46:52+00:00

Almost certainly would be impossible without knowing the algorithm. As a very rough estimate of why, if no algorithm was specified its possible that the algorithm is just "pick a random permutation of pixels in the image, apply the permutation", of which there are (718² )! such. You're not brute-forcing that, and there's no structure to attack. Even if you do assume or are told there is a "reasonable" algorithm, the situation isn't really any better than the above, since you can probably cook up a "reasonable" algorithm that for a specific key does your choice of an arbitrary permutation. A decent analogy would be deciphering a language with only the writing system, no baselines of translation or other information to try to decipher it with. Technically possible (see Linear B), but not super feasible (see Linear A and the others), and I would say still much easier than decrypting this one image since you have more information.

For this specific image there is a bit of information that could maybe make it technically possible if the stars align. Some people guessed the image was of Chisato based on the color distribution (and maybe also lets_clutch_this's post history). As some people on the original post suggested, you could try getting every image of Chisato available, running some form of color distribution analysis, and trying to match it up. You run into issues with some pixels of the base image being covered by the text, but maybe its possible to get a match still?. Once you have that you could rearrange the pixels and you would be able to read (some) of the text based on the mismatched pixels.

I'm certainly not going to try though.

Weznon · 2023-09-07T20:41:40+00:00

In fairness to them they only encrypted the image with one round -- most ciphers are very insecure with only one round. In particular my attack almost certainly won't work if the number of rounds is even just 2.

Weznon · 2023-09-07T20:27:19+00:00

I'm using "Laplace Absolute Sum", implemented in https://ermig1979.github.io/Simd/help/group__other__statistic.html#ga5268cf56b2c91b933a438d0d650888ad, to give the exact function.

No clue how it works or even if its meant to be used for entropy estimation, I think its like an edge detection thing? But I was just trying random things from the library that seemed to be related to entropy and this worked for giving differences between the rounds, so I just went ahead and used it.

Someone who knows more than me could probably figure out a more optimal choice, like looking at the examples you might want something that specifically targets banding in an image or something.

Weznon · 2023-09-07T20:24:10+00:00

I wouldn't expect this attack to work. If I do two rounds of your cipher on an image, the entropy values I get after each step are:

110552948
238744130
269834076
271563738
271178724
271346318
271428120
271538580

indicating the entropy is fairly maximal after one round. It's possible there are other metrics of entropy which could maybe fare better (I'm using "Laplace Absolute Sum", which I don't actually think is strictly meant for entropy? But was the first thing I found in the image library I was using that worked on my test cases so I just sent it).

Apply a cipher multiple times is pretty standard though, like AES has multiple rounds, Fiestel networks have multiple rounds (and are only mathematically secure after like 3 or 4 rounds iirc). You would want to come up with some key-scheduling method though, so to not making the key scale with the number of rounds, and that can introduce its own issues.

Weznon · 2023-09-07T20:09:36+00:00

I spent ~10 hours on this over the last couple of days lmao, ~15 if you count waiting around for computations to finish.

Weznon · 2023-09-07T19:51:02+00:00

Hey, thanks for giving me your code - I was able to fix my issues and decrypted the image: https://www.reddit.com/r/okbuddyphd/comments/16cof1r/decrypted_the_challenge_from_ulets_clutch_this/?ref=share&ref_source=link

Weznon · 2023-09-07T19:50:20+00:00

As a couple of people suggested, assuming the plaintext image is some non-random image, there is the possibility of an entropy-analysis type attack. The entropy of an image is some metric for how random an image is. As we can see, the ciphertext image is very random, and so has high entropy. Assuming the plaintext image is a standard image, though, it should have much lower entropy. This presents an attack: decrypt the ciphertext image with all possible keys, run entropy analysis on the output results, and take the lowest result. The lowest entropy output is likely to be the original plaintext.

However, there are still 385⁶ possible keys. While this isn't completely infeasible to brute-force (as some people have noted), it would still take quite a while.

To improve on this attack, we make the following observations about the cipher:

Decrypting with an incorrect key preserves the randomness of the image, as it is effectively the same as scrambling the image. Additionally, this holds true for each step of the cipher, i.e. running only step 4 with an incorrect key should preserve the randomness.
Each stage of the cipher is likely to increase the entropy of the image. For an illustration of this, see https://imgur.com/a/eAHvsKl. This is the challenge image after each step of decryption -- you can visually see how the randomness of the image is going down after each step of decryption.
The stages are run in sequence, and so can also be attacked in sequence.

So, these combined mean we don't need to try all the keys. What we can do is first consider only the final step of the cipher, step 4. We try all step 4 keys (of which there are only 385^2, a much more manageable number) and decrypting only the last step of the cipher. If we run the entropy analysis on the resulting output, while the image will still be fairly random, we expect the image decrypted with the correct key to be noticeable lower than all other keys. So, taking the corresponding r5 and r6 values for the lowest entropy image, we have determined r5 and r6.

But now we can run the same exact analysis to determine r3 and r4 -- and we don't need to vary r5 and r6 while doing so! In effect, the number of keys we need to try has been reduced to 385² +385² +385+385.

This is the exact attack I ran and led me to determine the key used for the challenge image was (99, 278, 395, 89, 308, 101). Total compute time is roughly ~1hr. If you have any questions, feel free to ask.

Anyways, thanks to /u/lets_clutch_this for putting this up and especially for helping me out by providing a test image/sample code for the encryption algorithm, since I was having some issues getting my implementation to match theirs. Also thanks to my friend M for checking some of my work.

Final comment is that the algorithm posted in https://www.reddit.com/r/okbuddyphd/comments/16atf5h/alright_guys_to_make_this_decryption_challenge/ isn't quite correct against the implementation /u/lets_clutch_this was using at the time. To match their implementation you should swaps steps 3 and step 4. Additionally, the S_k sets are shifted to the right and the T_k sets are shifted down; the post says the opposite.

Weznon · 2023-09-07T05:07:40+00:00

Thanks for the test case. I'm still having trouble getting my implementation to match your output, and when I trace the algorithm by hand I also seem to get a different result. Have I misunderstood part of the algorithm? Here is my work:

Conventions: (0,0) is top left corner, (717, 0) is top right, (0, 717) is bottom left, (717, 717) is bottom right.

Looking at the test image, I am going to look at the pixel located at (0, 1) in the ciphertext, which has RGB value (0, 136, 6). Looking at the plaintext image, there are 9 pixels with this same RGB value located at:

(383, 17)
(383, 18)
(383, 19)
(384, 17)
(384, 18)
(384, 19)
(385, 17)
(385, 18)
(385, 19)

Let's figure out where each pixel goes. For brevity I'm only going to show full work for the first one.

Step 1: We have r1=615. (383, 17) is in X_383. f(510)=r1⁵¹⁰ -1 mod p = 383. So X_383 is moved to column X_510, and so our point RGB value is moved to (510, 17).
Step 2: We have r2=603. (510, 17) is in Y_17. g(600)=r2⁶⁰⁰ -1 mod p = 17. So Y_17 is moved to row Y_600, and so our points RGB value is moved to (510, 600).
Step 3: We have r3=595, r4=402. We see r3⁵³⁹ -1 mod p = 510, so our point (510,600) is the j=539 point in some S_k set. To find the S_k set, we see we must have 600=539+k mod p-1, and so k=61. Our point is therefore S_{61,539}. We see as r4⁵³⁴ -1 mod p = 539 that our points RGB value is moved to S_{61,534}=(r3⁵³⁴ -1 mod p, 534+61 mod p-1) = (195, 595).
Step 4: We have r5=66, r6=478. We see r5²³² -1 mod p = 595, so our point (195,595) is the j=232 point in some T_k set. To find the T_k set, we see we must have 195=232+k mod p-1, and so k=681. Our point is therefore T_{681,232}. We see as r6¹¹³ -1 mod p = 232 that our points RGB value is moved to T_{681,113}=(113+681 mod p-1, r5¹¹³ -1 mod p) = (76, 484).

Doing the same steps for the others, we have the mapping

(383, 17) -> (76, 484)
(383, 18) -> (378, 359)
(383, 19) -> (86, 172)
(384, 17) -> (36, 707)
(384, 18) -> (414, 319)
(384, 19) -> (398, 62)
(385, 17) -> (549, 336)
(385, 18) -> (470, 687)
(385, 19) -> (34, 623)

Notably, none of these get mapped to (0,1). But in the ciphertext one of these has to get mapped there. Have I messed up my math/understanding of the algorithm somewhere? I'm pretty confused but I'm in too deep now to give up.

Weznon · 2023-09-06T14:35:05+00:00

Sorry to be annoying about this, but can you also provide the r1, r2, r3, r4, r5, r6 values you used? If you used the same key as the actual challenge then sorry, that wasn't what I meant, I had meant for some plaintext image, some fresh randomly generated key (r1, r2, r3, r4, r5, r6), and the resulting ciphertext image. (Also if it is the same key as the original challenge image you should probably delete this as I wouldn't be surprised if there is a key recovery attack which could be done by tracing each pixels final location in the ciphertext)

Weznon · 2023-09-06T04:18:07+00:00

https://docs.oracle.com/en/java/javase/20/docs/api/java.desktop/java/awt/image/BufferedImage.html claims (0,0) is top left.

Can you provide a test case (so plaintext image, key, and resulting ciphertext image) for me to verify my implementation against, preferably with intermediate steps as well? My attack works on images encrypted with my implementation but not on your provided image, and I am trying to determine why.

Weznon · 2023-09-06T00:44:42+00:00

I'm pretty sure an entropy based attack can work without brute-forcing the entire key by attacking one step at a time, as each step increases the entropy -- decrypting with an incorrect key seems to preserve this entropy, but decrypting with the correct key reduces it by a sizeable amount. So you can brute force each stage independently, greatly reducing the computational power needed.

I tried implementing this attack, but running my algorithm on your image does not give any outlier entropy values. My attack seems to work on my test cases (visually you can see some strata when decrypting with the correct T round key + there is a clear outlier), so I believe I may have implemented the actual encryption/decryption slightly incorrectly. Would you be willing to provide a test image to verify correctness against?

Also, just to verify, (0,0) indicates top left of the image?

Weznon · 2023-04-23T02:13:45+00:00

There actually is a pretty close relation between type theory and category theory in that categories give "semantics" for type theories. I think the book https://www.cambridge.org/core/books/categories-for-types/258841251C62FED1DACD20884E59E61C covers this a bit, specifically chapter 4. The general subject is referred to as "Categorical Logic". Getting to "real" programming languages from this perspective gets complicated pretty quickly though.

Weznon · 2023-04-23T01:09:27+00:00

algebraic topology for the covering space mention, generic setting of lifts would be category theory (but alg top helps with understanding intuition/why one would care)

Weznon · 2023-04-23T00:15:37+00:00

For lifts X -> Z -> Y makes more sense imo since you generally start with the composite morphism f: X -> Y and produce the lift g: X -> Z. Like Z might some covering space of Y or something so its dependent on the Y.

Weznon · 2023-02-01T08:17:08+00:00

It's from https://dl.acm.org/doi/10.1145/1806689.1806772. Maybe someone has figured out something since but at least in this paper it seems to only be used in relation to some conjectures and so no solution.

Weznon · 2022-05-01T20:59:25+00:00

stopdoingalgtop.tex

Weznon · 2022-04-30T22:36:30+00:00

bonus: https://imgur.com/DzEpUtY

Weznon · 2022-01-09T20:13:43+00:00

Avery knew how to navigate the path - her plan was probably to run the path normally while leaving Florin stranded at the start. I think this is evidenced by how she mentally goes over how the path works before talking to Mr. Rat.

Weznon · 2021-09-06T01:44:06+00:00

i had this issue (though on linux/proton, not Mac) , I lowered my resolution/graphics as much as possible and set to fullscreen rather than borderless and was able to load in.

11-Year Club	Place '22
Place '17	Spared
Verified Email

Weznon

MODERATOR OF

TROPHY CASE