Extracurricular challenges

[_madness_]

@upsidedown,
I may have forgotten to give my checksum for #113626: 14fe2671a62d5ba76d843679962b6f0f
But from my previous comments you may have realized that I had already been to the future and obtained the solution. Tenses in English when time-travelling can be tricky, so I think the correct thing so say when something happens in the future for you but happened in my personal past is that I willen solved it twestermorrow.

I think the correct thing to say is: “wow looks like there must be a pretty strong variation in the gravitational tensor round us! we had better be/have been careful” Harry

[_madness_]

Inspired by @AndGiggle’s use of GF(25), and because this week’s challenges are too easy,
and because it is Black Friday, here are some gifts for you.

First, what is Black Friday? BF is a dark day of consumerism that you have imported from
the United States. It began here (here = the U.S.) as the day after Thanksgiving, when
our attention is freed from the gluttany of the turkey-killing day and turns toward the
gimme-presents day. You, hedonsitic consumerists [edited by Harry] imported BF but
not the day of thanks. In Norway, I even saw signs that said “Black Friday all week long”
(Black Friday hele uke); like Thanksgiving never existed. Someone in the forum was
wondering about my level of evilness. So consider these challenges a pay-back for stealing
our darkest but most holy of holidays.

These challenges take the Caesar and Vigenère ciphers and replace addition in Z/26Z with
multiplication in GF(27). The moduli for two of them are given; for the other two not.
Elements (which are polynomials) of GF(27) are mapped to integers by evaluating them at
x = 3, which is the modulus of Z/3Z, the underlying field from which the coefficients of
the polynomials are drawn. Letters of the alphabet are mapped to nonzero integers only:
A=1, B=2, …, Z=26. If any of this sounds strange or confusing to you, consider it an
opportunity to go out and learn something. Evil, remember?

Challenge GF(27)_1:
cipher: Caesar
modulus: x^3 + 2x + 1
ciphertext: DBJPFYYLVFJAVBPPBSPFSFXBSPXBAAKJALJZBJPSBLPKJAMKGJFPPFXBDFZFRJMBLSPBZLJZJFP
PFVBLOBLGBSKNLRKPMFCPGLHKJALJFPMBSBYYFSPKPFVZMKGKNFCVZXBLSLJTPSKLVBQNBIPPMBRSBPNMBZJBDD
FYDBBKJAMKGNFGBXLNHLMBVIVBDDXSFHBJZFRJGLJPSTKJACDBVBDDVTPFXBAKJVKYBLALKJRMBJPFFFVZYFSLN
MLJAB
md5(PLAINTEXT): 934c48d3e7d78ab2d392bf56206d0d6f

Challenge GF(27)_2:
cipher: Caesar
modulus: ?
ciphertext: WAYEAREITTORBQFTSVFBRUSQNXTYARMTITTOVOTREURIQVWNQITNWROBVOTREURIQVWXRNUXUXY
OBYEARVOWTBIUWAQETFREWDQNBEQSATNEYITJROXUFYSTDNTWKATBFUROBDNTWKATBFUYRXETOWTOKTBWQTOBYW
md5(PLAINTEXT): a7e49656ab26a750d41354484f40f7be

Challenge GF(27)_3:
cipher: Vigenère
modulus: x^3 + 2x^2 + x + 1
ciphertext: WLUPFZIIAZTRTGFZIRNYDYBDMLXYLCIJSSRLFJPNOTIHXYFWUEBZXLRABZXNMQJZSNHJNWOOIJM
SQNUEUYWLNYFESBFKFREGTNUSQCOSXWRGNNYVGLCRBROBDIBJTBTJBEVDAXDYDDXEBZXDNDBYQZIIRSOMCKCVXB
JUSQYRDCTQTBCKGLSETUJATTOYAMQHSHFZYGMUUHRKAPQDOPEXDVYLPRBUFIYUMMNLWGFFOBWLUPOMASAPFDRVT
FTMLSSGFZEYBHLTAYMZSNESDOSEDCRHFZEGTVMXICBVKGTJIHQMTNTROQTJNHDDWYTGRNOPFYIRBKCRYGMNBVYL
UPIXOERQRMRGMAFZFRLEFSBNOUZNUTIIRSLZIIRYGDSGBZTWAVANXBENYVZGSLFERLFHTFTKATXMDGCJXR
md5(PLAINTEXT): d1b993390d150a2bc53f1a86a8e78c24

Challenge GF(27)_4:
cipher: Vigenère
modulus: ?
ciphertext: HNULERILEELIVWQMHDHFFOSSTLHETTOLMFFXSAQIBUATLVYVXNEENTFIHOCNOPVJTXGIPOHNRQE
XLRCNNIGFAFXUIPOVLDONTILEPZDRDTEQTTFLTOTNEHJOLXUYMUHCOQOKNUSPTYVEATOLCSXAEXGLSXOHRLRGXD
FXUEAYGHHUSFFLEEOTJOFSBORFIYOEKDGJNEENOPEIIJTTFLTSNRDMDLAZLIPUURGDERYWAPNOAALIQMSGALIJT
LSNATETCNEQNPMUCJQRHGANUURPONIDDIRLDSAQEROCSVFNUCOZXZAEROXDTCQTTEGUACVWJDMPELSVLVRPEIJF
GITOCTDTEETLFWFTGMNVETCETCQRFWAMRRWQFDUEJPFNUKANETDHUIUYGIXRGILATPFRSEGHPFINTLEPGAFGHEP
AECKFIUNAPOYARLRQDZPGLSSGUPHUSGFHFGEANEQNPFHFTLHNPEKDUNJMVJGUDAOTIGHDGEUHDFNUZNRLVBRLDH
CGHHUEIYSEYLEPYTAYZNRYTCHMFCEXIJZLGXASRMRFDATXKDCDAPHETFFOTOLMKXGIPZSZDRTRQECDHSBQIHLAO
BQYFFGHHAAAIURNKL
md5(PLAINTEXT): 3bbc3f50b2f401b39e5b27a809f6dae5

[upsidedown]

I’ll first offer some hints for my previous two ciphers: the plaintext of the 3×3 cipher is an excerpt from The Hitchhiker’s Guide to the Galaxy (as madness has hinted at 🙂 and the film that I was referring to for the 5×5 cipher is 2001: A Space Odyssey.

Third cipher: upsidedown-2025-3

Since it’s the third, I’ve composed three ciphers (written in the order they were applied to the plaintext):

1. Vigenere cipher, keyword length is not equal to the hill cipher block size
2. Autokey vigenere cipher, keyword length 6
3. 6×6 hill cipher

The alphabet is ABCDEFGHIJKLMNOPQRSTUVWXYZ?!’:.,_ (as before, underscores are used as spaces).

My program solves this in around 33 minutes (on 12 cores), so to save you the tedium I will reveal the first two columns of the inverse matrix. My program could break this in 2 minutes (on 1 core):

26 15  ?  ?  ?  ?
21 25  ?  ?  ?  ?
 1 22  ?  ?  ?  ?
13  6  ?  ?  ?  ?
27 15  ?  ?  ?  ?
19  1  ?  ?  ?  ?

I’ll also add that all three keys and the plaintext share a theme.

Here’s the ciphertext:

VHMI?XHCGVO,YOX?XLGUTPWKLGR?SSV,.FKNYJMC!?UADR!PAH,DU'OG:J,WBKO:SJHQXALWUQH
!UTU'BHOHA,F_EEARAYPONSNLW'XETFVMNOG:TEDICNDUHCK?R!KV?XWPM_TP'M_X!XQK:KGWWS
D_O:ZZEB.KS:!_'EAUUELK?!LJO.ZXK_.MRTD.IBL,DR!CFD!CV.NIQR.'LDCSALD:?NQFGEQHK
VLQFSUEGZXTBBZ,M:,'?BZOTP_TIKBZEGWJJE?YLBBB..P:TBY?ZYDFMERI._R!L?HIDWHKYFTO
Q,TTP.YJY,QHWJJE?YX.HV',KLR:WYOEILZJY!E:PJG'EO:HFTNHHXAM'Z,:ZQMQ.:TOJGAXGQ!
_VDO:AMEPRBZS?ZO,MNCOWSCM_:VEPZ?VEPS!NP!A?_!S!RIJDC''AXSGINJKCNU'OK__UFOV_:
DE'SBZ_VTER?VDUVBABM,XEYRL?PG:TAANBNJ:Z!QFPE'ZYVOZ,Z_TRGDHWGO',K,T_UZQNBOA.
N_FWFFFRLC,EC?QI'TNNVJQ.Y!LXK.A_JC!,.'NC?JCF:?:BG.:DH.Z:GEAOYV'FPGCIPIRHP,H
UYZKU?YE.:CIMOB.EO':ZQJJSYNIGB?GVPBNQQ,?GEN_,VQ!S!KCN.VCHRZ_NKTKALH_WWQN'.P
QMBCX!MMTS.!BCV.ZMX:WWRWMRTDIXZXH,KNKUTW,VJXV,BH.D!S:RSP?SWKHG!C,'RYWWFVZ,Y
Y!J!?QGAOBHKU!M:'IG:'VK,BSQJQIDXTPUM_MAKCLG.YDYXTV!QNA.M!!:FUASHBER,:MNUZNV
GV_TUQXNXCXAY,.:OWC!!IZXCJDQ,MFRQBBHHBA_JQBCQQBGLGGHLVS?_Z:OUC'DN?YF?X?MVFU
WTWDJAFFPS?.USH,TAO'WWIMER.TXEWBHOG'SSPXESRO?HUZHSEYYCK:AQKKSAQE?FL':XERC:I
.,.RWT!,QZZCSURUKBPTMZZUQGCOMLFM_ADO_B'IITZA:_YZ_KXJNKHDWG?_VPUDPXOXGGLMDHD
JNJK,'RJUDYIJ'PXDRMORTAHW,VJXV'TQ'E?W?!A!IDRTQ'DWNJ.UXHBKO:EV:,VSX?ELO'_ZGE
THYTGTDIDZMKQT'KVEFDBS.TJQWKSPMQR:XWK'KS'KMZOKRU'GVYPKNLYHNBJRWA,YE,FHK.HVW
KOIXQPCAKMPB:!SDAEG:'KX_MYSEQR_HQ?CB:!RFQWFTPWESTQQ.VFLXJQVMSZU!DQ'MNBUG?C'
!CSC.MJ'VN:.BDPWQOIUKMWPYSJJF'TGPZFTSHPI'FOXU,DMYIA?:.:PFA'ZOU'!?SI'AZ,SGHW
'IUE?YPT'JQRHDIHMW:OAPMTE:MHXELV?SDCJO','T_ACZC'P:,WF:AWEJKK.IS_EVJKZASWTRI
':DHMQTXKFFZ:C!UVBX_LF?X:AKY!DNPKLN:J!MC,HI:O.QN!!IBU,YUO_MHIGJYOM!PIX!CNAD
AXBNDOC?I'_!IK?::WQJ.,EO.FZTV?LOZXLQJ''XEZJ:ON_SDDOQUHTUFF,:IR,A:VTFX.YVWNG
MEJDK_HVQWXWAWDNZPI?PO,IXX:HIQNCGLPL!BUN:RLIEAP',TGJKEK'F_:EB!!_CD',_V'K'C:
LHP_X_JZWSBAE:KXMYE?NYXKVQLMMZ:S_QVPGR,HQR?Z:'FEVMAFJFVDCEHTZERSLPANUSR!ECJ
GE.SYKMNK'_:IFTYS,'CFNY!BBLAWQ,CG'N'IXQCQ'EO:VHDJR?W_O:O!_GBQVIFDHNOTTFIGRS
XYSAFAFDOKOI'KETZDJA?P'QRVJBU_YHASDFSU.HFZKTC!AJYEQIOQCGCARK_KVKXGTNXA.'M.Z
M!EJQRUREXQH:K:K,!APBIJ!CCVZQNUWHD:.SRJ,Q','!UHJU_FBTJ!ZJ?CD!IKJFWSWX.J,SHL
E'GCK?XRKFTAEABM_M_.E.O:I?PSNC_?L,QWAYVKBQW::YUDEXNBA.J:UFI.PELCRR!ATZDG,Z?
SPO,X'G:WEFECP!DCQTNSIS:BX_KZ!A!GJ:UJ!DO!NJZNWPQJWGM.LJN',CMEZ'Z.O?!WBFOAX.
AWI:GBCCKQA:?T!YEIJEPUEV:!MQMBGQF!PUQQHVN'F,,CXVA'BNF_._CSHVSJ'VXHA:BRGG?PE
QEB.OEVKDE,T!EEGNLOV_.AGQJZREXHJH'IWPGYPSK.?VPQGYGJ?YNHIWBWIEPYORGNIQ:?WCK,
XZBMXRGQHYEYSNM.'OOY'JFKTRC_:QJ?!TSN_JI'PS,AWR'BECYN:LHM_HUYSRWZ_YKFFMAZLKL
P,E_Y?XXLIYO,GLXXN!K:PJOHJXO!?CFBJK,HZXZJ'.A!?.W!VQRHPRVL,IGQSVFBXSQBTIBRHW
QZVV_TSMSBV,PJT:BBBBJR:OTL'JUOLSL_S?PFM.TK'LXIA?MYVWZNNW!E'R?AOGF!!OQYYRCRZ
SZYUQKKQJOLQVRLR!MGGZKD_:UB_YEBZJ'TZEAPZNENTFGPT.NVN'.R!RUGO_DPHJDKAI!,LXBS
ZMQO:XGN.QOHQU::GNXO',.SONQOSKXV_QV.HMAPIOL,.SFJKWARWTAO'FMC:,VMDBZP'R,UVRX
SSBBVOH_KD'QYZ?EBEDVAOTVGYW,O,FVTRVEQOXBYWP_NTEBC,FLRVRJ!YYHLDKWFQGKEJAR:L_
S?FNWNAGQTSVKD.,F''JWKIGXXQ!A?WZIV_DO,BXSLOW,OU_QLQY?:T!KCL'QEKAUOSUX:YCFT.
?VS,DDRBB?:T!?O.P__IPHNFVBONCQSYAZUITM!SYG,IKS.AMJAGGEWAY.SDGW._JLK!!GSIWDF
SWMT:APEYKVTHDBDBDUWVPCILGBACN:KX.Y.ZE!E.'Q,SVU!_BJRPTRZXAIO,TY_QUCPQLFRFKY
C'IMRRNLC.,B!VBFTYX:OZ.PYGV:YYSBIXWG!IED,D_WGA,HTADY:C,OEWITAOPTFXDGNUKEKVB

[Puzzling_Pelican]

@upsidedown
Part 3 (with ALL punctuation) || Puzzling_Pelican = 7e65a44b67bc47c921cc3189cf687381
I do wonder what would happen if the autokey length was different, it would be noticeably harder.

[upsidedown]

@Puzzling_Pelican nice, well done. I wonder how long your program took to run?

I think that if I used an autokey keyword length k != 6 you would need to consider n=k/gcd(-6%k, k) rows of the inverse matrix simultaneously, then try n! permutations of those rows, and then solve the resulting sequence as an autokey+vigenere combination. Would certainly be harder, but it’s effectively just multiplying the boring searching part.

[_madness_]

Thanks for this post Madness, I will take a longer look at it as I might consider your suggestion!! It is a really nice idea. Harry

[Crackerjack_404]

@upsidedown, in reply to post #113809

I’ve been meaning to learn more about Rust/functional programming for a while but haven’t got around to it yet. What was it like writing the solver in Rust? Curious if you ran into any bottlenecks with memory layout. I mostly program on my MS surface which isn’t the fastest but it’s alright, a GPU compute shader sounds really cool! I’d be super keen to hear how it goes if you try it.

[upsidedown]

@Crackerjack_404 I really like Rust as a middle ground between pure functional and imperative languages. There are aspects of functional languages that I really like, particularly sum types, match, and higher order functions like map, all of which are included in Rust via enum, match and Iterator. I sometimes feel that I have to contort the algorithm in my mind when writing purely functional programs, and it’s nice to have the option to write imperatively (sometimes imperative code is just neater and easier to read). Rust also has default immutability and variable shadowing which are small things that greatly reduce the number of stupid mistakes I make. Option and Result are great and I fully understand how they work, whereas all the jargon about Monads (joke explanation: “a monad is just a monoid in the category of endofunctors”) and other weird maths concepts go a little over over my head. I’m sure that all the mathematical concepts that Haskell encodes are very beautiful!

The Rust program I wrote has a very small memory footprint because, as I detail below, I decrypt the ciphertext directly into an array of letter frequencies, so the program is CPU limited rather than by memory. At risk of going on too much about Rust, I love that it makes easy-to-use parallelism possible and safe.

I did end up writing a GPU compute shader, but it was only around 10 times faster than the Rust program (when run on 12 cores) which was somewhat disappointing. It’s quite possible that there’s something I’m missing that would make it faster, as this is only the third compute shader program I’ve written (the first two were a brute-force SHA1 searcher and a rainbow table generator). My hill program uses two separate shaders, a map stage and a reduce stage.

In case you don’t know, GPUs divide work up into workgroups and invocations (and subgroups…) which sort of address points in a virtual 3d cuboid. There are x*y*z workgroups, and each workgroup contains u*v*w invocations. The global invocation index is made up from the coordinates of the workgroup and invocation. I used a 64*64*1 workgroups with 16*16*1 invocations.

The map stage decodes the global invocation index into a row of the inverse matrix, then decrypts the ciphertext once, incrementing counters for each letter in a 26-element (or whatever the modulus is) array which keeps the memory requirements down. I compute the IoC from that array, then using a precomputed array of letter counts from a corpus I find the relative shift resulting in the greatest angle between the counts vectors, ie. max_i(angle(corpus_frequencies, rotate(plaintext_frequencies, i))). If the score is above a threshold and the IoC is sufficiently close to the corpus IoC, I atomically (candidates[atomicAdd(index, 1u)] = … in WGSL) add the global invocation index and the angle score to a fixed-size array of candidates; I used a size of 10 per workgroup. So for each workgroup there’s an array of size 10 * sizeof(Candidate) bytes which is all contained in a big output buffer. This buffer is around 320KiB.

I then used a workgroupBarrier() which ensures that any memory writes in any invocation before the barrier are visible to reads in any invocation after the barrier. Then I bubble sort the candidates in the first invocation only (when local_invocation_id == 0). Typically each workgroup will have zero or, very occasionally, one candidate so even though this bubble sort isn’t parallel I don’t think it will have a noticeable effect on performance (it’s dwarfed by the time taken to decrypt and analyse the text). I could do this in another stage (possibly using a parallel sorting algorithm), but because I filter out candidates with score < 0.9 there are so few elements to sort that the overhead of another compute pass is probably higher than this bubble sort.

The reduce stage is basically just the merge() function from mergesort. It operates on two lists of candidates, and puts the (up to) 10 highest value candidates in the first list. This runs for around log2(n) times, where n is the number of workgroups.

I divide the space of inverse rows to search into fixed size chunks so the GPU doesn’t silently complain about me giving it too much work at a time. For a 5×5 matrix, the map stage takes around 60ms and the reduce stage around 50µs (miniscule), with overall runtime around 200ms.

Something I do for the CPU version is filtering out bad inverse rows by taking the IoC of the first 50 characters and stopping early if it’s too far out, which speeds things up a fair amount. IIUC I can’t do this on a GPU because all the invocations run together until the last one completes, and when I tried this it made little difference. The biggest performance improvement was, somewhat surprisingly, allocating a few large buffers that precompute the integers modulo the alphabet length, including one of size matrix_dimension * pow(alphabet_length – 1, 2). My GPU can read the corresponding entry of the buffer much faster than it can do the modulo operation (I guess that’s not all that surprising because division is generally not a primitive instruction).

[upsidedown]

This was a MAMMOTH post, and I was wondering if it would be better as a Christmas guide to the Enigma and the Bombe? Would you consider rewriting it for my Miscellany? I still have it and will repost in the original form if you prefer. Harry

[upsidedown]

@Harry yes that’s a good idea. I’ll email you when it’s ready!

Looking forward to it, thank you. Harry

[Crackerjack_404]

@upsidedown

Thanks for the detailed explanation, that was genuinely fascinating! I’m still pretty new to GPU compute, so this was really interesting, especially the part about precomputing modulo tables to avoid division, neat trick!

I learned a bit (very basic) of Haskell back in sixth form, but hoping do some more on functional programming later in the year (it’ll probably serve as good time pass once NCC season is over!), do you have any reading/learning recommendations?

[_hacker_]

Here I am, exploring the forums for any sort of nudge or hint towards 10B…

…then I find this. WHY CANT I FIND ANYTHING???????????

seriously we’ve been doing this for who knows how long and the best thing we have is the most obvious pieces of info.

i need help, and the casefiles dont light any bulbs to me either.

[Crackerjack_404]

@_hacker_

Sometimes progress here isn’t about finding new clues, but about re-interpreting the ones you already trust.

Many of us have been/are exactly where you are now. When it feels like you’re only left with the obvious observations, it can help to stop asking “what haven’t I tried?” and instead ask “what do these facts force to be true?” You will have your own idea(s) about what the cipher is, if you can test them conceptually or structurally, rather than exhaustively necessarily, that often gets you a good way.

Case files are gonna be annoying slow for the first few days, so all we can do is trust that Harry is feeling suitably generous when it comes to revealing better hints.

[upsidedown]

@Crackerjack_404 here are a few compsci books I like:

Crafting Interpreters: free on the internet, but the print book is a work of art. It’s also really well written and a remarkably easy read on a complex topic.

Security Engineering (Ross Anderson): if you are interested in computer security (and non-computer security) and all of its various interactions with the world, this is the book. The whole third edition is available for free on the author’s personal website.

Networking for System Administrators: short, easy read which gives you a good understanding of computer networking.

For Haskell/FP I don’t have any particular recommendations beyond the resources linked to on the Haskell website. I’ve heard that Haskell from first principles is very good (i.e. comprehensible and easy to read), but it’s quite expensive and print copies are no longer available.

[upsidedown]

I wonder whether anyone has had a go at my Bombe challenges?

[Author]

Posts