Trip Calculation

Task description

Laura and her friends take a trip every year. This year they’re keeping it local, a short trip to Zagreb, on a limited budget, so they use a program to add up the travel costs. Some go by plane, some by bus, some by tram. You get the source code and a Linux program to study. It’ll help your programming career, and maybe elsewhere too :)

The original was in Croatian; this is my translation. This task is filed under binary exploitation, but it’s really a logic puzzle: no memory tricks are needed, just inputs that get past every check.

What the program checks

We’re given the C source. The flag is printed only if a function called provjeri_parametre (“check the parameters”) returns success. Here are its rules, translated, with the prices it uses (plane 310, bus 150, tram 10, budget 550):

• the plane cost must not equal one ticket’s price, so you can’t send exactly 1 person by plane;
• the same for the bus: not exactly 1 person;
• the tram cost can’t go over 100, so at most 10 people by tram;
• the grand total must not be below 550;
• the grand total must not be above 550.

The last two together mean the total has to be exactly 550. The first three rule out some of the easy ways to get there.

Hitting the budget exactly

So we need plane, bus and tram counts where plane*310 + bus*150 + tram*10 = 550, without using exactly one plane or exactly one bus, and with no more than ten trams.

A bit of arithmetic lands on 0 planes, 3 buses and 10 trams:

0 * 310  +  3 * 150  +  10 * 10  =  0 + 450 + 100  =  550

Zero planes avoids the “exactly one plane” rule, three buses avoids the “exactly one bus” rule, ten trams is right on the limit, and the total is exactly the budget. We entered those three numbers and the program printed the flag.