I can kind of understand that the corners would in fact slide a little… you might need to touch up the animation curves in the IPO editor, which tends to try and smooth things out by default, hence the slide. Also, when you do any walkcycle, a good workflow is to do the contact positions first so the cube is shuffling its feet from along the ground. Only when you are happy with this do you go back to the inbetween frames and raise every other foot / corner position into the air for the “passing” position. At this point, you may find sliding occur due to some IPO curves needing to be sharpended at contact.
There are other things you can try. It might be that you want the corners of the cube to stretch a little (Disney style). The mesh stays as a basic cube, but you have a full leg-rig armature within.
If this is a set piece (e.g. not a generic character you’re likely to use for other shots) then I’d go with dropping the cycle altogether (too uniform… yawn snore every step the same) and make a simple zigzag rig which unfolds to create the walk.Basically, you have a bone from one corner foot to the other, but this is the last in a zigzag chain, which gets pressed together flat to come out something like the spring of a jack-in-the-box.