Extrude curve perpendicular to surface

I have a doubly curved surface, with a curve projected onto it.

I'd like to create a surface using the curve as a base, where at all points the surface will be extruded from the associated surface normal - basically, the two surfaces should be perpendicular at all points.

My current approach is sampling the surface normal at a number of points, drawing lines based on the associated normals, and then lofting between those lines - however, this is producing problems at curve inflection points.