Regarding C++ Lectures

For the attendees of 2012's C++ lectures at the State Univ. of Groningen:

Here is the archive of stuff that accompanies the lectures,
Here are the lecture notes.
Read all about Joren Heit's and Erik Mulder's attempt and evaluation to crack OTG on a multinode supercomputer! They wrote a PDF report!

Off the Grid

Steve Gibson
Challenge
Can you crack OTG? Read below... The prize: eternal fame and a set of Zen magnets.
Downloadables
- A sample 26x26 Latin square, used in the below encryption example.
- otg, a Perl script that implements Off The Grid encryption. decryption, and square generation.
- Encrypted text that you're supposed to decrypt.
- Long encrypted text (700K) so you have more data to play with.
Changes to this page
- 2011-10-23 - Initial
- 2011-10-25 - Added the long version of the encrypted message to solve.
- 2011-10-26 - otg script upped to V1.01.
- 2011-10-28 - Added the first-attempt movie.
- 2011-11-17 - Improved the description of the encryption process.
- 2012-02-13 - otg script improved to avoid Perl warnings, thanks Stuart Skelton.
- 2012-02-22 - Added info regarding my C++ lectures.
- 2013-01-14 - Added report by Joren Heit and Erik Mulder.

Off the Grid

In 2011 I gave a lecture on information security at the State University of Groningen (RuG) (If you're interested, there are slides in PDF format). As a little puzzle and food for thought, I introduced Off The Grid encryption. Plus I added a little challenge. Well here it is.

Off The Grid is invented by Steve Gibson (www.grc.com). Read all about it on https://www.grc.com/offthegrid.htm. The idea of this encryption is basically that:

All hand-usable encryption methods, such as Ceasar's cipher, or Fairplay's cipher, have been cracked; the currently available computing power makes bruteforcing just too easy.
However, how nice would it be to have an encryption algorithm that's easy enough to perform by hand, but still impossible to crack by computers? Such a method could be safely performed without any electronic means - "off the grid" - but would still be safe.

How does OTG work?

OTG encrypts a-z

OTG will only encrypt letters (a-z). It can be arbitrarily adapted for the entire ASCII range (or bigger, UTF-whatever), but let's stick with a-z. That way it's still nicely usable by hand. With this restriction, it doesn't differentiate between uppercase and lowercase.

Latin Squares

You start with a Latin square of 26x26 cells. Each row and column have every character just once (like Sudoku, but there are no sub-squares). To illustrate, here are two mini-squares for the letters a-g. The left one is pretty trivial. The right one also mixes casing ("a" and "A" should be considered equivalently, more on that later).

a b c d e f g
b c d e f g a
c d e f g a b
d e f g a b c
e f g a b c d
f g a b c d e
g a b c d e f

b D C e A G f 
F a b g c d E 
A e D B G F C 
D F G c E b a 
C g a F d E B 
G B e a f c d 
E c F D B A g

What's the algorithm, what's the key?

The key of OTG is (a) the square, (b) the position that you start encrypting (or decrypting). For now let's always take position (0,0), the upper left corner.

So what's the algorithm? For every character a-z in the input, OTG will output 2 characters. Here's how. First a description, then an example to illustrate:

In order to encrypt a character, start scanning from the scan coordinate, which is initially (0,0).
Take turns scanning horizontally and vertically. We'll start horizontally. So the first character must be scanned for in the top most row.
Given the fact that we're working with Latin squares, we are always sure to find the character that we want to encrypt. There's no need to switch to a different row or column.
When scanning horizontally:
- If the character to encrypt is to the right of the scan position, then output the 2 characters following the input character. Move the scan position just beyond (to the right of) the output characters.
- If the character to encrypt is to the left of the scan position, then output the 2 characters preceding the input character, but in reverse order (reading right-to-left). Move the scan position to just before (to the left of) the output characters.
- If the character to encrypt is at the scan position, then act as if it were to the right; i.e.; output the two characters following the input character, and move the scan position to the right of the output characters.
- When outputting the characters, or moving the scan position, we may need to "wrap around" the row.
When scanning vertically:
- If the character to encrypt is below the scan position, then output the 2 characters below the input character. Move the scan position just below the output characters.
- If the character to encrypt is above the scan position, then output the 2 characters above the input character, but in reverse order (reading bottom-to-top). Move the scan position just above the output characters.
- If the character to encrypt is at the scan position, then act as if it were below; i.e., output the two characters below the input character, and move the scan position below the output characters.
- When outputting the characters, or moving the scan position, we may need to "wrap around" the column.

An Example

Here's a random Latin square for a-z. Let's encrypt the message "hello" In the figures below, the scan position is indicated by a little circle. The output characters are in a box.

Encrypting: "h", horizontally. 1. Start at (0,0), the "S". 2. Find "h" horizontally. 3. Output the next 2 characters, "CG". 4. Move scan position to the "W". So far nothing out of the ordinary.

Encrypting: "e", vertically. 1. Start at (24,0), the "W". 2. Find "e" vertically. 3. Output the next 2 characters, "Fj". 4. Move scan position to the "v". So far nothing out of the ordinary.

Encrypting: "l", horizontally. 1. Start at (24,18), the "v". 2. Find "l" horizontally. 3. Output the next 2 characters, "SE". 4. Move scan position to the "G". Note that we had to scan left. The output is therefore "SE" (right to left).

Encrypting: "l", vertically. 1. Start at (4,18), the "G". 2. Find "l" vertically. 3. Output the next 2 characters, "Os". 4. Move scan position to the "k". Note that we had to scan up. Then we found the "l" at the topmost row, so we had to "wrap around" to the bottom.

Encrypting: "o", horizontally. 1. Start at (4,23), the "k". 2. Find "o" horizontally. 3. Output the next 2 characters, "Nq". 4. Move scan position to the "d". Note that we had to scan right. Then we found the "o" at the rightmost column, so we had to "wrap around" to the leftmost position.

To summarize, the input string hello encrypts into the output string CGFjSEOsNq.

Why are there lower and upper case characters in the square?

OTG was originally invented in order to encrypt the first 6 characters of a site name (e.g., amazon for amazon.com) into a site-password. Hence the upper case characters that sometimes occur. Given the above sample squre, amazon encrypts into BPFdTvXYuCmt. Having the upper case characters makes brute-forcing harder.

For the purpose of this challenge the upper case characters don't really matter (in fact, they might make the solving challenge even easier).

Can OTG decrypt?

Yes. Just apply the algorithm in reverse; it works just fine.

Do you have something to play around with?

Of course. As a download here's the Perl script otg, which implements Off The Grid. It can:

Generate Latin squares,
Encrypt strings on the command line or files,
Decrypt,
It accepts arbitrary alphabets (but defaults to a-z).

If you want to play around with it, follow these simple steps:

Download the script, and save it to a file, say /usr/local/bin/otg.
Make the file executable using
```
chmod +x /usr/local/bin/otg
```
Generate your Latin square (your encryption key), using:
```
otg -g print > MySecretSquare.txt
```

Try to encrypt, say you have a file plain.txt:

otg -l MySecretSquare.txt encryptfile plain.txt > encrypted.txt

Try to decrypt:

otg -l MySecretSquare.txt decryptfile encrypted.txt

Here's the "usage" information of the otg script:

This is OTG V1.02 - Off The Grid encryption/decryption made easy!
Read https://www.grc.com/offthegrid.htm for more info.
Copyright (c) Karel Kubat, karel@kubat.nl, http://www.kubat.nl.

Usage:
  otg -g [-a ALPHABET] [-n SWAPS]          print
  otg -l FILE [-a ALPHABET]                print
  otg -l FILE [-a ALPHABET] [-s SEED] [-v] encryptfile FILE
  otg -l FILE [-a ALPHABET] [-s SEED] [-v] encryptstring STRING
    Flag -a: Default ALPHABET is abcdefghijklmnopqrstuvwxyz
    Flag -g: A new grid is generated.
    Flag -l: A grid is loaded from the FILE (use - for stdin)
    Flag -n: Default SWAPS is 100. More is more random.
    Flag -s: Seeds encryption/decryption. Default is to start at (0,0).
    Flag -v: Makes encryption more verbose

Typical usage:
  otg -g print > MySecretGrid.txt
  otg -l MySecretGrid.txt encryptfile Plain.txt > Encrypted.txt
  otg -l MySecretGrid.txt decryptfile Encrypted.txt

The Challenge

The challenge is of course to break OTG. Given a long enough encrypted text, can you reconstruct the square that produced it, and decrypt into a meaningful text? Specifically, the below is an encrypted message. What's the message? (This text is also available as a download. Incase you need a longer blob: here is the same message, repeated 10 times, so you have more encrypted data to play with.)

yI oB IS EU ab Hj ZG ZD Vp jc wb bz rk eD Tc uN pW qp IK rX ev wT vU gy hv jc 
wb bz xF OD Yl Md XM xg Ks oE kf wX tV sr xF jA yr mX PG Wb gK jT iA RQ Je cx 
jD Ic aH tP tf Go EO pT FE nF Aw RG yg Jr Tl JO ad pH ZK Dc eY Gz Ur gh Is rB 
TN Uy bK md jZ Am tQ Wm yN Rt DC oQ cP sC Tz fz vf ph Bw Eh OX cT Yl vR ha yg 
WE dS ad de an by ta eD Yt Ic Qp wn Uq tb PJ Zg fL lT Aw Md zM hP il Zd yo Mt 
lk bN BJ mO rQ xg fb AV sI Jd rN Ry Bt fa Aw RG nv Xt Ix DY Nq Xg hM de zt JT 
ks Rq XM Kd TJ WL Xm dB JU Gz Hv Qv hs Qb Cg yl ps nf vp Su eK iM rd fQ KA ea 
GQ Ic aH tP eK Aj CR CI nM Ch wb Vf pW Ar fH WL qp oB tj mX bT Vf rt jt dg Bz 
th QH nc rY SU dS bf Wb bX kJ Fx sG LU sr Et Rt as QV zN dX vf LQ vH tO fD bk 
Rt NM gk De Kj qJ CQ JX tR WU Tp Nm gK jT tV xU fD Hj ca rX vG mO kT EH nS wt 
sK wd gt Mi kI lq Dx hs tE jR vy Er lO Ct ox Fh zN Tv lk hp TN Uy Li dU sk Eq 
xm gU LU Vh qz YD NF us nS ZJ tj Ux de Cw lQ hp Xc pe zS YK Rq Ji Uv sZ sV ch 
Sl Is aL li hv oN oX Im xF pH JN cT rt Nb rz DW QR ic rz HS xM yu re Jd Sl jR 
yI Oe CZ pL BQ sd Nv IK tf SL Ng Ry Bt Eh vU gy BT jR yI Qb WO HY SO JO bK md 
md kS MT Cw UD zU PA SL Ru lT cO Qe FB Ot IF oQ nc qw nM UM pQ oB sM Sd iM JT 
Hp Ng Qt ap bo DZ oX vj eR Ux kg AV WE Bj Zj HG dN UM as Qw ad eI PJ Wy zU jP 
xM Rq gk zL Qt Cb nc Kw rt Ch hz jB Ro qr FH Hl xZ nZ WO IK nO jB Qe su sl HI 
LM qf mD oN DP Ep xQ Ps PQ Ia zs yl ps Sd cn Rt CD oa zN qP BY VF EY Jk Wl cx 
LM IL bT Ji TU zD pR wT lk oQ Jr xg Ks YF Lf mq Sh CA mc dC AE hp NX Tl Wl Fp 
ER UE Vq vk iM Ax ks tv WE dS Mh tM XU sC YF UM CI oz Oh Lv Wr aW sa SY WM OC 
Cg bw ws Qv Je gs RJ EA uD Bj Zj bH LI ng XY Cs hk wT Qp MU Ri zP rk ea Qu vT 
fD eD PG cY iK SP ih TC hu nZ BO Fz LS KS WI BZ ab Oa Yl bz lS sd pQ oB ML DE 
ji fk gk mt DB Cb OX cT dr iM lY Zk Tr pz Qy Vh Se jD xm QM kr BY VK rX vG Fi 
Oa Nb ok KS WI BZ ab Oa hs Qb WO qR WM TF BD wd nM hs tE Rv Xd ZJ Rt Px ZC hp 
Xc HF PG Ej Wl aM md ZI BT bz zv zp yS oJ ok DL sz Jd kI RT tE Kd of Ft zU Bl 
Mp XN RJ yg vp Zl cu Zf bK md Gy pH lY dJ JN jw CD Kd fY Eq yO pH rt WL zU sd 
pQ cN Iw Gk DC hs Ch mN IY jT tV xU fD Hj ca rX vG mO fJ nd gF tw EF GN yo Nl 
Lr pX hz QL SL tv md cT hs eQ wJ HQ La FL rM Ic lk ao xN ng oX Bo BO Fz QV Vf 
JN DG BT bz zv DL sz Cw sE qs bs JX tR ae za hg OX MO yN gh dn UZ vy Er OD gh 
bK Nm yS ZO rz iM sh BV yH gZ Hy hp Es bx it Uy nM xg Ks tv WE dS Mh jA Uq tb 
iA VQ Vp CT zP HF KI VJ MH Ck hv xE hC ks yw Os wQ LX Wp RS Sh FO Lp by Je cx 
xm wP Wv Ps Hg Jd GE rA FB bW aW Nb aW mI Lb zS cd rB BO nD Hy XD lc pa Mh SF 
FB Uy Li aC fq Nm aU xb Hn YD at vh sg zF ad sG vp WL qp UW bo xM Tk eB sg fa 
dx sL ZU Zd CE tb Hp hs Ch kJ Gu hp Es Uq wb jR TM WQ BH zP OJ vI sM Sd iM JT 
Hp dJ lY Zk zT nW WE dS GP DL mX Mt Od ZU zO rX Mh CH Ex YH dk MX XV vU zP yZ 
EI JO ad de YX Xg bK aR CE Nl dn gU Qh GU gK ba ps XL xF xK KY km UT DY qP LK 
qJ Rq CQ JX tR tC Aw RG vf EU wb Vf al nr pW mA fu kv ad de YX vr jc Dj Od pj 
Vp ZU zO rX hi Cw UD qt RW mu AR xy tj Ux PF rX Mh tb Yl if Td bx Bk Tl hs eQ 
Rp Xd RJ yg Gy mu zO dS Mh tb Yl if Td DU aL Wb pO pz IS Ji yH xU vm VQ sk Uv 
wb Vf JN cT rt WL qp Ps Hg Jd GE rA FB bW ks mt KL bP BQ Oe fu ax qJ vt Cg eV 
BQ Wa Iy mt EK us Ro qr PJ Jd Gu DX zG xg pT Ry LB Oj KL bP Es Wm Xp Rp Od dC 
tV xU Tg DW xj tB PF aE bX Ic nv Wu Xr fk xM fZ dW ax RW rY dW Fu OX Fv RJ ry 
Oi jb gt HC Wl cx GL dC FH Hl xZ ZJ Vc Oa dr Aj CR vL kg zc FM DU Vz iM bX Ic 
nv RQ at LX sh tX DC Jd xF tb IY xP hv CO YF Kd QB zB Wp RS jQ AV av Pz bX dH 
tj hE Ge Kc bo QM Mb Sz Od jp yw QV zN lT CN Xp Vq by Xm hX id kJ yS rX sY RT 
tE Fh az XW sd zU bT bP BQ ZC hV tv WI rY CE zK Ai gh GA nA DU bw PJ dJ lY oQ 
bs kC tf SL vf Ux YF hC rd tM JB kJ zh Ic Qp tM JB GX rz rx Mq Dy tZ ig tf LX 
al mZ lz EQ eK iM sh HW kI oj dV wX ub Rt Lf Dc gd aW CD Nb di VA tj Jd Sl dU 
BO Fz Fh Rq fJ IJ DA Jr gk Pa Kn sd sl HI nH Qv gK jT ZD hj PQ aC sY oj Kj pe 
SX Wx QG uc Se Mu Sc Jr Tl sk zr pH hs Oe CZ uy vG mO fJ QT Td DU aL Wb FN gy 
PE rY yo Gz bT Vf rt Ch hz Om IY xP jQ zc SO xB Qp ry tW su yH Ji yH hs EW JH 
bo xM Tk eB CD xE tN wd EF Fu rb gU pR CT Mg Gu lO DY Fx JX tR br kt HW dx aC 
vG SR jg eD cJ UK ER tf Wx wd tQ cd FN nL kZ IN zG oN oX jc hU li Xs Bl WO Qv 
ta DZ DP gy Cg eV BQ Wa jc tb iA pf Wl tb PJ Ux YF Mo pO pz kt QV Ua Bt ZR QF 
xm xM BE Bl Uz ba ps fk qS cG ER hp sk sP kZ WL ja YH BG Sk AR QL SL lZ GA nA 
UJ rY CE Gz oX eV aB AV zG dw GL pa hi rX vG hj md qw ev pj Jf iJ vG mO yw md 
dh GU eg uM xm gU vp WL iK Bj qb um Rl IL bT Ji Wm pj Xc HF PG Mi dx xg Ks lH 
tQ Bj fC QF xm xM UI qJ dh HK Vp MN YF IN fH ER Je Vy Hw XL lF QM Ik lT xF jA 
yr IS hQ Fz Nz eV BQ Wa Nk nr JN kL nu oQ cP Os Ex QT Jf sr lF FT lJ Ic vU sO 
gK oE Is hp TN Uy ih gU Yt Ic Qp BE DN cj BH Om IY xP jQ Vk BY OJ CE xr ij ft 
PG Nl dn IK Od ap bo ZU md UA MJ jA vh LY PN li Bw XM Lf Uk FS dS pT WB gk bw 
VK nf ba NM Yt Uq ja QT YI mt rz jA yr hE Li sL lv Ck PQ yQ Cn Oa Rp rX sY RT 
tE oa Bw wd ZG ab rU md WI YH MW rX hM YH RJ pX IA Fp WM TF BD wd jU QT Td Uq 
hU li lO Ct GZ tO Cg JH bo xM CQ IJ be DY qP Gm Ix kg wX Zg vy rX Mh FQ YX rw 
TB fi ps XL bM QT XN QN ja nr ZK Fz LS vR UG dJ lY oQ br qB WO Zl uN sy ku Xw 
Yt DU WO IK hS tb PJ PR RJ kj kI RT WI Gk vy rX hi Cw UD Bq yF VJ MH dn Tk Xg 
hi Cw UD Bq bk nc yv FK WI YH ER LS WL UN CQ IJ DA sr kI pz Ko jA yr or Ix DY 
Nq Wn Wr Oa gk ab KI eV aB Xp ta ZU RB jp fJ IJ FC xW Ng cI QC dn kg LK RW rY 
mj LY iA pf Wl et LF wT Qp AV av zP qN sq dL Ic vU JO hM Xw mB PK vW LK La dn 
BE Bl KL hE pR QN wb UM pQ wq Zx MK JB yZ Vp dM zO Xr kf dn za Jf YF vK cm Wm 
zG Ch rk vL eY Mt as Se bs CH Ex YH dk by FN Ru hU jA zl WB Fi cU zN Ae gk VJ 
MW rX vG hj jc Dj Od QN KY pT BF oI Vc LH md UA Qt sg ps Er OD qm xm eV Es Wm 
La YH RJ lB Xm Rq QC Mi xF Mt CI XD Ai Ft dn QM EG gX KA ea Hp QL rz Mi SJ jk 
tE Rq gk Qv Je gs RJ AV HP wd vj VJ dk ZJ KY pT gs PR RJ lB Xm Rq QC Wb iY DZ 
Qt HQ dm Qf GZ LY wm kU IS Jd Sl dU aZ Vk LB UN ps Jo JY wT UT DY qP cX CE EG 
qp sn TJ Nb di pX th uS zO dS be ac bT dJ pW Ic Nv DY EG RQ Je cx Ih pj ER fa 
Aw CS lz Rh de rX ev uS md jc hU li Xs sp cT Ax MW Er QC Mi Aw Md Iy WL Rt oN 
DP OJ IC Jd th NQ nv HW rk jP Yt Ic Qp tM JB WT hu MB yF VJ GQ Ic nv HW rk vL 
bz WB Fi gN lR bW RJ pX zv tO yn Mi th QH kt QV Dh cx Xo wn fD CI Mn Jd Sl oa 
Ua Bt cd kc bL xB fH Ps dN WE dO Bj Xo wn BT bz dx sL ZU Zd yH gZ gt Aj CR vL 
kg zc xt pj sE HW rk br dr Zd Nv wX cu xM Tk ZH OV ks yw Os wQ Er QC il rz FQ 
SL lZ yv AW ps fk gk mt KL gN GL pa sY sg za ac UN rB NX Ar wQ Bq Qx zp jg Wr 
IF EU ab bk Lp by ta Ug wl ig Zj zS RW pH dr iM lY bN Yt Ft dn QM ht rq qI jp 
kT GU eg uM fr kn WI YH ER fa kI jy aB sp nM jR xw Md Nz vb AP Ma pQ ZI gC Go 
sI Ux de rX GP DL mX cU yv Hy Fm ZO rz Mt kf Bv HB mo Fi Qy Qx zp tZ mN PJ Ux 
YF oa lO eD dn gU BJ cG ER mX JY zG CQ IJ YJ Eb QC lN br qB BT bz SJ Bl nD Rt 
CD Py CQ jE aO EU hu Rt uE FV wl RQ dr Mi vy UK fZ Bq yF VJ ks Px wb bP Nx wX 
cu xM Nz vb AP Ma pQ ZI af sO Op qf Rp UK fZ SL Bw kv GA Ax aW Nb aW cj KL Vf 
eJ Tl pW eI gK oE vy jb uN sy ku Yr dn CO bz mN dk vk WO Dz md UA OX cT al ed 
qf SR xm gU cn DY qP SA iM Ax Yl gZ tQ vI Ku qt Bm HW kI pz li YF Iy UM sl oE 
mv xB as zS up Dz PQ UM Nv Ow ks yl ps rX XU Nm cJ Ic Qp tM hQ jy wZ Vb YE Uy 
Mh tb Zf ph Bw Gu lO DY Aw jR dm Uy Kz vy nc Qv al dn za BM Tg Gz NU ch kI RT 
tE Nb di zc JB yZ wZ Ic Qp AV na rX eG GU KZ sy Tk VF gk

Conditions

The essense of the challenge is as follows. Me and a counterparty have in our possession the same Latin square. We're exchanging messages and chatting about highly secret stuff. You are tapping our conversation - listening on the wire - and you see only the encrypted text flowing by.
Crack the above encrypted text.
- You may assume that it's natural language text (though only a-z are encrypted, spaces and punctuation marks are skipped).
- Furthermore you may assume that the encryption started at (0,0), just as the example that I have given above.
- The encrypted message is a result of one (long) text, it's not a simple short sentence repeated ad lib.
- Also rest assured that the encryption square is different than the example above ;-)
Send me the solution by e-mail to karel@kubat.nl.
The first one to send me the solution gets the prize. As simple as that.
With your solution, send me a description how you did it, and preferably the code that solved it (I'm assuming that you'll need a computer for the cracking.)
I'm the sole judge of the validity or invalidity of your submission. For example, if you only guess the outcome without a complete decryption process, then your submission won't be considered.
The winner gets full credits, on this page, plus a set of Zen magnets (see video below).
I'm pretty sure that Steve Gibson will be very interested if you crack it. Should be interesting!
Oh by the way. I haven't started cracking this thing yet. I can't comment (yet) on the (im)possibility of the endeavor. I will give it a try though as soon as I find the time. However, also feel free to send me your deliberations, most interesting comments will be included on this page.
Good hunting!

My own attempts

Yep, I'm enrolling in the challenge myself. I might win the magnets, who knows ;-)

Honorary Mention: Parallel Approach

After my C++ lectures in 2012, two students of the University of Groningen took up the challenge to implement an OTG cracker on a massive multi-node supercomputer. Joren Heit and Erik Mulder published their findings in January 2013, and I'm very proud to add this information to my site. Without further ado, here is the report in PDF. Licensing information is contained within; basically, you're free to reproduce it - with attribution - just as I am now.